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 条
  • [1] Number of cycles of small length in a graph
    Barik, Sasmita
    Reddy, Sane Umesh
    AKCE INTERNATIONAL JOURNAL OF GRAPHS AND COMBINATORICS, 2023, 20 (02) : 134 - 147
  • [2] Covering the vertices of a graph with cycles of bounded length
    Bekkai, Siham
    Forge, David
    Kouider, Mekkia
    DISCRETE MATHEMATICS, 2009, 309 (08) : 1963 - 1966
  • [3] An old problem of Erdos: A graph without two cycles of the same length
    Lai, Chunhui
    DISCRETE APPLIED MATHEMATICS, 2023, 337 : 42 - 45
  • [4] Every planar graph without 3-cycles adjacent to 4-cycles and without 6-cycles is (1, 1, 0)-colorable
    Ying Bai
    Xiangwen Li
    Gexin Yu
    Journal of Combinatorial Optimization, 2017, 33 : 1354 - 1364
  • [5] Every planar graph without 3-cycles adjacent to 4-cycles and without 6-cycles is (1,1,0)-colorable
    Bai, Ying
    Li, Xiangwen
    Yu, Gexin
    JOURNAL OF COMBINATORIAL OPTIMIZATION, 2017, 33 (04) : 1354 - 1364
  • [6] Short cycles in repeated exponentiation modulo a prime
    Lev Glebsky
    Igor E. Shparlinski
    Designs, Codes and Cryptography, 2010, 56 : 35 - 42
  • [7] Short cycles in repeated exponentiation modulo a prime
    Glebsky, Lev
    Shparlinski, Igor E.
    DESIGNS CODES AND CRYPTOGRAPHY, 2010, 56 (01) : 35 - 42
  • [8] Partition of a graph into cycles and degenerated cycles
    Enomoto, H
    Li, H
    DISCRETE MATHEMATICS, 2004, 276 (1-3) : 177 - 181
  • [9] On decomposing Kn-1 into cycles of a fixed odd length
    Sajna, M
    DISCRETE MATHEMATICS, 2002, 244 (1-3) : 435 - 444
  • [10] On the (3,1)-choosability of planar graphs without adjacent cycles of length 5, 6, 7
    Wang, Yue
    Wu, Jianliang
    Yang, Donglei
    DISCRETE MATHEMATICS, 2019, 342 (06) : 1782 - 1791
12345