DMGT

Discussiones Mathematicae Graph Theory 30(3) (2010) 449-459
DOI: https://doi.org/10.7151/dmgt.1506

THE COMPETITION NUMBERS OF JOHNSON GRAPHS

Suh-Ryung Kim, Boram Park

Department of Mathematics Education
Seoul National University, Seoul 151-742, Korea

Yoshio Sano

Research Institute for Mathematical Sciences
Kyoto University, Kyoto 606-8502, Japan

Abstract

The competition graph of a digraph D is a graph which has the same vertex set as D and has an edge between two distinct vertices x and y if and only if there exists a vertex v in D such that (x,v) and (y,v) are arcs of D. For any graph G, G together with sufficiently many isolated vertices is the competition graph of some acyclic digraph. The competition number k(G) of a graph G is defined to be the smallest number of such isolated vertices. In general, it is hard to compute the competition number k(G) for a graph G and to characterize all graphs with given competition number k has been one of the important research problems in the study of competition graphs.

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_X₁ and v_X₂ are adjacent if and only if |X₁ ∩X₂| = 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.

References

[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