Name
Title | ||
|---|---|---|
Fault-tolerant Hamiltonian laceability of Cayley graphs generated by transposition trees. |
Abstract | ||
|---|---|---|
A bipartite graph is Hamiltonian laceable if there exists a Hamiltonian path joining every pair of vertices that are in different parts of the graph. It is well known that Cay(Sn,B) is Hamiltonian laceable, where Sn is the symmetric group on {1,2,…,n} and B is a generating set consisting of transpositions of Sn. In this paper, we show that for any F⊆E(Cay(Sn,B)), if |F|≤n−3 and n≥4, then there exists a Hamiltonian path in Cay(Sn,B)−F joining every pair of vertices that are in different parts of the graph. The result is optimal with respect to the number of edge faults. |
Year | DOI | Venue |
|---|---|---|
2012 | 10.1016/j.disc.2012.06.007 | Discrete Mathematics |
Keywords | Field | DocType |
Cayley graph,Johnson graph,Symmetric group,Hamiltonian laceability,Fault tolerance | Random regular graph,Discrete mathematics,Wheel graph,Combinatorics,Hamiltonian path,Quartic graph,Hamiltonian path problem,Factor-critical graph,Pancyclic graph,Mathematics,Path graph | Journal |
Volume | Issue | ISSN |
312 | 21 | 0012-365X |
Citations | PageRank | References |
7 | 0.51 | 24 |
Authors | ||
3 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Hengzhe Li | 1 | 81 | 9.29 |
| Weihua Yang | 2 | 149 | 16.21 |
| Jixiang Meng | 3 | 353 | 55.62 |