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 < \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 $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$.
Type de document :
Article dans une revue
Discrete Mathematics and Theoretical Computer Science, DMTCS, 2016, Vol. 17 no. 3 (3), pp.307-314
Liste complète des métadonnées

Littérature citée [13 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/hal-01352843
Contributeur : Coordination Episciences Iam <>
Soumis le : mercredi 17 août 2016 - 11:04:21
Dernière modification le : jeudi 7 septembre 2017 - 01:03:41
Document(s) archivé(s) le : vendredi 18 novembre 2016 - 10:14:27

Fichier

2776-9978-1-PB.pdf
Accord explicite pour ce dépôt

Identifiants

  • HAL Id : hal-01352843, version 1

Collections

Citation

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. Discrete Mathematics and Theoretical Computer Science, DMTCS, 2016, Vol. 17 no. 3 (3), pp.307-314. 〈hal-01352843〉

Partager

Métriques

Consultations de la notice

49

Téléchargements de fichiers

231