The sum number of d-partite complete hypergraphs

Hanns-Martin Teichert

Discussiones Mathematicae Graph Theory (1999)

  • Volume: 19, Issue: 1, page 79-91
  • ISSN: 2083-5892

Abstract

top
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 ≠ j ⇒ v i ≠ v j ) ∧ ∑ i = 1 d v i ∈ S . 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 σ ( n ₁ , . . . , n d d ) = 1 + ∑ i = 1 d ( n i - 1 ) + m i n 0 , ⌈ 1 / 2 ( ∑ 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.

How to cite

top

Hanns-Martin Teichert. "The sum number of d-partite complete hypergraphs." Discussiones Mathematicae Graph Theory 19.1 (1999): 79-91. <http://eudml.org/doc/270567>.

@article{Hanns1999,
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₁,...,v_d\}: (i ≠ j ⇒ v_i ≠ v_j)∧ ∑^d_\{i=1\} v_i ∈ S\}$. 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₁,...,n_d\}) = 1 + ∑^d_\{i=1\} (n_i -1 ) + min\{0,⌈1/2(∑_\{i=1\}^\{d-1\} (n_i -1) - n_d)⌉\}$, where $^\{d\}_\{n₁,...,n_d\}$ denotes the d-partite complete hypergraph; this generalizes the corresponding result of Hartsfield and Smyth [8] for complete bipartite graphs.},
author = {Hanns-Martin Teichert},
journal = {Discussiones Mathematicae Graph Theory},
keywords = {sum number; sum hypergraphs; d-partite complete hypergraph; sum graph; labelling; hypergraph},
language = {eng},
number = {1},
pages = {79-91},
title = {The sum number of d-partite complete hypergraphs},
url = {http://eudml.org/doc/270567},
volume = {19},
year = {1999},
}

TY - JOUR
AU - Hanns-Martin Teichert
TI - The sum number of d-partite complete hypergraphs
JO - Discussiones Mathematicae Graph Theory
PY - 1999
VL - 19
IS - 1
SP - 79
EP - 91
AB - 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 ≠ j ⇒ v_i ≠ v_j)∧ ∑^d_{i=1} v_i ∈ S}$. 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₁,...,n_d}) = 1 + ∑^d_{i=1} (n_i -1 ) + min{0,⌈1/2(∑_{i=1}^{d-1} (n_i -1) - n_d)⌉}$, where $^{d}_{n₁,...,n_d}$ denotes the d-partite complete hypergraph; this generalizes the corresponding result of Hartsfield and Smyth [8] for complete bipartite graphs.
LA - eng
KW - sum number; sum hypergraphs; d-partite complete hypergraph; sum graph; labelling; hypergraph
UR - http://eudml.org/doc/270567
ER -

References

top
  1. [1] C. Berge, Hypergraphs, (North Holland, Amsterdam-New York-Oxford-Tokyo, 1989). 
  2. [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. Zbl0702.05072
  3. [3] Z. Chen, Harary's conjectures on integral sum graphs, Discrete Math. 160 (1996) 241-244, doi: 10.1016/0012-365X(95)00163-Q. Zbl0867.05056
  4. [4] Z. Chen, Integral sum graphs from identification, Discrete Math. 181 (1998) 77-90, doi: 10.1016/S0012-365X(97)00046-0. Zbl0902.05064
  5. [5] M.N. Ellingham, Sum graphs from trees, Ars Comb. 35 (1993) 335-349. 
  6. [6] F. Harary, Sum Graphs and Difference Graphs, Congressus Numerantium 72 (1990) 101-108. 
  7. [7] F. Harary, Sum Graphs over all the integers, Discrete Math. 124 (1994) 99-105, doi: 10.1016/0012-365X(92)00054-U. Zbl0797.05069
  8. [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. Zbl0791.05090
  9. [9] M. Miller, J. Ryan, Slamin, Integral sum numbers of H 2 , n and K m , m , 1997 (to appear). 
  10. [10] A. Sharary, Integral sum graphs from complete graphs, cycles and wheels, Arab. Gulf J. Sci. Res. 14 (1) (1996) 1-14. Zbl0856.05088
  11. [11] A. Sharary, Integral sum graphs from caterpillars, 1996 (to appear). Zbl0856.05088
  12. [12] M. Sonntag and H.-M. Teichert, The sum number of hypertrees, 1997 (to appear). 
  13. [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). 

NotesEmbed ?

top

You must be logged in to post comments.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.