Hamiltonian paths and Hamiltonian cycles passing through prescribed linear forests in star graph with fault-tolerant edges (Q6157419)

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.