Minimum self-repairing graphs
type: Item
instance of: scholarly article
title: Minimum self-repairing graphs
zbMATH Open document ID: 0890.05059
DOI: 10.1007/BF03353012
author: Arthur M. Farley
author: Andrzej Proskurowski
published in: Graphs and Combinatorics
publication date: 1998-06-29T00:00:00Z
review text: 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 th…
Mathematics Subject Classification ID: 05C75
zbMATH DE Number: 1106810
zbMATH Keywords: self-repairing graph
zbMATH Keywords: twin graph
zbMATH Keywords: characterization
reviewed by: Heinz-Joachim Presia
MaRDI profile type: Publication
cites work: Linear time algorithms for NP-hard problems restricted to partial k- trees
cites work: Minimally 3-connected graphs
cites work: Q3789491
cites work: Q5572939
cites work: Graph minors. II. Algorithmic aspects of tree-width
full work available at URL: https://doi.org/10.1007/bf03353012
OpenAlex ID: W2073756966
description: scientific article; zbMATH DE number 1106810