Cycles of length 1 modulo 3 in graph

被引：0

作者：

Lu, M ^{[1
]}

Yu, ZG ^{[1
]}

机构：

[1] Tsing Hua Univ, Dept Math Sci, Beijing 100084, Peoples R China

来源：

DISCRETE APPLIED MATHEMATICS | 2001年 / 113卷 / 2-3期

关键词：

cycle; modulo; chord;

D O I：

暂无

中图分类号：

O29 [应用数学];

学科分类号：

070104 ;

摘要：

We prove a conjecture of Saito that if a graph G with delta greater than or equal to 3 has no cycle of length 1 (mod 3), then G has an induced subgraph which is isomorphic to the Petersen graph. The above result strengthened the result by Dean et al. that every 2-connected graph with delta greater than or equal to 3 has a (1 mod 3)-cycle if G is not isomorphic to the Petersen graph. (C) 2001 Elsevier Science B.V. All rights reserved.

引用

页码：329 / 336

页数：8

共 50 条

[11] Relative length of longest paths and cycles in 3-connected graphs
Li, R
Saito, A
Schelp, RH
JOURNAL OF GRAPH THEORY, 2001, 37 (03) : 137 - 156
[12] On the length of longest chordless cycles
Van Nuffelen C.
Van Rompay K.
4OR, 2005, 3 (2) : 133 - 138
[13] Decomposition of the complete bipartite graph with a 1-factor removed into cycles and stars
Lee, Hung-Chih
Lin, Jenq-Jong
DISCRETE MATHEMATICS, 2013, 313 (20) : 2354 - 2358
[14] On the maximum number of cycles in a Hamiltonian graph
Rautenbach, D
Stella, I
DISCRETE MATHEMATICS, 2005, 304 (1-3) : 101 - 107
[15] The confirmation of a conjecture on disjoint cycles in a graph
Ma, Fuhong
Yan, Jin
DISCRETE MATHEMATICS, 2018, 341 (10) : 2903 - 2911
[16] On the linear 2-arboricity of planar graph without normally adjacent 3-cycles and 4-cycles
Wang, Yiqiao
INTERNATIONAL JOURNAL OF COMPUTER MATHEMATICS, 2017, 94 (05) : 981 - 988
[17] Covering vertices of a graph by k disjoint cycles
Egawa, Y
Hagita, M
Kawarabayashi, K
Wang, H
DISCRETE MATHEMATICS, 2003, 270 (1-3) : 115 - 125
[18] Vertex-disjoint chorded cycles in a graph
Qiao, Shengning
Zhang, Shenggui
OPERATIONS RESEARCH LETTERS, 2010, 38 (06) : 564 - 566
[19] A look at cycles containing specified elements of a graph
Gould, Ronald J.
DISCRETE MATHEMATICS, 2009, 309 (21) : 6299 - 6311
[20] The strong clique index of a graph with forbidden cycles
Cho, Eun-Kyung
Choi, Ilkyoo
Kim, Ringi
Park, Boram
JOURNAL OF GRAPH THEORY, 2021, 98 (02) : 326 - 341

← 1 2 3 4 5 →