Geodesic
The competition numbers of Johnson graphs
Discussiones Mathematicae. Graph Theory, Tome 30 (2010) no. 3, pp. 449-459.

Voir la notice de l'article provenant de la source Library of Science

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.
Keywords: competition graph, competition number, edge clique cover, Johnson graph 
@article{DMGT_2010_30_3_a7,
     author = {Kim, Suh-Ryung and Park, Boram and Sano, Yoshio},
     title = {The competition numbers of {Johnson} graphs},
     journal = {Discussiones Mathematicae. Graph Theory},
     pages = {449--459},
     publisher = {mathdoc},
     volume = {30},
     number = {3},
     year = {2010},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/DMGT_2010_30_3_a7/}
}
TY  - JOUR
AU  - Kim, Suh-Ryung
AU  - Park, Boram
AU  - Sano, Yoshio
TI  - The competition numbers of Johnson graphs
JO  - Discussiones Mathematicae. Graph Theory
PY  - 2010
SP  - 449
EP  - 459
VL  - 30
IS  - 3
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/DMGT_2010_30_3_a7/
LA  - en
ID  - DMGT_2010_30_3_a7
ER  - 
%0 Journal Article
%A Kim, Suh-Ryung
%A Park, Boram
%A Sano, Yoshio
%T The competition numbers of Johnson graphs
%J Discussiones Mathematicae. Graph Theory
%D 2010
%P 449-459
%V 30
%N 3
%I mathdoc
%U http://geodesic.mathdoc.fr/item/DMGT_2010_30_3_a7/
%G en
%F DMGT_2010_30_3_a7
Kim, Suh-Ryung; Park, Boram; Sano, Yoshio. The competition numbers of Johnson graphs. Discussiones Mathematicae. Graph Theory, Tome 30 (2010) no. 3, pp. 449-459. http://geodesic.mathdoc.fr/item/DMGT_2010_30_3_a7/

[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.