A note on circumferences in k-connected graphs with given independence number

被引：0

作者：

Cui, Qing ^{[1
]}

Zhong, Lingping ^{[1
]}

机构：

[1] Nanjing Univ Aeronaut & Astronaut, Dept Math, Nanjing 210016, Peoples R China

来源：

ARS COMBINATORIA | 2013年 / 111卷

基金：

中国国家自然科学基金;

关键词：

Circumference; Connectivity; Independence number; LONGEST CYCLES;

D O I：

暂无

中图分类号：

O1 [数学];

学科分类号：

0701 ; 070101 ;

摘要：

Fouquet and Jolivet conjectured that if G is a k-connected n-vertex graph with independence number alpha >= k >= 2, then G has circumference at least k(n+alpha-k)/alpha. This conjecture was recently proved by O, West and Wu. In this note, we consider the set of k-connected n-vertex graphs with independence number alpha > k >= 2 and circumference exactly k(n+alpha-k)/alpha. We show that all of these graphs have a similar structure.

引用

页码：315 / 322

页数：8

共 8 条

[1] Circumferences of k-Connected Graphs Involving Independence Numbers [J].

Chen, Guantao ;

Hu, Zhiquan ;

Wu, Yaping .

JOURNAL OF GRAPH THEORY, 2011, 68 (01) :55-76

[2]

Chvatal V., 1972, Discrete Math, V2, P111, DOI DOI 10.1016/0012-365X(72)90079-9

[3]

Fouquet J.L., 1976, Problemes combinatoires et theorie des graphes

[4]

Fournier I., 1982, THESIS U PARIX 11

[5]

Fournier I., 1985, CYCLES GRAPHS, P201

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

KOUIDER, M .

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

[7] Longest Cycles in 3-connected Graphs with Given Independence Number [J].

Manoussakis, Y. .

GRAPHS AND COMBINATORICS, 2009, 25 (03) :377-384

[8] Longest cycles in k-connected graphs with given independence number [J].

Suil, O. ;

West, Douglas B. ;

Wu, Hehui .

JOURNAL OF COMBINATORIAL THEORY SERIES B, 2011, 101 (06) :480-485

← 1 →