Abstract
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 \(\left( \left| E(C)\right| +5\right) /6\).
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
Aldred, R.E.L., Hemminger, R.L., Ota, K.: The 3-connected graphs having a longest cycle containing only three contractible edges. J. Graph Theory 17, 361–371 (1993)
Dean, N., Hemminger, R.L., Ota, K.: Longest cycles in 3-connected graphs contain three contractible edges. J. Graph Theory 12, 17–21 (1989)
Diestel, R.: “Graph Theory’’ graduate texts in mathematics, 5th edn., p. 173. Springer, Berlin (2017)
Ellingham, M.N., Hemminger, R.L., Johnson, K.E.: Contractible edges in longest cycles in nonhamiltonian graphs. Discrete Math. 133, 89–98 (1994)
Fujita, K.: Longest cycles \(C\) in a 3-connected graph \(G\) such that \(C\) contains precisely four contractible edges of \(G\). Math. Japon. 43, 99–116 (1996)
Fujita, K.: Contractible edges on hamiltonian cycles of 3-connected graphs, Ph. D. Dissertation, Science University of Tokyo (2001)
Fujita, K.: Maximum number of contractible edges on hamiltonian cycles of a 3-connected graph. Graphs Combin. 18, 447–478 (2002)
Fujita, K.: Maximum number of contractible edges on longest cycles of a 3-connected graph. Ars Combin. 74, 129–149 (2005)
Fujita, K.: Lower bound on the maximum number of contractible edges on longest cycles of a 3-connected graph. Far East J. Appl. Math. 22, 55–86 (2006)
Fujita, K., Kotani, K.: Classification of hamiltonian cycles of a 3-connected graph which contain five contractible edges. SUT J. Math. 36, 287–350 (2000)
Ota, K.: Non-critical subgraphs in \(k\)-connected graphs, Ph. D. Dissertation, University of Tokyo (1989)
Tutte, W.T.: A theory of 3-connected graphs. Indag. Math. 23, 441–445 (1961)
Funding
No funding
Author information
Authors and Affiliations
Corresponding author
Ethics declarations
Conflict of interest
We declare that there is no conflict of interest between the authors.
Additional information
Publisher's Note
Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.
Rights and permissions
Springer Nature or its licensor (e.g. a society or other partner) holds exclusive rights to this article under a publishing agreement with the author(s) or other rightsholder(s); author self-archiving of the accepted manuscript version of this article is solely governed by the terms of such publishing agreement and applicable law.
About this article
Cite this article
Egawa, Y., Nakamura, S. Contractible Edges and Longest Cycles in 3-Connected Graphs. Graphs and Combinatorics 39, 14 (2023). https://doi.org/10.1007/s00373-022-02609-5
Received:
Revised:
Accepted:
Published:
DOI: https://doi.org/10.1007/s00373-022-02609-5