ISSN 1816-9791 (Print)
ISSN 2541-9005 (Online)

#### For citation:

Razumovsky P. V. The search for minimal edge 1-extension of an undirected colored graph. Izvestiya of Saratov University. Mathematics. Mechanics. Informatics, 2021, vol. 21, iss. 3, pp. 400-407. DOI: 10.18500/1816-9791-2021-21-3-400-407

Published online:
31.08.2021
Full text:
Language:
English
Article type:
Article
UDC:
517.98

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

Autors:
Razumovsky Peter Vladimirovich, Saratov State University
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.

Key words:
References:
1. Avizienis A. Design of fault-tolerant computers. AFIPS ’67 (Fall): Proceedings of the November 14–16, 1967, fall joint computer conference. New York, ACM, 1967, pp. 733– 743. https://doi.org/10.1145/1465611.1465708
2. Hayes J. P. A graph model for fault-tolerant computing system. IEEE Transactions on Computers, 1976, vol. C-25, iss. 9, pp. 875–884. https://doi.org/10.1109/TC.1976.1674712
3. Harary F., Hayes J. P. Edge fault tolerance in graphs. Networks, 1993, vol. 23, pp. 135–142. https://doi.org/10.1002/net.3230230207
4. Harary F., Hayes J. P. Node fault tolerance in graphs. Networks, 1996, vol. 27, pp. 19–23. https://doi.org/10.1002/(SICI)1097-0037(199601)27:1%3C19::AID-NET2%3E3.0.CO;2-H
5. Abrosimov M. B. Grafovye modeli otkazoustoichivosti [Fault Tolerance Graph Models]. Saratov, Izd-vo Sarat. un-ta, 2012. 192 p. (in Russian).
6. McKay B. D. Isomorphism-free exhaustive generation. Journal of Algorithms, 1998, vol. 26, iss. 2, pp. 306–324. https://doi.org/10.1006/jagm.1997.0898
7. Brinkmann G. Isomorphism rejection in structure generation programs. Discrete Mathematical Chemistry (DIMACS Series in Discrete Mathematics and Theoretical Computer Science, vol. 51). 2000, pp. 25–38. https://doi.org/10.1090/dimacs/051/03
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, 2020, vol. 20, iss. 1, pp. 105–115 (in Russian). https://doi.org/10.18500/1816-9791-2020-20-1-105-115
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, 2019, vol. 19, iss. 4, pp. 479– 486 (in Russian). https://doi.org/10.18500/1816-9791-2019-19-4-479-486
10. Zykov A. A. Osnovy teorii grafov [The Basics of the Graph Theory]. Moscow, Vuzovskaya kniga, 2004. 664 p. (in Russian).