Classes of hypergraphs with sum number one

Hanns-Martin Teichert

Discussiones Mathematicae Graph Theory (2000)

  • Volume: 20, Issue: 1, page 93-103
  • ISSN: 2083-5892

Abstract

top
A hypergraph ℋ is a sum hypergraph iff there are a finite S ⊆ ℕ⁺ and d̲,d̅ ∈ ℕ⁺ with 1 < d̲ < d̅ such that ℋ 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 w ₁ , . . . , w σ ∉ V such that ℋ ∪ w ₁ , . . . , w σ is a sum hypergraph. For graphs it is known that cycles Cₙ and wheels Wₙ have sum numbersgreater than one. Generalizing these graphs we prove for the hypergraphs ₙ and ₙ that under a certain condition for the edgecardinalities (ₙ)= (ₙ)=1

How to cite

top

Hanns-Martin Teichert. "Classes of hypergraphs with sum number one." Discussiones Mathematicae Graph Theory 20.1 (2000): 93-103. <http://eudml.org/doc/270220>.

@article{Hanns2000,
abstract = {A hypergraph ℋ is a sum hypergraph iff there are a finite S ⊆ ℕ⁺ and d̲,d̅ ∈ ℕ⁺ with 1 < d̲ < d̅ such that ℋ 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 $w₁,..., w_σ∉ V$ such that $ℋ ∪ \{w₁,..., w_σ\}$ is a sum hypergraph. For graphs it is known that cycles Cₙ and wheels Wₙ have sum numbersgreater than one. Generalizing these graphs we prove for the hypergraphs ₙ and ₙ that under a certain condition for the edgecardinalities (ₙ)= (ₙ)=1},
author = {Hanns-Martin Teichert},
journal = {Discussiones Mathematicae Graph Theory},
keywords = {hypergraphs; sum number; vertex labelling; sum graph; sum hypergraph},
language = {eng},
number = {1},
pages = {93-103},
title = {Classes of hypergraphs with sum number one},
url = {http://eudml.org/doc/270220},
volume = {20},
year = {2000},
}

TY - JOUR
AU - Hanns-Martin Teichert
TI - Classes of hypergraphs with sum number one
JO - Discussiones Mathematicae Graph Theory
PY - 2000
VL - 20
IS - 1
SP - 93
EP - 103
AB - A hypergraph ℋ is a sum hypergraph iff there are a finite S ⊆ ℕ⁺ and d̲,d̅ ∈ ℕ⁺ with 1 < d̲ < d̅ such that ℋ 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 $w₁,..., w_σ∉ V$ such that $ℋ ∪ {w₁,..., w_σ}$ is a sum hypergraph. For graphs it is known that cycles Cₙ and wheels Wₙ have sum numbersgreater than one. Generalizing these graphs we prove for the hypergraphs ₙ and ₙ that under a certain condition for the edgecardinalities (ₙ)= (ₙ)=1
LA - eng
KW - hypergraphs; sum number; vertex labelling; sum graph; sum hypergraph
UR - http://eudml.org/doc/270220
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] M.N. Ellingham, Sum graphs from trees, Ars Combin. 35 (1993) 335-349. Zbl0779.05042
  4. [4] F. Harary, Sum Graphs and Difference Graphs, Congressus Numerantium 72 (1990) 101-108. 
  5. [5] F. Harary, Sum Graphs over all the integers, Discrete Math. 124 (1994)99-105, doi: 10.1016/0012-365X(92)00054-U. Zbl0797.05069
  6. [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. Zbl0791.05090
  7. [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. Zbl0827.05048
  8. [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. Zbl0918.05091
  9. [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. Zbl0943.05071
  10. [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. [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. Zbl0933.05104

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.