Embedding longest fault-free paths onto star graphs with more vertex faults
An {\(n\)-dimensional star \(S_n\)} is a graph with vertex set equal to all the permutations of \(n\) numbers. Two vertices of \(S_n\) are adjacent if the corresponding permutations differ by a transposition involving their first elements. In particular, the graph \(S_n\) is \((n-1)\)-regular and bipartite. The author shows that for any set \(W\) of vertices of \(S_n\), \(| W| \leq n-3\) and \(n\geq 4\), and any two vertices \(s\) and \(t\) of \(S_n\), \(s,t\not\in W\), there exists a path between \(s\) and \(t\) of length at least \(n!-2| W| -2\) avoiding vertices contained in the set \(W\). This improves previous results of \textit{J.-H.~Chang, C.-S.~Shin} and \textit{K.-Y.~Chwa} [IEICE Trans. Fund. E82-A~(9), 1953--1964 (1999)], \textit{S.-Y. Hsieh, G.-H.~Chen} and \textit{C.-W.~Ho} [Proc. Int. Conf. Parallel Process., 140--147 (1998)], and \textit{S.-Y.~Hsieh, G.-H.~Chen} and \textit{C.-W.~Ho} [Theor. Comput. Sci. 262, 215--227 (2001; Zbl 0983.68141)] by constant factors.
- Longest fault-free paths in star graphs with vertex faults
- Cycle embedding in star graphs with more conditional faulty edges
- Longest paths and cycles in faulty star graphs
- Embedding cycles of various lengths into star graphs with both edge and vertex faults
- Edge-bipancyclicity of star graphs with faulty elements
- A group-theoretic model for symmetric interconnection networks
- Embedding an arbitrary binary tree into the star graph
- Embedding meshes on the star graph
- Hamiltonian-laceability of star graphs
- scientific article; zbMATH DE number 54299 (Why is no real title available?)
- scientific article; zbMATH DE number 52113 (Why is no real title available?)
- Longest fault-free paths in star graphs with vertex faults
- Near embeddings of hypercubes into Cayley graphs on the symmetric group
- Path embedding in star graphs
- Fault-tolerant panconnectivity of augmented cubes
- Survey on path and cycle embedding in some networks
- The \(h\)-extra connectivity and \(h\)-extra conditional diagnosability of bubble-sort star graphs
- g-good-neighbor conditional diagnosability of star graph networks under PMC model and MM^* model
- Node-disjoint paths in a level block of generalized hierarchical completely connected networks
- Structure connectivity and substructure connectivity of wheel networks
- Edge-fault-tolerant hamiltonicity of locally twisted cubes under conditional edge faults
- Structure connectivity and substructure connectivity of bubble-sort star graph networks
- Edge-fault-tolerant Hamiltonicity of pancake graphs under the conditional fault model
- Fault-free mutually independent Hamiltonian cycles in hypercubes with faulty edges
- Path and cycle fault tolerance of bubble-sort graph networks
- Cycle embedding in star graphs with edge faults
- The spanning cyclability of Cayley graphs generated by transposition trees
- Embedding longest fault-free paths in arrangement graphs with faulty vertices
- Random induced subgraphs of Cayley graphs induced by transpositions
- Cycle embedding in star graphs with more conditional faulty edges
- The 2-good-neighbor connectivity and 2-good-neighbor diagnosability of bubble-sort star graph networks
- Linearly many faults in arrangement graphs
- Longest fault-free paths in star graphs with vertex faults
- Hamiltonian paths and Hamiltonian cycles passing through prescribed linear forests in star graph with fault-tolerant edges
- Edge-bipancyclicity of star graphs with faulty elements
- Conditional matching preclusion for the arrangement graphs
- The edge fault-tolerant two-disjoint path covers of Cayley graphs generated by a transposition tree
- Reliability analysis of exchanged hypercubes based on the path connectivity
- Two-disjoint-cycle-cover edge/vertex bipancyclicity of star graphs
- Fault tolerance in k-ary n-cube networks
- Disjoint path covers of star graphs
- On prescribed Hamilton laceability of hybrid-faulty star graphs
- Longest paths and cycles in faulty star graphs
- Conditional connectivity of star graph networks under embedding restriction
- Many-to-many two-disjoint path covers in Cayley graphs generated by unicyclic graphs
- Fault-tolerant embedding of pairwise independent Hamiltonian paths on a faulty hypercube with edge faults
- Fault tolerance in bubble-sort graph networks
- The preclusion numbers and edge preclusion numbers in a class of Cayley graphs
- Structure connectivity and substructure connectivity of star graphs
- Cycle embedding in star graphs with conditional edge faults
- On the construction of all shortest node-disjoint paths in star networks
- Substar reliability analysis in star networks
- Conditional edge-fault Hamiltonicity of augmented cubes
- Properties of a hierarchical network based on the star graph
- Embedding cycles of various lengths into star graphs with both edge and vertex faults
- Pancyclicity and bipancyclicity of conditional faulty folded hypercubes
This page was built for publication: Embedding longest fault-free paths onto star graphs with more vertex faults
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q557839)
