Name
Abstract | ||
|---|---|---|
Fault-tolerant networks are often modeled as s-hamiltonian graphs. Thus it is of interests to find graph families in which whether a graph is s-hamiltonian can be determined in polynomial time. An hourglass is a graph obtained from K-5 by deleting the edges in a cycle of length 4, and an hourglass-free graph is one that has no induced subgraph isomorphic to an hourglass. Kriesell in [J. Combin. Theory Ser. B, 82 (2001), 306-315] proved that every 4 connected hourglass-free line graph is Hamilton-connected, and Kaiser, Ryjacek and Vrana in [Discrete Mathematics, 321 (2014) 1-11] extended it by showing that every 4-connected hourglass-free line graph is 1-Hamilton-connected. We characterize all essentially 4-edge connected graphs whose line graph is hourglass-free. Consequently we prove that for any integer s and for any hourglass-free line graph L(G), each of the following holds.& nbsp;(i) Ifs >= 2, then L(G) is s-hamiltonian if and only if kappa(L(G)) >= s + 2;& nbsp;(ii) Ifs >= 1, then L(G) is s-Hamilton-connected if and only if kappa(L(G)) >= s + 3. (C)& nbsp;2022 Published by Elsevier B.V. |
Year | DOI | Venue |
|---|---|---|
2022 | 10.1016/j.disc.2022.112897 | DISCRETE MATHEMATICS |
Keywords | DocType | Volume |
Fault-tolerant networks, Polynomial algorithm, s-hamiltonian, Line graph, Hourglass-free graph | Journal | 345 |
Issue | ISSN | Citations |
8 | 0012-365X | 0 |
PageRank | References | Authors |
0.34 | 0 | 4 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Aimei Yu | 1 | 0 | 2.37 |
| Ping Li | 2 | 21 | 7.14 |
| Yang Wu | 3 | 84 | 18.42 |
| Hong-Jian Lai | 4 | 631 | 97.39 |