DMGT

Discussiones Mathematicae Graph Theory 19(1) (1999) 79-91
DOI: https://doi.org/10.7151/dmgt.1087

THE SUM NUMBER OF d-PARTITE COMPLETE HYPERGRAPHS

Hanns-Martin Teichert

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

Abstract

A d-uniform hypergraph H is a sum hypergraph iff there is a finite S ⊆ [.2em][l]IN⁺ such that H is isomorphic to the hypergraph H_d⁺(S) = (V,E), where V = S and E = {{ v₁,…,v_d}:(i ≠ j⇒ v_i ≠ v_j)∧∑^d_{i = 1} v_i ∈ S}. For an arbitrary d-uniform hypergraph H the sum number σ = σ(H) is defined to be the minimum number of isolated vertices w₁,…,w_σ∉ V such that H∪{ w₁,…, w_σ} is a sum hypergraph.

In this paper, we prove

σ(K^d_{n₁,…,n_d}) = 1 +

d
∑
i = 1

(n_i-1) +

min

⎧
⎨
⎝

⎡
⎢
⎢

1
--
2

⎛
⎝

d-1
∑
i = 1

(n_i-1)-n_d

⎞
⎠

⎤
⎥
⎥

⎫>
⎬
⎭

where K^d_{n₁,…,n_d} 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.

1991 Mathematics Subject Classification: 05C65, 05C78.

References

[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 H_2,n and K_m,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).

Received 24 August 1998
Revised 4 January 1999