Title of article
Removable matchings and hamiltonian cycles
Author/Authors
Hu، نويسنده , , Zhiquan and Li، نويسنده , , Hao، نويسنده ,
Issue Information
روزنامه با شماره پیاپی سال 2009
Pages
5
From page
1020
To page
1024
Abstract
For a graph G , let σ 2 ( G ) denote the minimum degree sum of two nonadjacent vertices (when G is complete, we let σ 2 ( G ) = ∞ ). In this paper, we show the following two results: (i) Let G be a graph of order n ≥ 4 k + 3 with σ 2 ( G ) ≥ 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 ≅ K 2 + ( K 2 ∪ K n − 4 ) or G ≅ K 2 ¯ + ( K 2 ∪ K n − 4 ) ; (ii) Let G be a graph of order n ≥ 16 k + 1 with σ 2 ( G ) ≥ 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. Examples show that first result is the best possible.
Keywords
pancyclic , Matching , hamiltonian cycle
Journal title
Discrete Mathematics
Serial Year
2009
Journal title
Discrete Mathematics
Record number
1598570
Link To Document