Razumovskiĭ, Petr Vladimirovich The search for minimal edge 1-extension of an undirected colored graph. (English) Zbl 1482.05324 Izv. Sarat. Univ. (N.S.), Ser. Mat. Mekh. Inform. 21, No. 3, 400-407 (2021). Edge \(k\)-extension of graphs is a model proposed by Harary (see [F. Harary and J. P. Hayes, Networks 23, No. 2, 135–142 (1993; Zbl 0796.05046); ibid. 27, No. 1, 19–23 (1996; Zbl 0852.90081)]) to investigate edge fault tolerance between components in discrete systems. In this paper, for \(k=1\), the author extends this investigation to graphs with given coloring functions.Summary: “Let \(G=(V, \alpha, f)\) be a colored graph with a coloring function \(f\) defined on its vertices set \(V\) . Colored graph \(G^\ast\) is an edge 1-extension of a colored graph \(G\) if \(G\) could be included into each subgraph taking into consideration the colors. These subgraphs could be built from \(G^\ast\) by removing one of the graph’s edges. Let colored edge 1-extension \(G^\ast\) be minimal if \(G^\ast\) has as many vertices as the original graph \(G\) and it has the minimal number of edges among all edge 1-extensions of graph \(G\). The article considers the problem of search for minimal edge 1-extensions of a colored graph with isomorphism rejection technique. The search algorithm of all non-isomorphic minimal edge 1-extensions of a defined colored graph is suggested.” Reviewer: Italo Simonelli (Durham) Cited in 1 Document MSC: 05C85 Graph algorithms (graph-theoretic aspects) 68M15 Reliability, testing and fault tolerance of networks and computer systems 05C15 Coloring of graphs and hypergraphs 05C60 Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) Keywords:graph extensions; graph colorings; colored graphs; edge extensions; minimal extensions; graph isomorphism; colored graph isomorphism; fault tolerance Citations:Zbl 0796.05046; Zbl 0852.90081 PDFBibTeX XMLCite \textit{P. V. Razumovskiĭ}, Izv. Sarat. Univ. (N.S.), Ser. Mat. Mekh. Inform. 21, No. 3, 400--407 (2021; Zbl 1482.05324) Full Text: DOI MNR