Competition hypergraphs of digraphs with certain properties II. Hamiltonicity

Martin Sonntag; Hanns-Martin Teichert

Discussiones Mathematicae Graph Theory (2008)

  • Volume: 28, Issue: 1, page 23-34
  • ISSN: 2083-5892

Abstract

top
If D = (V,A) is a digraph, its competition hypergraph (D) has vertex set V and e ⊆ V is an edge of (D) iff |e| ≥ 2 and there is a vertex v ∈ V, such that e = N D ⁻ ( v ) = w ∈ V | ( w , v ) ∈ A . We give characterizations of (D) in case of hamiltonian digraphs D and, more general, of digraphs D having a τ-cycle factor. The results are closely related to the corresponding investigations for competition graphs in Fraughnaugh et al. [4] and Guichard [6].

How to cite

top

Martin Sonntag, and Hanns-Martin Teichert. "Competition hypergraphs of digraphs with certain properties II. Hamiltonicity." Discussiones Mathematicae Graph Theory 28.1 (2008): 23-34. <http://eudml.org/doc/270461>.

@article{MartinSonntag2008,
abstract = {If D = (V,A) is a digraph, its competition hypergraph (D) has vertex set V and e ⊆ V is an edge of (D) iff |e| ≥ 2 and there is a vertex v ∈ V, such that $e = N_D⁻(v) = \{w ∈ V|(w,v) ∈ A\}$. We give characterizations of (D) in case of hamiltonian digraphs D and, more general, of digraphs D having a τ-cycle factor. The results are closely related to the corresponding investigations for competition graphs in Fraughnaugh et al. [4] and Guichard [6].},
author = {Martin Sonntag, Hanns-Martin Teichert},
journal = {Discussiones Mathematicae Graph Theory},
keywords = {hypergraph; competition graph; hamiltonian digraph; competition hypergraph; Hamiltonian digraph; food web},
language = {eng},
number = {1},
pages = {23-34},
title = {Competition hypergraphs of digraphs with certain properties II. Hamiltonicity},
url = {http://eudml.org/doc/270461},
volume = {28},
year = {2008},
}

TY - JOUR
AU - Martin Sonntag
AU - Hanns-Martin Teichert
TI - Competition hypergraphs of digraphs with certain properties II. Hamiltonicity
JO - Discussiones Mathematicae Graph Theory
PY - 2008
VL - 28
IS - 1
SP - 23
EP - 34
AB - If D = (V,A) is a digraph, its competition hypergraph (D) has vertex set V and e ⊆ V is an edge of (D) iff |e| ≥ 2 and there is a vertex v ∈ V, such that $e = N_D⁻(v) = {w ∈ V|(w,v) ∈ A}$. We give characterizations of (D) in case of hamiltonian digraphs D and, more general, of digraphs D having a τ-cycle factor. The results are closely related to the corresponding investigations for competition graphs in Fraughnaugh et al. [4] and Guichard [6].
LA - eng
KW - hypergraph; competition graph; hamiltonian digraph; competition hypergraph; Hamiltonian digraph; food web
UR - http://eudml.org/doc/270461
ER -

References

top
  1. [1] J. Bang-Jensen and G. Gutin, Digraphs: Theory, Algorithms and Applications (Springer, London, 2001). Zbl0958.05002
  2. [2] J.E. Cohen, Interval graphs and food webs: a finding and a problem (Rand Corporation Document 17696-PR, Santa Monica, CA, 1968). 
  3. [3] R.D. Dutton and R.C. Brigham, A characterization of competition graphs, Discrete Appl. Math. 6 (1983) 315-317, doi: 10.1016/0166-218X(83)90085-9. Zbl0521.05057
  4. [4] K.F. Fraughnaugh, J.R. Lundgren, S.K. Merz, J.S. Maybee and N.J. Pullman, Competition graphs of strongly connected and hamiltonian digraphs, SIAM J. Discrete Math. 8 (1995) 179-185, doi: 10.1137/S0895480191197234. Zbl0830.05035
  5. [5] H.J. Greenberg, J.R. Lundgren and J.S. Maybee, Inverting graphs of rectangular matrices, Discrete Appl. Math. 8 (1984) 255-265, doi: 10.1016/0166-218X(84)90123-9. Zbl0545.05060
  6. [6] D.R. Guichard, Competition graphs of hamiltonian digraphs, SIAM J. Discrete Math. 11 (1998) 128-134, doi: 10.1137/S089548019629735X. Zbl0910.05030
  7. [7] P. Hall, On representation of subsets, J. London Math. Soc. 10 (1935) 26-30, doi: 10.1112/jlms/s1-10.37.26. Zbl0010.34503
  8. [8] S.R. Kim, The competition number and its variants, in: J. Gimbel, J.W. Kennedy and L.V. Quintas (eds.), Quo vadis, graph theory?, Ann. of Discrete Math. 55 (1993) 313-326. 
  9. [9] J.R. Lundgren, Food webs, competition graphs, competition-common enemy graphs and niche graphs, in: F. Roberts (ed.), Applications of combinatorics and graph theory to the biological and social sciences, IMA 17 (Springer, New York, 1989) 221-243. 
  10. [10] J.R. Lundgren and J.S. Maybee, A characterization of graphs of competition number m, Discrete Appl. Math. 6 (1983) 319-322, doi: 10.1016/0166-218X(83)90086-0. Zbl0521.05058
  11. [11] F.S. Roberts, Competition graphs and phylogeny graphs, in: L. Lovasz (ed.), Graph theory and combinatorial biology; Proc. Int. Colloqu. Balatonlelle (Hungary) 1996, Bolyai Soc. Math. Studies 7 (Budapest, 1999) 333-362. Zbl0924.05032
  12. [12] F.S. Roberts and J.E. Steif, A characterization of competition graphs of arbitrary digraphs, Discrete Appl. Math. 6 (1983) 323-326, doi: 10.1016/0166-218X(83)90087-2. Zbl0521.05059
  13. [13] M. Sonntag and H.-M. Teichert, Competition hypergraphs, Discrete Appl. Math. 143 (2004) 324-329, doi: 10.1016/j.dam.2004.02.010. Zbl1056.05103

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.