The search for minimal edge 1-extension of an undirected colored graph

Abstract

Let $G=(V, \alpha, f)$ be a colored graph with a coloring function $f$ defined on its vertices set $V$. Colored graph $G^*$ 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^*$ by removing one of the graph's edges. Let colored edge $1$-extension $G^*$ be minimal if $G^*$ 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.

Keywords

• graph extensions
• graph colorings
• colored graphs
• edge extensions
• minimal extensions
• graph isomorphism
• colored graph isomorphism
• fault tolerance