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 条

[41] A Connected Graph with Non-concurrent Longest Cycles
Junejo, Abdul Hameed
Kalhoro, Abdul Naem
Soomro, Inayatullah
Ahmed, Israr
Muhammad, Raza
Jokhio, Imdad Ali
Chohan, Rozina
INTERNATIONAL JOURNAL OF COMPUTER SCIENCE AND NETWORK SECURITY, 2019, 19 (05): : 78 - 80
[42] LONGEST CYCLES IN 2-CONNECTEDCLAW-FREE GRAPHS
GAO Taiping (Department of Mathematics
Systems Science and Mathematical Sciences, 1997, (02) : 176 - 182
[43] LARGE DEGREE VERTICES IN LONGEST CYCLES OF GRAPHS, I
Li, Binlong
Xiong, Liming
Yin, Jun
DISCUSSIONES MATHEMATICAE GRAPH THEORY, 2016, 36 (02) : 363 - 382
[44] Large degree vertices in longest cycles of graphs, II
Li, Binlong
Xiong, Liming
Yin, Jun
ELECTRONIC JOURNAL OF GRAPH THEORY AND APPLICATIONS, 2019, 7 (02) : 277 - 299
[45] Edges incident with a vertex of degree greater than four and the number of contractible edges in a 4-connected graph
Egawa, Yoshimi
Nakamura, Shunsuke
DISCRETE APPLIED MATHEMATICS, 2024, 355 : 142 - 158
[46] DISTRIBUTION OF CONTRACTIBLE EDGES AND THE STRUCTURE OF NONCONTRACTIBLE EDGES HAVING ENDVERTICES WITH LARGE DEGREE IN A 4-CONNECTED GRAPH
Nakamura, Shunsuke
DISCUSSIONES MATHEMATICAE GRAPH THEORY, 2021, 41 (04) : 1051 - 1066
[47] Contractible edges in a 4-connected graph with vertices of degree greater than four
Ando, Kiyoshi
Egawa, Yoshimi
GRAPHS AND COMBINATORICS, 2007, 23 (Suppl 1) : 99 - 115
[48] A connected graph with set of empty intersection of all Longest Cycles
Junejo, Abdul Hameed
Soomro, Inayatullah
Ahmed, Israr
Kalhoro, Abdul Naeem
Muhammad, Raza
Jokhio, Imdad
Chohan, Rozina
Jumani, A. D.
INTERNATIONAL JOURNAL OF COMPUTER SCIENCE AND NETWORK SECURITY, 2019, 19 (05): : 87 - 89
[49] Contractible Edges in a 4-Connected Graph with Vertices of Degree Greater Than Four
Kiyoshi Ando
Yoshimi Egawa
Graphs and Combinatorics, 2007, 23 : 99 - 115
[50] Degree conditions and relative length of longest paths and cycles in graphs
Wu, Yueyu
DISCRETE MATHEMATICS, 2023, 346 (08)

← 1 2 3 4 5 →