Geodesic
The search for minimal edge $1$-extension of an undirected colored graph
Izvestiya of Saratov University. Mathematics. Mechanics. Informatics, Tome 21 (2021) no. 3, pp. 400-407 
P. V. Razumovsky. The search for minimal edge $1$-extension of an undirected colored graph. Izvestiya of Saratov University. Mathematics. Mechanics. Informatics, Tome 21 (2021) no. 3, pp. 400-407. http://geodesic.mathdoc.fr/item/ISU_2021_21_3_a11/
@article{ISU_2021_21_3_a11,
     author = {P. V. Razumovsky},
     title = {The search for minimal edge $1$-extension of an undirected colored graph},
     journal = {Izvestiya of Saratov University. Mathematics. Mechanics. Informatics},
     pages = {400--407},
     year = {2021},
     volume = {21},
     number = {3},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/ISU_2021_21_3_a11/}
}
TY  - JOUR
AU  - P. V. Razumovsky
TI  - The search for minimal edge $1$-extension of an undirected colored graph
JO  - Izvestiya of Saratov University. Mathematics. Mechanics. Informatics
PY  - 2021
SP  - 400
EP  - 407
VL  - 21
IS  - 3
UR  - http://geodesic.mathdoc.fr/item/ISU_2021_21_3_a11/
LA  - en
ID  - ISU_2021_21_3_a11
ER  - 
%0 Journal Article
%A P. V. Razumovsky
%T The search for minimal edge $1$-extension of an undirected colored graph
%J Izvestiya of Saratov University. Mathematics. Mechanics. Informatics
%D 2021
%P 400-407
%V 21
%N 3
%U http://geodesic.mathdoc.fr/item/ISU_2021_21_3_a11/
%G en
%F ISU_2021_21_3_a11

Voir la notice de l'article provenant de la source Math-Net.Ru

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.

[1] Avizienis A., “Design of fault-tolerant computers”, AFIPS '67 (Fall): Proceedings of the November 14–16, 1967, fall joint computer conference, ACM, New York, 1967, 733–743 | DOI

[2] Hayes J. P., “A graph model for fault-tolerant computing system”, IEEE Transactions on Computers, C-25:9 (1976), 875–884 | DOI

[3] Harary F., Hayes J. P., “Edge fault tolerance in graphs”, Networks, 23 (1993), 135–142 | DOI | Zbl

[4] Harary F., Hayes J. P., “Node fault tolerance in graphs”, Networks, 27 (1996), 19–23 | DOI | Zbl

[5] Abrosimov M. B., Fault Tolerance Graph Models, Izd-vo Sarat. un-ta, Saratov, 2012, 192 pp. (in Russian)

[6] McKay B. D., “Isomorphism-free exhaustive generation”, Journal of Algorithms, 26:2 (1998), 306–324 | DOI | Zbl

[7] Brinkmann G., “Isomorphism rejection in structure generation programs”, Discrete Mathematical Chemistry, DIMACS Series in Discrete Mathematics and Theoretical Computer Science, 51, 2000, 25–38 | DOI | Zbl

[8] Abrosimov M. B., Sudani H. H. K., Lobov A. A., “Construction of all minimal edge extensions of the graph with isomorphism rejection”, Izvestiya of Saratov University. Mathematics. Mechanics. Informatics, 20:1 (2020), 105–115 (in Russian) | DOI | Zbl

[9] Abrosimov M. B., Kamil I. A. K., Lobov A. A., “Construction of all nonisomorphic minimal vertex extensions of the graph by the method of canonical representatives”, Izvestiya of Saratov University. Mathematics. Mechanics. Informatics, 19:4 (2019), 479–486 (in Russian) | DOI | Zbl

[10] Zykov A. A., The Basics of the Graph Theory, Vuzovskaya kniga, M., 2004, 664 pp. (in Russian)