On degree-sequence characterization and the extremal number of edges for various Hamiltonian properties under fault tolerance
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$...
| Main Authors: | , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Discrete Mathematics & Theoretical Computer Science
2016-08-01
|
| Series: | Discrete Mathematics & Theoretical Computer Science |
| Subjects: | |
| Online Access: | https://dmtcs.episciences.org/2149/pdf |
| _version_ | 1797270054778175488 |
|---|---|
| author | Shih-Yan Chen Shin-Shin Kao Hsun Su |
| author_facet | Shih-Yan Chen Shin-Shin Kao Hsun Su |
| author_sort | Shih-Yan Chen |
| collection | DOAJ |
| description | 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$. |
| first_indexed | 2024-04-25T01:58:10Z |
| format | Article |
| id | doaj.art-1413b1dd5600444a826e51135c009e76 |
| institution | Directory Open Access Journal |
| issn | 1365-8050 |
| language | English |
| last_indexed | 2024-04-25T01:58:10Z |
| publishDate | 2016-08-01 |
| publisher | Discrete Mathematics & Theoretical Computer Science |
| record_format | Article |
| series | Discrete Mathematics & Theoretical Computer Science |
| spelling | doaj.art-1413b1dd5600444a826e51135c009e762024-03-07T15:29:03ZengDiscrete Mathematics & Theoretical Computer ScienceDiscrete Mathematics & Theoretical Computer Science1365-80502016-08-01Vol. 17 no. 3Graph Theory10.46298/dmtcs.21492149On degree-sequence characterization and the extremal number of edges for various Hamiltonian properties under fault toleranceShih-Yan Chen0Shin-Shin Kao1Hsun Su2Taipei Municipal Bai-Ling Senior High SchoolDepartment of Applied Mathematics, Chung Yuan Christian UniversityDepartment of Public Finance and Taxation, Takming UniversityAssume 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$.https://dmtcs.episciences.org/2149/pdfgraph sizehamiltonianfault-tolerant hamiltonianhamiltonian-connecteddegree sequence[info.info-dm] computer science [cs]/discrete mathematics [cs.dm] |
| spellingShingle | 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 & Theoretical Computer Science graph size hamiltonian fault-tolerant hamiltonian hamiltonian-connected degree sequence [info.info-dm] computer science [cs]/discrete mathematics [cs.dm] |
| title | On degree-sequence characterization and the extremal number of edges for various Hamiltonian properties under fault tolerance |
| title_full | On degree-sequence characterization and the extremal number of edges for various Hamiltonian properties under fault tolerance |
| title_fullStr | On degree-sequence characterization and the extremal number of edges for various Hamiltonian properties under fault tolerance |
| title_full_unstemmed | On degree-sequence characterization and the extremal number of edges for various Hamiltonian properties under fault tolerance |
| title_short | On degree-sequence characterization and the extremal number of edges for various Hamiltonian properties under fault tolerance |
| title_sort | on degree sequence characterization and the extremal number of edges for various hamiltonian properties under fault tolerance |
| topic | graph size hamiltonian fault-tolerant hamiltonian hamiltonian-connected degree sequence [info.info-dm] computer science [cs]/discrete mathematics [cs.dm] |
| url | https://dmtcs.episciences.org/2149/pdf |
| work_keys_str_mv | AT shihyanchen ondegreesequencecharacterizationandtheextremalnumberofedgesforvarioushamiltonianpropertiesunderfaulttolerance AT shinshinkao ondegreesequencecharacterizationandtheextremalnumberofedgesforvarioushamiltonianpropertiesunderfaulttolerance AT hsunsu ondegreesequencecharacterizationandtheextremalnumberofedgesforvarioushamiltonianpropertiesunderfaulttolerance |