Contractible Edges and Longest Cycles in 3-Connected Graphs

被引：0
|
作者：
Egawa, Yoshimi [1 ]
Nakamura, Shunsuke [2 ]
机构：
[1] Tokyo Univ Sci, Dept Appl Math, 1-3 Kagurazaka,Shinju Ku, Tokyo 1628601, Japan
[2] Natl Inst Technol, Kurume Coll, Dept Liberal Arts Sci & Math, 1-1-1 Komorino, Fukuoka 8308555, Japan
来源：
GRAPHS AND COMBINATORICS | 2023年 / 39卷 / 01期
关键词：
3-Connected graph; Contractible edge; Longest cycle; MAXIMUM NUMBER;
D O I：
10.1007/s00373-022-02609-5
中图分类号：
O1 [数学];
学科分类号：
0701 ; 070101 ;
摘要：
We show that if G is a 3-connected graph of order at least 5, then there exists a longest cycle C of G such that the number of contractible edges of G which are on C is greater than or equal to (|E(C)| + 5) /6.
引用
收藏
页数：16
相关论文
共 50 条
  • [21] Contractible edges in some k-connected graphs
    Yang, Yingqiu
    Sun, Liang
    CZECHOSLOVAK MATHEMATICAL JOURNAL, 2012, 62 (03) : 637 - 644
  • [22] Contractible edges in some k-connected graphs
    Yingqiu Yang
    Liang Sun
    Czechoslovak Mathematical Journal, 2012, 62 : 637 - 644
  • [23] LONGEST CYCLES AND LONGEST CHORDLESS CYCLES IN 2-CONNECTED GRAPHS
    Hu, Yanan
    Li, Chengli
    Liu, Feng
    BULLETIN OF THE AUSTRALIAN MATHEMATICAL SOCIETY, 2025,
  • [24] Contractible edges in 2-connected locally finite graphs
    Chan, Tsz Lung
    ELECTRONIC JOURNAL OF COMBINATORICS, 2015, 22 (02):
  • [25] Contractible Edges in k-Connected Graphs with Some Forbidden Subgraphs
    Yingqiu Yang
    Liang Sun
    Graphs and Combinatorics, 2014, 30 : 1607 - 1614
  • [26] Contractible Edges in k-Connected Graphs with Some Forbidden Subgraphs
    Yang, Yingqiu
    Sun, Liang
    GRAPHS AND COMBINATORICS, 2014, 30 (06) : 1607 - 1614
  • [27] On the number of 4-contractible edges in 4-connected graphs
    Ando, K.
    Egawa, Y.
    Kawarabayashi, K.
    Kriesell, Matthias
    JOURNAL OF COMBINATORIAL THEORY SERIES B, 2009, 99 (01) : 97 - 109
  • [28] Contractible edges of k-connected graphs for k=4, 5
    Qin, Chengfu
    Guo, Xiaofeng
    ARS COMBINATORIA, 2010, 97 : 321 - 332
  • [29] ON LONGEST CYCLES IN ESSENTIALLY 4-CONNECTED PLANAR GRAPHS
    Fabrici, Igor
    Harant, Jochen
    Jendrol', Stanislav
    DISCUSSIONES MATHEMATICAE GRAPH THEORY, 2016, 36 (03) : 565 - 575
  • [30] A note on 3-connected cubic planar graphs
    Lu, Xiaoyun
    DISCRETE MATHEMATICS, 2010, 310 (13-14) : 2054 - 2058
12345