PL EN

Preferencje
Język
Widoczny [Schowaj] Abstrakt
Liczba wyników
Czasopismo

## Discussiones Mathematicae Graph Theory

2010 | 30 | 3 | 449-459
Tytuł artykułu

### The competition numbers of Johnson graphs

Autorzy
Treść / Zawartość
Warianty tytułu
Języki publikacji
EN
Abstrakty
EN
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 ∈ \binom{[n]}{d}$, where $\binom{[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).
Słowa kluczowe
EN
Kategorie tematyczne
Wydawca
Czasopismo
Rocznik
Tom
Numer
Strony
449-459
Opis fizyczny
Daty
wydano
2010
otrzymano
2009-04-14
poprawiono
2009-10-09
zaakceptowano
2009-10-10
Twórcy
autor
• Department of Mathematics Education, Seoul National University, Seoul 151-742, Korea
autor
• Department of Mathematics Education, Seoul National University, Seoul 151-742, Korea
autor
• Research Institute for Mathematical Sciences, Kyoto University, Kyoto 606-8502, Japan
Bibliografia
• [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.
Typ dokumentu
Bibliografia
Identyfikatory