THE COMPETITION NUMBERS OF HAMMING GRAPHS WITH DIAMETER AT MOST THREE
1
조회
0
다운로드
0
인용
0
참고문헌
키워드
초록
The competition graph of a digraph D is a graph which has the same vertex set as D and has an edge between 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 it has been one of important research problems in the study of competition graphs. In this paper, we compute the competition numbers of Hamming graphs with diameter at most three.
Abstract
The competition graph of a digraph D is a graph which has the same vertex set as D and has an edge between 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 it has been one of important research problems in the study of competition graphs. In this paper, we compute the competition numbers of Hamming graphs with diameter at most three.
참고문헌 (18)
- H. H. Cho, "The competition number of a graph having exactly one hole", Discrete Math, 303(1), pp.32~41 (2005)
- J. E. Cohen, "Interval Graphs and Food Webs: a finding and a problem", Document 17696-PR, RAND Corporation, ~ (1968)
- J. E. Cohen, "Food Webs and Niche Space" (1978), Princeton University Press
- S.-R. Kim, "The competition number and its variants, Quo vadis, graph theory", Ann. Discrete Math, 55, pp.313~326 (1993)
- S.-R. Kim, "On competition graphs and competition numbers", Commun. Korean Math. Soc, 16(1), pp.1~24 (2001)
- 김서령, "Graphs with one hole and competition number one", 대한수학회지, 42(6), pp.1251~1264 (2005), 대한수학회
- S.-R. Kim, "The competition number of a graph whose holes do not overlap much", Discrete Appl. Math, 158(13), pp.1456~1460 (2010)
- S.-R. Kim, "The competition numbers of Johnson graphs", Discussiones Mathematicae - Graph Theory, 30(3), pp.449~459 (2010), Univ. Zielona Góra
- S.-R. Kim, "Competition numbers of graphs with a small number of triangles", Discrete Appl. Math, 78(1), pp.153~162 (1997)
- S.-R. Kim, "The competition numbers of complete tripartite graphs", Discrete Appl. Math, 156(18), pp.3522~3524 (2008)
- 김석진, "The competition number of a graph with exactly two holes", ARS COMBINATORIA, 95, pp.45~54
- R. J. Opsut, "On the computation of the competition number of a graph", SIAM J. Alge- braic Discrete Methods, 3(4), pp.420~428 (1982)
- "On competition numbers of complete multi- partite graphs with partite sets of equal size" (2008)[URL]
- 박보람, "The competition numbers of complete multipartite graphs and mutually orthogonal Latin squares", DISCRETE MATHEMATICS, 309(23), pp.6464~6469 (2009), ELSEVIER SCIENCE BV
- B. Park, "The competition numbers of ternary Hamming graphs", APPLIED MATHEMATICS LETTERS, 24(9), pp.1608~1613 (2011), PERGAMON-ELSEVIER SCIENCE LTD
- F. S. Roberts, "Food webs, competition graphs, and the boxicity of ecological phase space, Theory and applications of graphs", Lecture Notes in Math, 642, pp.477~490 (1978), Springer
- Y. Sano, "The competition numbers of regular polyhedra", Congr. Numer, 198, pp.211~219 (2009)
- Y.Wu, "Dimension-2 poset competition numbers and dimension-2 poset double competition numbers", Discrete Appl. Math, 158(6), pp.706~717 (2010)