### On degree-sequence characterization and the extremal number of edges for various Hamiltonian properties under fault tolerance

*Shih-Yan Chen, Shin-Shin Kao, Hsun Su*

#### Abstract

Assume that n,δ,k are integers with 0 ≤k
< δ< n. Given a graph G=(V,E) with
|V|=n. The symbol G-F,
F⊆V, denotes the graph with V(G-F)=V-F,
and E(G-F) obtained by E after deleting the
edges with at least one endvertex in F. G
is called

*k-vertex fault traceable*,*k-vertex fault Hamiltonian*, or*k-vertex fault Hamiltonian-connected*if G-F remains traceable, Hamiltonian, and Hamiltonian-connected for all F with 0≤|F| ≤k, respectively. The notations h_{1}(n,δ,k), h_{2}(n,δ,k), and h_{3}(n,δ,k) denote the minimum number of edges required to guarantee an n-vertex graph with minimum degree δ(G) ≥δ to be k-vertex fault traceable, k-vertex fault Hamiltonian, and k-vertex fault Hamiltonian-connected, respectively. In this paper, we establish a theorem which uses the degree sequence of a given graph to characterize the k-vertex fault traceability/hamiltonicity/Hamiltonian-connectivity, respectively. Then we use this theorem to obtain the formulas for h_{i}(n,δ,k) for 1≤i ≤3, which improves and extends the known results for k=0.Full Text: PDF PostScript