Dominating cycles in triangle-free graphs

被引：0

作者：

Ozeki, Kenta ^{[1
]}

Yamashita, Tomoki ^{[2
]}

机构：

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

[2] Asahi Univ, Dept Math, Sch Dent, Gifu 5010296, Japan

来源：

ARS COMBINATORIA | 2011年 / 98卷

关键词：

D O I：

暂无

中图分类号：

O1 [数学];

学科分类号：

0701 ; 070101 ;

摘要：

A cycle C in a graph G is said to be dominating if E(G - C) = empty set. Enomoto et al. showed that if G is a 2-connected triangle-free graph with alpha(G) <= 2 kappa(G) - 2, then every longest cycle is dominating. But it is unknown whether the condition on the independence number is sharp. In this paper, we show that if G is a 2-connected triangle-free graph with alpha(G) <= 2 kappa(G) - 1, then G has a longest cycle which is dominating. This condition is best possible.

引用

页码：173 / 182

页数：10

共 6 条

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

AUNG, M .

JOURNAL OF COMBINATORIAL THEORY SERIES B, 1989, 47 (02) :171-186

[2]

Bondy J.A, 1980, 8016 CORR U WAT DEP

[3]

BROERSMA H, DEGREE CONDITI UNPUB

[4]

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

[5] Long cycles in triangle-free graphs with prescribed independence number and connectivity [J].

Enomoto, H ;

Kaneko, A ;

Saito, A ;

Wei, B .

JOURNAL OF COMBINATORIAL THEORY SERIES B, 2004, 91 (01) :43-55

[6]

West D. B., 2006, INTRO GRAPH THEORY

← 1 →