Spectral Conditions for Graphs to be k-Hamiltonian or k-Path-Coverable

Abstract

A graph G is k-Hamiltonian if for all X ⊂ V (G) with |X| ≤ k, the subgraph induced by V (G) \ X is Hamiltonian. A graph G is k-path-coverable if V (G) can be covered by k or fewer vertex disjoint paths. In this paper, by making use of the vertex degree sequence and an appropriate closure concept (due to Bondy and Chvátal), we present sufficient spectral conditions of a connected graph with fixed minimum degree and large order to be k-Hamiltonian or k-path-coverable.

Keywords

• spectral radius
• minimum degree
• k-hamiltonian
• k-path-coverable
• 05c50
• 05c12