Djelloul, Selma; Kouider, Mekkia Minimum survivable graphs with bounded distance increase. (English) Zbl 1058.68081 Discrete Math. Theor. Comput. Sci. 6, No. 1, 123-132 (2003). Summary: We study in graphs properties related to fault-tolerance in case a node fails. A graph \(G\) is \(k\)-self-repairing, where \(k\) is a non-negative integer, if after the removal of any vertex no distance in the surviving graph increases by more than \(k\). In the design of interconnection networks such graphs guarantee good fault-tolerance properties. We give upper and lower bounds on the minimum number of edges of a \(k\)-self-repairing graph for prescribed \(k\) and \(n\), where \(n\) is the order of the graph. We prove that the problem of finding, in a \(k\)-self-repairing graph, a spanning \(k\)-self-repairing subgraph of minimum size is NP-hard. MSC: 68R10 Graph theory (including graph drawing) in computer science 68M15 Reliability, testing and fault tolerance of networks and computer systems Keywords:distance; fault-tolerance; spanning subgraph PDFBibTeX XMLCite \textit{S. Djelloul} and \textit{M. Kouider}, Discrete Math. Theor. Comput. Sci. 6, No. 1, 123--132 (2003; Zbl 1058.68081) Full Text: EuDML EMIS