DMGT

ISSN 1234-3099 (print version)

ISSN 2083-5892 (electronic version)

https://doi.org/10.7151/dmgt

Discussiones Mathematicae Graph Theory

IMPACT FACTOR 2018: 0.741

SCImago Journal Rank (SJR) 2018: 0.763

Rejection Rate (2018-2019): c. 84%

Discussiones Mathematicae Graph Theory

PDF

Discussiones Mathematicae Graph Theory 20(1) (2000) 93-103
DOI: 10.7151/dmgt.1109

CLASSES OF HYPERGRAPHS WITH SUM NUMBER ONE

Hanns-Martin Teichert

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

Abstract

A hypergraph ℋ is a sum hypergraph iff there are a finite S ⊆ ℕ+ and d,d ∈ ℕ+ with 1<d<d suchthat ℋ is isomorphic to the hypergraph ℋd,d(S)=(V,ℰ) where V=S and ℰ={e ⊆ S: d< |e|< d ∧ ∑v∈e v∈ S}. For an arbitrary hypergraph ℋ the sum number(ℋ) is defined to be the minimum number of isolatedvertices w1,..., wσ∉ V such that ℋ∪{w1,..., wσ} is a sum hypergraph. For graphs it is known that cycles Cn and wheels Wn have sum numbersgreater than one. Generalizing these graphs we prove for the hypergraphs 𝒞n and 𝒲n that under a certain condition for the edgecardinalities (𝒞n)= (𝒲n)=1

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] M.N. Ellingham, Sum graphs from trees, Ars Combin. 35 (1993) 335-349.
[4] F. Harary, Sum Graphs and Difference Graphs, Congressus Numerantium 72 (1990) 101-108.
[5] F. Harary, Sum Graphs over all the integers, Discrete Math. 124 (1994)99-105, doi: 10.1016/0012-365X(92)00054-U.
[6] 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.
[7] N. Hartsfield and W.F. Smyth, A family of sparse graphs with large sum number, Discrete Math. 141 (1995) 163-171, doi: 10.1016/0012-365X(93)E0196-B.
[8] M. Miller, Slamin, J. Ryan, W.F. Smyth, Labelling Wheels for Minimum Sum Number, J. Comb. Math. and Comb. Comput. 28 (1998) 289-297.
[9] M. Sonntag and H.-M. Teichert, Sum numbers of hypertrees, Discrete Math. 214 (2000) 285-290, doi: 10.1016/S0012-365X(99)00307-6.
[10] M. Sonntag and H.-M. Teichert, On the sum number and integral sum number of hypertrees and complete hypergraphs, Proc. 3rd Krakow Conf. on Graph Theory (1997), to appear.
[11] H.-M. Teichert, The sum number of d-partite complete hypergraphs, Discuss. Math. Graph Theory 19 (1999) 79-91, doi: 10.7151/dmgt.1087.