Long cycles in triangle-free graphs with prescribed independence number and connectivity

被引：7

作者：

Enomoto, H

Kaneko, A

Saito, A

Wei, B

机构：

[1] Keio Univ, Dept Math, Kohoku Ku, Yokohama, Kanagawa 2238522, Japan

[2] Kogakuin Univ, Dept Elect Engn, Shinjuku Ku, Tokyo 1638677, Japan

[3] Nihon Univ, Dept Math Appl, Setagaya Ku, Tokyo 1568550, Japan

[4] Acad Sinica, Inst Syst Sci, Beijing 100080, Peoples R China

来源：

JOURNAL OF COMBINATORIAL THEORY SERIES B | 2004年 / 91卷 / 01期

基金：

中国国家自然科学基金;

关键词：

longest cycle; triangle-free graph; independence number; connectivity;

D O I：

10.1016/j.jctb.2003.05.002

中图分类号：

O1 [数学];

学科分类号：

0701 ; 070101 ;

摘要：

The Chvatal-Erdos theorem says that a 2-connected graph with alpha(G) less than or equal to kappa(G) is hamiltonian. We extend this theorem for triangle-free graphs. We prove that if G is a 2-connected triangle-free graph of order n with alpha(G) less than or equal to 2kappa(G) - 2, then every longest cycle in G is dominating, and G has a cycle of length at least min{n - alpha(G) + kappa(G), n}. (C) 2003 Elsevier Inc. All rights reserved.

引用

页码：43 / 55

页数：13

共 6 条

[1] LONGEST CYCLES IN TRIANGLE-FREE GRAPHS [J].