Increasing the connectivity of the star graphs
The authors prove the following structural theorem for star graphs \(S_n\): Let be \(n\geq 4\) and \(T\) a set of vertices of \(S_n\) such that \(|T|\leq 2n-4\). Then \(S_n\setminus T\) satisfies one of the following conditions: (1) \(S_n\setminus T\) is connected. (2) \(S_n\setminus T\) has two components, one is exactly a vertex. (3) \(S_n\setminus T\) has two components, one is a graph with two vertices and one edge. Moreover, \(T\) is the union of the neighbour sets of \(u\) and \(v\) without \(\{u,v\}\). This structural theorem is used to solve an augmentation problem for \(S_n\): construct the maximally connected graphs based on star graphs. For an introduction of star graphs see, i.e., \textit{S. B. Akers}, \textit{D. Harel} and \textit{B. Krishnamurthy} [Proc. Int. Conf. Parallel Processing, St. Charles, IL, 393-400 (1987)].
- Strong structural properties of unidirectional star graphs
- Conditional fault tolerance of arrangement graphs
- Characterization of component diagnosability of regular networks
- Linearly many faults in Cayley graphs generated by transposition triangle free unicyclic graphs
- The 1-good neighbor connectivity of unidirectional star graph networks
- On the problem of determining which \((n, k)\)-star graphs are Cayley graphs
- Linearly many faults in Cayley graphs generated by transposition trees
- Augmenting chains in graphs without a skew star.
- A new approach to finding the extra connectivity of graphs
- Note on reliability of star graphs
- Increasing the connectivity of split-stars
- Conditional fault diagnosability of dual-cubes
- Cyclic connectivity of star graph
- Linearly many faults in (n,k)-star graphs
- Matching preclusion and conditional matching preclusion for bipartite interconnection networks. II: Cayley graphs generated by transposition trees and hyper-stars
- Linearly many faults in 2-tree-generated networks
- The extra connectivity of bubble-sort star graphs
- Fault resiliency of Cayley graphs generated by transpositions
- Maximal vertex-connectivity of
- Conditional fault diagnosis of hierarchical hypercubes
- Fault diagnosability of arrangement graphs
- On component connectivity of hierarchical star networks
- The generalized 4-connectivity of hypercubes
- Linearly many faults in arrangement graphs
- Fault-Tolerance of Star Graph Based on Subgraph Fault Pattern
- Conditional diagnosability of alternating group networks
- The non-inclusive diagnosability of a kind of networks
- Conditional (edge) neighbor connectivity of hierarchical star networks
- Vulnerability assessment of a new class of Cayley graph
- \(\{ 1, 2, 3 \}\)-extra connectivity of Cayley graphs generated by \(k\)-trees
- On reliability of the folded hypercubes in terms of the extra edge-connectivity
- A characterization of 1, 2-extra-cut set for hierarchical graph
- Relationship between extra edge connectivity and component edge connectivity for regular graphs
This page was built for publication: Increasing the connectivity of the star graphs
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4785232)