ArticleOriginal scientific text

Title

The sum number of d-partite complete hypergraphs

Authors 1

Affiliations

  1. Institute of Mathematics, Medical University of Lübeck, Wallstraße 40, 23560 Lübeck, Germany

Abstract

A d-uniform hypergraph is a sum hypergraph iff there is a finite S ⊆ IN⁺ such that is isomorphic to the hypergraph d(S)=(V,), where V = S and ={{v,...,vd}:(ijvivj)d_{i=1}viS}. For an arbitrary d-uniform hypergraph the sum number σ = σ() is defined to be the minimum number of isolated vertices w,...,wσV such that {w,...,wσ} is a sum hypergraph. In this paper, we prove σ(^{d}n,...,nd)=1+d_{i=1}(ni-1)+min{0,12(i=1d-1(ni-1)-nd)}, where ^{d}n,...,nd denotes the d-partite complete hypergraph; this generalizes the corresponding result of Hartsfield and Smyth [8] for complete bipartite graphs.

Keywords

sum number, sum hypergraphs, d-partite complete hypergraph

Bibliography

  1. C. Berge, Hypergraphs, (North Holland, Amsterdam-New York-Oxford-Tokyo, 1989).
  2. D. Bergstrand, F. Harary, K. Hodges. G. Jennings, L. Kuklinski and J. Wiener, The Sum Number of a Complete Graph, Bull. Malaysian Math. Soc. (Second Series) 12 (1989) 25-28.
  3. Z. Chen, Harary's conjectures on integral sum graphs, Discrete Math. 160 (1996) 241-244, doi: 10.1016/0012-365X(95)00163-Q.
  4. Z. Chen, Integral sum graphs from identification, Discrete Math. 181 (1998) 77-90, doi: 10.1016/S0012-365X(97)00046-0.
  5. M.N. Ellingham, Sum graphs from trees, Ars Comb. 35 (1993) 335-349.
  6. F. Harary, Sum Graphs and Difference Graphs, Congressus Numerantium 72 (1990) 101-108.
  7. F. Harary, Sum Graphs over all the integers, Discrete Math. 124 (1994) 99-105, doi: 10.1016/0012-365X(92)00054-U.
  8. N. Hartsfield and W.F. Smyth, The Sum Number of Complete Bipartite Graphs, in: R. Rees, ed., Graphs and Matrices (Marcel Dekker, New York, 1992) 205-211.
  9. M. Miller, J. Ryan, Slamin, Integral sum numbers of H2,n and Km,m, 1997 (to appear).
  10. A. Sharary, Integral sum graphs from complete graphs, cycles and wheels, Arab. Gulf J. Sci. Res. 14 (1) (1996) 1-14.
  11. A. Sharary, Integral sum graphs from caterpillars, 1996 (to appear).
  12. M. Sonntag and H.-M. Teichert, The sum number of hypertrees, 1997 (to appear).
  13. M. Sonntag and H.-M. Teichert, On the sum number and integral sum number of hypertrees and complete hypergraphs, Proc. 3rd Kraków Conf. on Graph Theory, 1997 (to appear).
Pages:
79-91
Main language of publication
English
Received
1998-08-24
Accepted
1999-01-04
Published
1999
Exact and natural sciences