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 条
  • [31] Decomposition of hypercube graphs into paths and cycles of length four
    Saranya, D.
    Jeevadoss, S.
    AKCE INTERNATIONAL JOURNAL OF GRAPHS AND COMBINATORICS, 2022, 19 (02) : 141 - 145
  • [32] Decomposition of Product Graphs into Paths and Cycles of Length Four
    Jeevadoss, S.
    Muthusamy, A.
    GRAPHS AND COMBINATORICS, 2016, 32 (01) : 199 - 223
  • [33] Decomposition of Product Graphs into Paths and Cycles of Length Four
    S. Jeevadoss
    A. Muthusamy
    Graphs and Combinatorics, 2016, 32 : 199 - 223
  • [34] Complementary cycles of any length in regular bipartite tournaments
    Bessy, Stephane
    Thiebaut, Jocelyn
    JOURNAL OF GRAPH THEORY, 2023, 103 (02) : 186 - 211
  • [35] Maximum bisections of graphs without cycles of length 4
    Rao, Mengjiao
    Hou, Jianfeng
    Zeng, Qinghou
    DISCRETE MATHEMATICS, 2022, 345 (08)
  • [36] Planar graphs with cycles of length neither 4 nor 7 are (3,0,0)-colorable
    Li, Huihui
    Xu, Jinghan
    Wang, Yingqian
    DISCRETE MATHEMATICS, 2014, 327 : 29 - 35
  • [37] (1,0,0)-colorability of planar graphs without cycles of length 4, 5 or 9
    Wang, Yingqian
    Yang, Yaochou
    DISCRETE MATHEMATICS, 2014, 326 : 44 - 49
  • [38] Injective Δ+2 Coloring of Planar Graph Without Short Cycles
    Chen, Ying
    Tao, Lan
    Zhang, Li
    ACTA MATHEMATICAE APPLICATAE SINICA-ENGLISH SERIES, 2023, 39 (04): : 1009 - 1031
  • [39] Hamilton cycles in graph bundles over a cycle with tree as a fibre
    Pisanski, Tomaz
    Zerovnik, Janez
    DISCRETE MATHEMATICS, 2009, 309 (17) : 5432 - 5436
  • [40] The Existence of Even Cycles with Specific Lengths in Wenger's Graph
    Jia-yu Shao~1 Chang-xiang He~2 Hai-ying Shan~1 ~1Department of Mathematics
    Acta Mathematicae Applicatae Sinica, 2008, (02) : 281 - 288
12345