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

Abstract

Assume that $n, \delta ,k$ are integers with $0 \leq k $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 \leq |F| \leq k$, respectively. The notations $h_1(n, \delta ,k)$, $h_2(n, \delta ,k)$, and $h_3(n, \delta ,k)$ denote the minimum number of edges required to guarantee an $n$-vertex graph with minimum degree $\delta (G) \geq \delta$ 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, \delta ,k)$ for $1 \leq i \leq 3$, which improves and extends the known results for $k=0$.

Keywords

• graph size
• hamiltonian
• fault-tolerant hamiltonian
• hamiltonian-connected
• degree sequence
• [info.info-dm] computer science [cs]/discrete mathematics [cs.dm]