The competition numbers of ternary Hamming graphs

被引：9

作者：

Park, Boram ^{[1
]}

Sano, Yoshio ^{[2
]}

机构：

[1] Seoul Natl Univ, Dept Math Educ, Seoul 151742, South Korea

[2] POSTECH, Pohang Math Inst, Pohang 790784, South Korea

来源：

APPLIED MATHEMATICS LETTERS | 2011年 / 24卷 / 09期

关键词：

Competition graph; Competition number; Edge clique cover; Hamming graph;

D O I：

10.1016/j.aml.2011.04.012

中图分类号：

O29 [应用数学];

学科分类号：

070104 ;

摘要：

It is is known to be a hard problem to compute the competition number k(G) of a graph G in general. Park and Sano (in press) [16] gave the exact values of the competition numbers of Hamming graphs H(n, q) if 1 <= n <= 3 or 1 <= q <= 2. In this paper, we give an explicit formula for the competition numbers of ternary Hamming graphs. (C) 2011 Elsevier Ltd. All rights reserved.

引用

页码：1608 / 1613

页数：6

共 17 条

[1]

Cohen J.E., 1968, RAND Corporation Document 17696-PR

[2]

Kim S.-R., 2010, DISCUSS MATH GRAPH T, V30, P449

[3] The competition number of a graph whose holes do not overlap much [J].

Kim, Suh-Ryung ;

Lee, Jung Yeun ;

Sano, Yoshio .

DISCRETE APPLIED MATHEMATICS, 2010, 158 (13) :1456-1460

[4] The competition numbers of complete tripartite graphs [J].

Kim, Suh-Ryung ;

Sano, Yoshio .

DISCRETE APPLIED MATHEMATICS, 2008, 156 (18) :3522-3524

[5]

Kim Suh-Ryung, 1993, Ann. Discrete Math., V55, P313, DOI DOI 10.1016/S0167-5060(08)70396-0

[6] The competition number of a graph with exactly two holes [J].

Li, Bo-Jr ;

Chang, Gerard J. .

JOURNAL OF COMBINATORIAL OPTIMIZATION, 2012, 23 (01) :1-8

[7] The competition number of a graph with exactly h holes, all of which are independent [J].

Li, Bo-Jr ;

Chang, Gerard J. .

DISCRETE APPLIED MATHEMATICS, 2009, 157 (07) :1337-1341

[8] ON THE COMPUTATION OF THE COMPETITION NUMBER OF A GRAPH [J].

OPSUT, RJ .

SIAM JOURNAL ON ALGEBRAIC AND DISCRETE METHODS, 1982, 3 (04) :420-428

[9]

PARK B, J KOREAN MA IN PRESS

[10]

PARK B, 2008, RIMS1644

← 1 2 →