×

The search for minimal edge 1-extension of an undirected colored graph. (English) Zbl 1482.05324

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.”

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.)
PDFBibTeX XMLCite
Full Text: DOI MNR