Minimum self-repairing graphs (Q1376072)

Let \(G= (V,E)\) be a simple undirected graph. Such a graph is self-repairing if it is 2-connected and the removal of a single vertex results in no increase in distance between any pair of remaining vertices. By a corollary of the authors' Theorem 1 such graphs \(G\) can be characterized in the following manner: \(G\) is a self-repairing graph iff, for each vertex \(v\in G\) and for each pair of vertices \(u,w\in N_G(v)\), vertices \(u\), \(v\), and \(w\) are members of a cycle of length at most 4 in \(G\), e.g., a three- or four-cycle (here the open neighborhood of \(v\) in \(G\) is denoted by \(N_G(v)\)). In the present paper, the class of minimum self-repairing graphs which have the fewest edges for a given number of vertices is characterized. Therefore two vertices \(x\) and \(y\) of \(G\) are said to be twins iff \(N_G(x)= N_G(y)\). Basing upon this notion, twin graphs are defined recursively as follows: (i) the four-cycle is a twin graph, and (ii) if \(G\) is a twin graph, then \(G'\) constructed by connecting a new vertex by two edges to a pair of twins in \(G\) is a twin graph. It is proved that a twin graph is self-repairing (Theorem 2), and the minimum self-repairing graphs are characterized by the following theorems and some lemmas: (a) the minimum number of edges in a self-repairing graph of \(n\) vertices is \(2n-4\) (Theorem 3); (b) a minimum self-repairing graph with more than 4 vertices and having a degree 2 vertex is a twin graph (Lemma 5); (c) a minimum self-repairing graph without degree 2 vertices has no three-cycle involving a degree 3 vertex (Lemma 6); and (d) the only minimum self-repairing graph with no degree 2 vertices is the cube graph (Lemma 7). By these properties the class of minimum self-repairing graphs is completely characterized and the authors obtain the following main result of the paper: A minimum self-repairing graph is either a twin graph or the cube graph (Theorem 4). Finally, they present a constructive characterization of this class of graphs.