Coverings of the vertices of a graph by small cycles

被引：1

作者：

Forge, David ^{[1
]}

Kouider, Mekkia ^{[1
]}

机构：

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

来源：

GRAPHS AND COMBINATORICS | 2007年 / 23卷 / 02期

关键词：

vertex covering; cycles; paths;

D O I：

10.1007/s00373-006-0678-8

中图分类号：

O1 [数学];

学科分类号：

0701 ; 070101 ;

摘要：

Given a graph G with n vertices, we call c(k)(G) the minimum number of elementary cycles of length at most k necessary to cover the vertices of G. We bound c(k)(G) from the minimum degree and the order of the graph.

引用

页码：135 / 143

页数：9

共 6 条

[1] BERGE C, 1987, GRAPHES, P400
[2] Dirac G. A., 1952, Proc. Lond. Math. Soc, V2, P69, DOI [10.1112/plms/s3-2.1.69, DOI 10.1112/PLMS/S3-2.1.69]
[3] Enomoto H., 1987, C MATH SOC J BOLYAI, V52, P213
[4] NEIGHBORHOOD UNIONS AND HAMILTON CYCLES
JACKSON, B
[J]. JOURNAL OF GRAPH THEORY, 1991, 15 (04) : 443 - 451
[5] Covering cycles and k-term degree sums
Kouider, M
Long, Z
[J]. COMBINATORICA, 1996, 16 (03) : 407 - 412
[6] Neighborhoods and covering vertices by cycles
Kouider, M
[J]. COMBINATORICA, 2000, 20 (02) : 219 - 226

← 1 →