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 条
  • [41] The existence of even cycles with specific lengths in Wenger’s graph
    Jia-yu Shao
    Chang-xiang He
    Hai-ying Shan
    Acta Mathematicae Applicatae Sinica, English Series, 2008, 24 : 281 - 288
  • [42] Injective Δ+2 Coloring of Planar Graph Without Short Cycles
    Ying Chen
    Lan Tao
    Li Zhang
    Acta Mathematicae Applicatae Sinica, English Series, 2023, 39 : 1009 - 1031
  • [43] The existence of even cycles with specific lengths in Wenger's graph
    Shao, Jia-yu
    He, Chang-xiang
    Shan, Hai-ying
    ACTA MATHEMATICAE APPLICATAE SINICA-ENGLISH SERIES, 2008, 24 (02): : 281 - 288
  • [44] Monotonic Star Decomposition of Jump Graph of Cycles and Even Decomposition of Jump Graph of Complete Bipartite Graphs
    Jenisha, M.
    Devi, P. Chithra
    SOUTHEAST ASIAN BULLETIN OF MATHEMATICS, 2024, 48 (03) : 367 - 374
  • [45] Maximum bisections of graphs without cycles of length four and five
    Wu, Shufei
    Zhong, Yuanyuan
    DISCRETE APPLIED MATHEMATICS, 2025, 360 : 209 - 220
  • [46] DECOMPOSITION OF COMPLETE TRIPARTITE GRAPHS INTO CYCLES AND PATHS OF LENGTH THREE
    Priyadarsini, Shanmugasundaram
    Muthusamy, Appu
    CONTRIBUTIONS TO DISCRETE MATHEMATICS, 2020, 15 (03) : 117 - 129
  • [47] Cycle decompositions III: Complete graphs and fixed length cycles
    Sajna, M
    JOURNAL OF COMBINATORIAL DESIGNS, 2002, 10 (01) : 27 - 78
  • [48] Decomposing Various Graphs into Short Even-Length Cycles
    Daniel Horsley
    Annals of Combinatorics, 2012, 16 : 571 - 589
  • [49] Decomposing Various Graphs into Short Even-Length Cycles
    Horsley, Daniel
    ANNALS OF COMBINATORICS, 2012, 16 (03) : 571 - 589
  • [50] Every planar graph without 4-cycles and 6-cycles is (2,9)-colorable
    Ma, Jianqing
    Huang, Mingfang
    Zhang, Xiaoxia
    ITALIAN JOURNAL OF PURE AND APPLIED MATHEMATICS, 2023, (48): : 659 - 670
12345