Discussiones Mathematicae Graph Theory 30(3) (2010)
449-459
doi: 10.7151/dmgt.1506
Suh-Ryung Kim, Boram Park
Department of Mathematics Education | Yoshio Sano
Research Institute for Mathematical Sciences |
The Johnson graph J(n,d) has the vertex set {v_{X} | X ∈ ([n] || d)}, where ([n] || d) denotes the set of all d-subsets of an n-set [n] = {1, …, n }, and two vertices v_{X1} and v_{X2} are adjacent if and only if |X_{1} ∩X_{2}| = d−1. In this paper, we study the edge clique number and the competition number of J(n,d). Especially we give the exact competition numbers of J(n,2) and J(n,3).
Keywords: competition graph, competition number, edge clique cover, Johnson graph.
2010 Mathematics Subject Classification: 05C69, 05C75.
[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. |
[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. |
[3] | J.E. Cohen, Interval graphs and food webs: a finding and a problem, Document 17696-PR, RAND Corporation (Santa Monica, CA, 1968). |
[4] | J.E. Cohen, Food webs and Niche space (Princeton University Press, Princeton, NJ, 1978). |
[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. |
[6] | C. Godsil and G. Royle, Algebraic Graph Theory, Graduate Texts in Mathematics 207 (Springer-Verlag, 2001). |
[7] | S.G. Hartke, The elimination procedure for the phylogeny number, Ars Combin. 75 (2005) 297-311. |
[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. |
[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. |
[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. |
[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. |
[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. |
[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. |
[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. |
[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. |
[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. |
[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. |
[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. |
[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. |
[20] | M. Sonntag and H.-M. Teichert, Competition hypergraphs, Discrete Appl. Math. 143 (2004) 324-329, doi: 10.1016/j.dam.2004.02.010. |
Received 14 April 2009
Revised 9 October 2009
Accepted 10 October 2009