Increasing the connectivity of the star graphs

From MaRDI portal





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)].




Cited in
(33)








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)