Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
4648003 | Discrete Mathematics | 2012 | 9 Pages |
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.
Related Topics
Physical Sciences and Engineering
Mathematics
Discrete Mathematics and Combinatorics
Authors
Hengzhe Li, Weihua Yang, Jixiang Meng,