The competition numbers of Johnson graphs

Suh-Ryung Kim ; Boram Park ; Yoshio Sano

Discussiones Mathematicae Graph Theory, Tome 30 (2010), p. 449-459 / Harvested from The Polish Digital Mathematics Library

Détail

Publié le : 2010-01-01

Zbl 1217.05180

EUDML-ID : urn:eudml:doc:270824

Bibliographie

[000] [1] H.H. Cho and S.-R. Kim, The competition number of a graph having exactly one hole, Discrete Math. 303 (2005) 32-41, doi: 10.1016/j.disc.2004.12.016. | Zbl 1079.05041

[001] [2] H.H. Cho, S.-R. Kim and Y. Nam, On the trees whose 2-step competition numbers are two, Ars Combin. 77 (2005) 129-142. | Zbl 1164.05329

[002] [3] J.E. Cohen, Interval graphs and food webs: a finding and a problem, Document 17696-PR, RAND Corporation (Santa Monica, CA, 1968).

[003] [4] J.E. Cohen, Food webs and Niche space (Princeton University Press, Princeton, NJ, 1978).

[004] [5] 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. | Zbl 0521.05057

[005] [6] C. Godsil and G. Royle, Algebraic Graph Theory, Graduate Texts in Mathematics 207 (Springer-Verlag, 2001). | Zbl 0968.05002

[006] [7] S.G. Hartke, The elimination procedure for the phylogeny number, Ars Combin. 75 (2005) 297-311. | Zbl 1071.05041

[007] [8] S.G. Hartke, The elimination procedure for the competition number is not optimal, Discrete Appl. Math. 154 (2006) 1633-1639, doi: 10.1016/j.dam.2005.11.009. | Zbl 1100.05045

[008] [9] G.T. Helleloid, Connected triangle-free m-step competition graphs, Discrete Appl. Math. 145 (2005) 376-383, doi: 10.1016/j.dam.2004.06.010. | Zbl 1066.05120

[009] [10] W. Ho, The m-step, same-step, and any-step competition graphs, Discrete Appl. Math. 152 (2005) 159-175, doi: 10.1016/j.dam.2005.04.005. | Zbl 1080.05095

[010] [11] S.-R. Kim, The competition number and its variants, in: Quo Vadis, Graph Theory, (J. Gimbel, J.W. Kennedy, and L.V. Quintas, eds.), Annals of Discrete Mathematics 55 (North-Holland, Amsterdam, 1993) 313-326.

[011] [12] S.-R. Kim, Graphs with one hole and competition number one, J. Korean Math. Soc. 42 (2005) 1251-1264, doi: 10.4134/JKMS.2005.42.6.1251. | Zbl 1082.05046

[012] [13] S.-R. Kim and F.S. Roberts, Competition numbers of graphs with a small number of triangles, Discrete Appl. Math. 78 (1997) 153-162, doi: 10.1016/S0166-218X(97)00026-7. | Zbl 0889.05057

[013] [14] S.-R. Kim and Y. Sano, The competition numbers of complete tripartite graphs, Discrete Appl. Math. 156 (2008) 3522-3524, doi: 10.1016/j.dam.2008.04.009. | Zbl 1200.05173

[014] [15] J.R. Lundgren, Food Webs, Competition Graphs, Competition-Common Enemy Graphs, and Niche Graphs, in: Applications of Combinatorics and Graph Theory to the Biological and Social Sciences, IMH Volumes in Mathematics and Its Application 17 (Springer-Verlag, New York, 1989) 221-243.

[015] [16] R.J. Opsut, On the computation of the competition number of a graph, SIAM J. Algebraic Discrete Methods 3 (1982) 420-428, doi: 10.1137/0603043. | Zbl 0512.05032

[016] [17] A. Raychaudhuri and F.S. Roberts, Generalized competition graphs and their applications, Methods of Operations Research, 49 (Anton Hain, Königstein, West Germany, 1985) 295-311. | Zbl 0572.05050

[017] [18] F.S. Roberts, Food webs, competition graphs, and the boxicity of ecological phase space, in: Theory and applications of graphs (Proc. Internat. Conf., Western Mich. Univ., Kalamazoo, Mich., 1976) (1978) 477-490.

[018] [19] F.S. Roberts and L. Sheng, Phylogeny numbers for graphs with two triangles, Discrete Appl. Math. 103 (2000) 191-207, doi: 10.1016/S0166-218X(99)00209-7. | Zbl 0953.05027

[019] [20] M. Sonntag and H.-M. Teichert, Competition hypergraphs, Discrete Appl. Math. 143 (2004) 324-329, doi: 10.1016/j.dam.2004.02.010. | Zbl 1056.05103