Hamiltonian paths and Hamiltonian cycles passing through prescribed linear forests in star graph with fault-tolerant edges (Q6157419)
From MaRDI portal
scientific article; zbMATH DE number 7684698
Language | Label | Description | Also known as |
---|---|---|---|
English | Hamiltonian paths and Hamiltonian cycles passing through prescribed linear forests in star graph with fault-tolerant edges |
scientific article; zbMATH DE number 7684698 |
Statements
Hamiltonian paths and Hamiltonian cycles passing through prescribed linear forests in star graph with fault-tolerant edges (English)
0 references
11 May 2023
0 references
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.
0 references
Hamiltonian path
0 references
Hamiltonian cycle
0 references
prescribed Hamiltonian laceable
0 references
fault-tolerant edges
0 references
star graph
0 references
prescribed linear forests
0 references
0 references
0 references
0 references