• 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