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 条
  • [31] A Survey on Contractible Edges in Graphs of a Prescribed Vertex Connectivity
    Matthias Kriesell
    Graphs and Combinatorics, 2002, 18 : 1 - 30
  • [32] Edges not contained in triangles and the distribution of contractible edges in a 4-connected graph
    Ando, Kiyoshi
    Egawa, Yoshimi
    DISCRETE MATHEMATICS, 2008, 308 (16) : 3449 - 3460
  • [33] Edges not contained in triangles and the number of contractible edges in a 4-connected graph
    Ando, Kiyoshi
    Egawa, Yoshimi
    DISCRETE MATHEMATICS, 2008, 308 (23) : 5463 - 5472
  • [34] Contractible edges and liftable vertices in a 4-connected graph
    Ando, Kiyoshi
    DISCRETE MATHEMATICS, 2022, 345 (02)
  • [35] Destroying longest cycles in graphs and digraphs
    van Aardt, Susan A.
    Burger, Alewyn P.
    Dunbar, Jean E.
    Frick, Marietjie
    Llano, Bernardo
    Thomassen, Carsten
    Zuazua, Rita
    DISCRETE APPLIED MATHEMATICS, 2015, 186 : 251 - 259
  • [36] REGULAR GRAPHS WITH FEW LONGEST CYCLES
    Zamfirescu, Carol T.
    SIAM JOURNAL ON DISCRETE MATHEMATICS, 2022, 36 (01) : 755 - 776
  • [37] Structure of edges in a 4-connected graph not contained in triangles and the number of contractible edges
    Egawa, Yoshimi
    Kotani, Keiko
    Nakamura, Shunsuke
    AKCE INTERNATIONAL JOURNAL OF GRAPHS AND COMBINATORICS, 2018, 15 (02) : 202 - 210
  • [38] Lower Bound on the Number of Contractible Edges in a 4-Connected Graph with Edges Not Contained in Triangles
    Egawa, Yoshimi
    Kotani, Keiko
    Nakamura, Shunsuke
    GRAPHS AND COMBINATORICS, 2018, 34 (05) : 965 - 987
  • [39] Lower Bound on the Number of Contractible Edges in a 4-Connected Graph with Edges Not Contained in Triangles
    Yoshimi Egawa
    Keiko Kotani
    Shunsuke Nakamura
    Graphs and Combinatorics, 2018, 34 : 965 - 987
  • [40] THE NUMBER OF CONTRACTIBLE EDGES IN A 4-CONNECTED GRAPH HAVING A SMALL NUMBER OF EDGES NOT CONTAINED IN TRIANGLES
    Kotani, Keiko
    Nakamura, Shunsuke
    ADVANCES AND APPLICATIONS IN DISCRETE MATHEMATICS, 2015, 15 (02): : 153 - 166
12345