Note on the m-step competition numbers of paths and cycles

被引：11

作者：

Zhao, Yongqiang ^{[1
]}

Chang, Gerard J. ^{[2
,3
,4
]}

机构：

[1] Shijiazhuang Coll, Dept Math, Shijiazhuang 050035, Peoples R China

[2] Natl Taiwan Univ, Dept Math, Taipei 10617, Taiwan

[3] Natl Taiwan Univ, Taida Inst Math Sci, Taipei 10617, Taiwan

[4] Taipei Off, Natl Ctr Theoret Sci, Taipei, Taiwan

来源：

DISCRETE APPLIED MATHEMATICS | 2009年 / 157卷 / 08期

关键词：

Competition graph; Competition number; m-step competition graph; m-step competition number; GRAPHS;

D O I：

10.1016/j.dam.2009.01.010

中图分类号：

O29 [应用数学];

学科分类号：

070104 ;

摘要：

Since Cohen introduced the competition graph in 1968, the competition graph has been studied widely and many variations of it have been discussed. In 2000, Cho, Kim and Nam defined and studied the m-step competition graph and computed the 2-step competition numbers of paths and cycles. Recently, Ho gave bounds for the m-step competition numbers of paths and cycles. In this paper we continue to study the m-step competition numbers of paths and cycles, partially improve the results of Ho on the upper bounds of the m-step competition numbers of paths and cycles, and show that a conjecture posed by Ho is not true. (C) 2009 Elsevier B.V. All rights reserved.

引用

页码：1953 / 1958

页数：6

共 8 条

[1] m-Step competition graph of a digraph [J].

Cho, Han Hyuk ;

Kim, Suh-Ryung ;

Nam, Yunsun .

Discrete Applied Mathematics, 2000, 105 (01) :115-127

[2]

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

[3] Connected triangle-free m-step competition graphs [J].

Helleloid, GT .

DISCRETE APPLIED MATHEMATICS, 2005, 145 (03) :376-383

[4] The m-step, same-step, and any-step competition graphs [J].

Ho, W .

DISCRETE APPLIED MATHEMATICS, 2005, 152 (1-3) :159-175

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

Kim, Suh-Ryung ;

Sano, Yoshio .

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

[6]

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

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

[8]

Roberts F. S., 1978, Theory and applications of graphs, P477

← 1 →