Removable matchings and Hamiltonian cycles
type: Item
instance of: scholarly article
title: Removable matchings and Hamiltonian cycles
zbMATH Open document ID: 1179.05087
author: Hao Li
author: Zhiquan Hu
published in: Discrete Mathematics
publication date: 2009-04-09T00:00:00Z
review text: The authors show the following two results: {\parindent=5mm \begin{itemize}\item[1)]Let \(G\) be a graph of order \(n\geq 4k+3\) with \(\sigma_2 (G)\geq n\) and let \(F\) be a matching of size \(k\) in \(G\) such that \(G-F\) is 2-connected. Then \(G-F\) is hamiltonian or \(G\cong K_2 +(K_2\cup K_{n-4})\) or \(G\cong \bar{K_2} +(K_2\cup K_{n-4})\), where \(\sigma_2(G)\) denotes the minimum degree sum of two nonadjacent vertices. \item[2)]Let \(G\) be a graph of order \(n\geq 16k+1\) with \(\sigma_2(G)\geq n\) and let \(F\) be a set of \(k\) edges of \(G\) such that \(G-F\) is hamiltonian. Then \(G-F\) is either pancyclic or bipartite. \end{itemize}}
reviewed by: Dara Moazzami
Mathematics Subject Classification ID: 05C70
Mathematics Subject Classification ID: 05C45
zbMATH DE Number: 5542419
zbMATH Keywords: matching
zbMATH Keywords: Hamiltonian cycle
zbMATH Keywords: pancyclic
MaRDI profile type: Publication
full work available at URL: j.disc.2007.11.053
OpenAlex ID: W2014529345
cites work: Proof of a conjecture of Haeggkvist on cycles and independent edges
cites work: Q4087221
cites work: A method in graph theory
cites work: Q5628163
cites work: Note on Hamilton Circuits
cites work: A cycle structure theorem for Hamiltonian graphs
DOI: 10.1016/J.DISC.2007.11.053
Recommended article: On removable circuits in graphs and matroids
Recommended article: Q4627526
Recommended article: Removable cycles in non-bipartite graphs
Recommended article: Removable Cycles in Planar Graphs
Recommended article: Hamiltonian cycles and paths through matchings
Recommended article: Q5199104
Recommended article: HAMILTONIAN CYCLES THROUGH MATCHINGS
Recommended article: Q3576703
Recommended article: On removable even circuits in graphs
Recommended article: On removable and non-separating even cycles in graphs
description: scientific article; zbMATH DE number 5542419