A characterization of the graphs with high degree sum that are not covered by three cycles

被引：0

作者：

Chiba, Shuya ^{[1
]}

Tsugaki, Masao ^{[2
]}

机构：

[1] Kumamoto Univ, Dept Math & Engn, 2-39-1 Kurokami, Kumamoto 8608555, Japan

[2] Chinese Acad Sci, Inst Math & Syst Sci, Beijing, Peoples R China

来源：

ARS COMBINATORIA | 2016年 / 128卷

关键词：

Degree sum; Cycle cover;

D O I：

暂无

中图分类号：

O1 [数学];

学科分类号：

0701 ; 070101 ;

摘要：

Let G be a graph of order n. In [A. Saito, Degree sums and graphs that are not covered by two cycles, J. Graph Theory 32 (1999), 51-61.], Saito characterized the graphs with sigma(3)(G) >= n - 1 that are not covered by two cycles. In this paper, we characterize the graphs with sigma(4) (G) >= n - 1 that are not covered by three cycles. Moreover, to prove our main theorem, we show several new results which are useful in the study of this area.

引用

页码：127 / 163

页数：37

共 11 条

[1] Cycles in partially square graphs [J].

Ainouche, A ;

Kouider, M .

GRAPHS AND COMBINATORICS, 2001, 17 (01) :1-9

[2]

[Anonymous], 1952, Proceedings of the London Mathematical Society, DOI [10.1112/plms/s3-2.1.69, DOI 10.1112/PLMS/S3-2.1.69]

[3]

[Anonymous], 1980, NATURAL SCI REPORT

[4]

Bondy J., 1995, Handbook of Combinatorics, V1, P5

[5]

ENOMOTO H, 1988, COLLOQ MATH SOC J B, V52, P213

[6]

Fraisse P., 1989, RECENT STUDIES GRAPH, P114

[7] Covering cycles and k-term degree sums [J].

Kouider, M ;

Long, Z .

COMBINATORICA, 1996, 16 (03) :407-412

[8] CYCLES IN GRAPHS WITH PRESCRIBED STABILITY NUMBER AND CONNECTIVITY [J].

KOUIDER, M .

JOURNAL OF COMBINATORIAL THEORY SERIES B, 1994, 60 (02) :315-318

[9]

Ore O., 1960, Amer. Math. Monthly, V67, P55, DOI [10.2307/2308928, DOI 10.2307/2308928]

[10]

Saito A, 1999, J GRAPH THEOR, V32, P51, DOI 10.1002/(SICI)1097-0118(199909)32:1<51::AID-JGT5>3.3.CO

← 1 2 →