Contractible Edges and Longest Cycles in 3-Connected Graphs

被引：0
作者：
Yoshimi Egawa
Shunsuke Nakamura
机构：
[1] Tokyo University of Science,Department of Applied Mathematics
[2] National Institute of Technology,Department of Liberal Arts (Sciences and Mathematics)
[3] Kurume College,undefined
来源：
Graphs and Combinatorics | 2023年 / 39卷
关键词：
3-Connected graph; Contractible edge; Longest cycle;
D O I：
暂无
中图分类号：
学科分类号：
摘要：
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\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\left( \left| E(C)\right| +5\right) /6$$\end{document}.
引用
收藏
相关论文
共 16 条
  • [1] Aldred REL(1993)The 3-connected graphs having a longest cycle containing only three contractible edges J. Graph Theory 17 361-371
  • [2] Hemminger RL(1989)Longest cycles in 3-connected graphs contain three contractible edges J. Graph Theory 12 17-21
  • [3] Ota K(1994)Contractible edges in longest cycles in nonhamiltonian graphs Discrete Math. 133 89-98
  • [4] Dean N(1996)Longest cycles Math. Japon. 43 99-116
  • [5] Hemminger RL(2002) in a 3-connected graph Graphs Combin. 18 447-478
  • [6] Ota K(2005) such that Ars Combin. 74 129-149
  • [7] Ellingham MN(2006) contains precisely four contractible edges of Far East J. Appl. Math. 22 55-86
  • [8] Hemminger RL(2000)Maximum number of contractible edges on hamiltonian cycles of a 3-connected graph SUT J. Math. 36 287-350
  • [9] Johnson KE(1961)Maximum number of contractible edges on longest cycles of a 3-connected graph Indag. Math. 23 441-445
  • [10] Fujita K(undefined)Lower bound on the maximum number of contractible edges on longest cycles of a 3-connected graph undefined undefined undefined-undefined
12