Hamiltonian paths and Hamiltonian cycles passing through prescribed linear forests in star graph with fault-tolerant edges
The \(n\)-dimensional star graph \(S_n\) has as its vertex set all permutations of the set \(\{1,2,\dots , n\}\). A vertex (permutation) \(u\) is denoted as \(u=u_1u_2\dots u_n\). Each vertex \(u_1u_2\dots u_n\) is adjacent to the following \(n-1\) vertices : \(u_iu_2\dots u_{i-1}u_1u_{i+1}\dots u_n\), where \(2 \leq i \leq n\). The authors note that \(S_n\) is bipartite. They also state that the star graph is a popular and efficient model in network theory, and give examples to show that it possesses many graph theoretic properties. The authors focus on Hamiltonian paths and cycles passing through prescribed linear forests \(L\) in \(S_n\) with specified sets \(F\) of fault-tolerant edges. Let \(F\) be a set of fault tolerant edges of \(S_n\) and let \(L\) be a linear forest of \(S_n-F\) with \(|E(L)+|F| \leq n-3\). The authors show that for any two vertices \(u\) and \(v\) in different partite sets of \(S_n\), if \(\{u,v\}\) and \(L\) are compatible in \(S_n\), then there is a Hamiltonian path of \(S_n-F\) between \(u\) and \(v\) which passes through each edge of \(L\), They also show that there is Hamiltonian cycle of \(S_n-F\) passing through each edge of \(L\). These results are also optimal in a described sense.
- Conditional fault-tolerant Hamiltonicity of star graphs
- Embedding cycles of various lengths into star graphs with both edge and vertex faults
- Longest paths and cycles in faulty star graphs
- Edge-bipancyclicity of star graphs with faulty elements
- Embedding longest fault-free paths onto star graphs with more vertex faults
- A fault-free Hamiltonian cycle passing through prescribed edges in a hypercube with faulty edges
- A group-theoretic model for symmetric interconnection networks
- Cycles passing through prescribed edges in a hypercube with some faulty edges
- Edge-bipancyclicity of star graphs under edge-fault tolerant
- Embedding fault-free Hamiltonian paths with prescribed linear forests into faulty ternary \(n\)-cubes
- Embedding paths and cycles in 3-ary \(n\)-cubes with faulty nodes and links
- Fault-free Hamiltonian cycles passing through a linear forest in ternary n-cubes with faulty edges
- Fault-free Hamiltonian cycles passing through a prescribed linear forest in 3-ary \(n\)-cube with faulty edges
- Generalized measures for fault tolerance of star networks
- Hamiltonian cycles passing through linear forests in k-ary n-cubes
- Hamiltonian Cycles with Prescribed Edges in Hypercubes
- Hamiltonian paths and cycles pass through prescribed edges in the balanced hypercubes
- Hamiltonian paths and cycles passing through a prescribed path in hypercubes
- Hamiltonian paths and cycles with prescribed edges in the 3-ary \(n\)-cube
- Hamiltonian paths passing through prescribed edges in balanced hypercubes
- Hamiltonian paths with prescribed edges in hypercubes
- Hyper Hamiltonian laceability on edge fault star graph
- Hyper-Hamilton laceable and caterpillar-spannable product graphs
- Strong structural properties of unidirectional star graphs
- Fault-free Hamiltonian paths passing through prescribed linear forests in balanced hypercubes with faulty links
- Fault-free Hamiltonian cycles passing through a prescribed linear forest in 3-ary \(n\)-cube with faulty edges
- Conditional fault-tolerant Hamiltonicity of star graphs
- Optimal bounds for disjoint Hamilton cycles in star graphs
- Two-disjoint-cycle-cover edge/vertex bipancyclicity of star graphs
- On prescribed Hamilton laceability of hybrid-faulty star graphs
This page was built for publication: Hamiltonian paths and Hamiltonian cycles passing through prescribed linear forests in star graph with fault-tolerant edges
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6157419)
