The sum number of d-partite complete hypergraphs

Hanns-Martin Teichert

Discussiones Mathematicae Graph Theory, Tome 19 (1999), p. 79-91 / Harvested from The Polish Digital Mathematics Library

Access to full text
Full (PDF)

Résumé

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 ₁, . . ., v_{d} : (i \neq j \Rightarrow v_{i} \neq v_{j}) \land \sum_{i = 1}^{d} v_{i} \in S$ . For an arbitrary d-uniform hypergraph the sum number σ = σ() is defined to be the minimum number of isolated vertices $w ₁, . . ., w_{σ} \notin V$ such that $\cup w ₁, . . ., w_{σ}$ is a sum hypergraph. In this paper, we prove $σ (_{n ₁, . . ., n_{d}}^{d}) = 1 + \sum_{i = 1}^{d} (n_{i} - 1) + m i n 0, ⌈ 1 / 2 (\sum_{i = 1}^{d - 1} (n_{i} - 1) - n_{d}) ⌉$ , where $_{n ₁, . . ., n_{d}}^{d}$ denotes the d-partite complete hypergraph; this generalizes the corresponding result of Hartsfield and Smyth [8] for complete bipartite graphs.

Publié le : 1999-01-01

Zbl 0933.05104

EUDML-ID : urn:eudml:doc:270567

@article{bwmeta1.element.bwnjournal-article-doi-10_7151_dmgt_1087,
     author = {Hanns-Martin Teichert},
     title = {The sum number of d-partite complete hypergraphs},
     journal = {Discussiones Mathematicae Graph Theory},
     volume = {19},
     year = {1999},
     pages = {79-91},
     zbl = {0933.05104},
     language = {en},
     url = {http://dml.mathdoc.fr/item/bwmeta1.element.bwnjournal-article-doi-10_7151_dmgt_1087}
}

Hanns-Martin Teichert. The sum number of d-partite complete hypergraphs. Discussiones Mathematicae Graph Theory, Tome 19 (1999) pp. 79-91. http://gdmltest.u-ga.fr/item/bwmeta1.element.bwnjournal-article-doi-10_7151_dmgt_1087/

Bibliographie

[000] [1] C. Berge, Hypergraphs, (North Holland, Amsterdam-New York-Oxford-Tokyo, 1989).

[001] [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. | Zbl 0702.05072

[002] [3] Z. Chen, Harary's conjectures on integral sum graphs, Discrete Math. 160 (1996) 241-244, doi: 10.1016/0012-365X(95)00163-Q. | Zbl 0867.05056

[003] [4] Z. Chen, Integral sum graphs from identification, Discrete Math. 181 (1998) 77-90, doi: 10.1016/S0012-365X(97)00046-0. | Zbl 0902.05064

[004] [5] M.N. Ellingham, Sum graphs from trees, Ars Comb. 35 (1993) 335-349.

[005] [6] F. Harary, Sum Graphs and Difference Graphs, Congressus Numerantium 72 (1990) 101-108.

[006] [7] F. Harary, Sum Graphs over all the integers, Discrete Math. 124 (1994) 99-105, doi: 10.1016/0012-365X(92)00054-U. | Zbl 0797.05069

[007] [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. | Zbl 0791.05090

[008] [9] M. Miller, J. Ryan, Slamin, Integral sum numbers of $H_{2, n}$ and $K_{m, m}$ , 1997 (to appear).

[009] [10] A. Sharary, Integral sum graphs from complete graphs, cycles and wheels, Arab. Gulf J. Sci. Res. 14 (1) (1996) 1-14. | Zbl 0856.05088

[010] [11] A. Sharary, Integral sum graphs from caterpillars, 1996 (to appear). | Zbl 0856.05088

[011] [12] M. Sonntag and H.-M. Teichert, The sum number of hypertrees, 1997 (to appear).

[012] [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).