Izvestiya of Saratov University.

Mathematics. Mechanics. Informatics

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

This is an open access article distributed under the terms of Creative Commons Attribution 4.0 International License (CC-BY 4.0).
Published online: 
31.08.2021
Full text:
(downloads: 159)
Language: 
English
Heading: 
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.

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).
Received: 
25.01.2021
Accepted: 
29.04.2021
Published: 
31.08.2021