Download PDF - Competition hypergraphs of digraphs with certain properties II. HamiltonicityAll rights reserved. Copyright exceptions and limitations apply

ArticleOriginal scientific text

Title

Competition hypergraphs of digraphs with certain properties II. Hamiltonicity

Authors 1, 2

Affiliations

  1. Faculty of Mathematics and Computer Science, TU Bergakademie Freiberg, Prüferstraße 1, D-09596 Freiberg, Germany
  2. Institute of Mathematics, University of Lübeck, Wallstraß e 40, D-23560 Lübeck, Germany

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=ND⁻(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].

Keywords

ENG
hypergraph, competition graph, hamiltonian digraph

Bibliography

  1. J. Bang-Jensen and G. Gutin, Digraphs: Theory, Algorithms and Applications (Springer, London, 2001).
  2. J.E. Cohen, Interval graphs and food webs: a finding and a problem (Rand Corporation Document 17696-PR, Santa Monica, CA, 1968).
  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.
  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.
  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.
  6. D.R. Guichard, Competition graphs of hamiltonian digraphs, SIAM J. Discrete Math. 11 (1998) 128-134, doi: 10.1137/S089548019629735X.
  7. P. Hall, On representation of subsets, J. London Math. Soc. 10 (1935) 26-30, doi: 10.1112/jlms/s1-10.37.26.
  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. 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. 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.
  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.
  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.
  13. M. Sonntag and H.-M. Teichert, Competition hypergraphs, Discrete Appl. Math. 143 (2004) 324-329, doi: 10.1016/j.dam.2004.02.010.
Discussiones Mathematicae Graph Theory
2008/28/1
Export to PBN, Opens in new tab
Pages:
23-34
Main language of publication
English
Received
2005-01-14
Accepted
2007-09-24
Published
2008

DOI: 10.7151/dmgt.1389

Exact and natural sciences