Shih-Yan Chen ; Shin-Shin Kao ; Hsun Su - On degree-sequence characterization and the extremal number of edges for various Hamiltonian properties under fault tolerance

dmtcs:2149 - Discrete Mathematics & Theoretical Computer Science, August 2, 2016, Vol. 17 no. 3 - https://doi.org/10.46298/dmtcs.2149
On degree-sequence characterization and the extremal number of edges for various Hamiltonian properties under fault toleranceArticle

Authors: Shih-Yan Chen 1; Shin-Shin Kao 2; Hsun Su 3

  • 1 Taipei Municipal Bai-Ling Senior High School
  • 2 Department of Applied Mathematics, Chung Yuan Christian University
  • 3 Department of Public Finance and Taxation, Takming University

Assume that $n, \delta ,k$ are integers with $0 \leq k < \delta < n$. Given a graph $G=(V,E)$ with $|V|=n$. The symbol $G-F, F \subseteq 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 <i>$k$-vertex fault traceable</i>, <i>$k$-vertex fault Hamiltonian</i>, or <i>$k$-vertex fault Hamiltonian-connected</i> 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$.


Volume: Vol. 17 no. 3
Section: Graph Theory
Published on: August 2, 2016
Submitted on: March 4, 2015
Keywords: graph size, Hamiltonian, fault-tolerant Hamiltonian, Hamiltonian-connected, degree sequence,[INFO.INFO-DM] Computer Science [cs]/Discrete Mathematics [cs.DM]

Consultation statistics

This page has been seen 337 times.
This article's PDF has been downloaded 616 times.