Discrete Mathematics & Theoretical Computer Science, Vol 17, No 3 (2016)

Font Size:  Small  Medium  Large

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


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 h1(n,δ,k), h2(n,δ,k), and h3(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 hi(n,δ,k) for 1≤i ≤3, which improves and extends the known results for k=0.

Full Text: PDF PostScript