Covering the vertices of a graph with cycles of bounded length

被引：1

作者：

Bekkai, Siham ^{[1
]}

Forge, David ^{[2
]}

Kouider, Mekkia ^{[2
]}

机构：

[1] USTHB, Fac Math, LAID3, El Alia Bab Ezzouar 16111, Alger, Algeria

[2] Univ Paris 11, LRI, UMR 8623, F-91405 Orsay, France

来源：

DISCRETE MATHEMATICS | 2009年 / 309卷 / 08期

关键词：

Cycle; Vertex covering; Independence number; DISJOINT CYCLES; NUMBER;

D O I：

10.1016/j.disc.2008.03.031

中图分类号：

O1 [数学];

学科分类号：

0701 ; 070101 ;

摘要：

Let c(k)(G) be the minimum number of elementary cycles of length at most k necessary to cover the vertices of a given graph G. In this work, we bound c(k)(G) by a function of the order of G and its independence number. (C) 2008 Elsevier B.V. All rights reserved.

引用

页码：1963 / 1966

页数：4

共 10 条

[1] Bondy J. A., 1976, Graduate Texts in Mathematics, V290
[2] BONDY JA, 1993, HDB COMBINATORICS
[3] Corradi K., 1963, ACTA MATH ACAD SCI H, V14, P423
[4] Covering vertices of a graph by k disjoint cycles
Egawa, Y
Hagita, M
Kawarabayashi, K
Wang, H
[J]. DISCRETE MATHEMATICS, 2003, 270 (1-3) : 115 - 125
[5] On the existence of disjoint cycles in a graph
Enomoto, H
[J]. COMBINATORICA, 1998, 18 (04) : 487 - 492
[6] Coverings of the vertices of a graph by small cycles
Forge, David
Kouider, Mekkia
[J]. GRAPHS AND COMBINATORICS, 2007, 23 (02) : 135 - 143
[7] Covering cycles and k-term degree sums
Kouider, M
Long, Z
[J]. COMBINATORICA, 1996, 16 (03) : 407 - 412
[8] CYCLES IN GRAPHS WITH PRESCRIBED STABILITY NUMBER AND CONNECTIVITY
KOUIDER, M
[J]. JOURNAL OF COMBINATORIAL THEORY SERIES B, 1994, 60 (02) : 315 - 318
[9] LESNIAK L, 1995, JCMCC, V17, P55
[10] On the maximum number of independent cycles in a graph
Wang, H
[J]. DISCRETE MATHEMATICS, 1999, 205 (1-3) : 183 - 190

← 1 →