Geodesic
Constructing all nonisomorphic supergraphs with isomorphism rejection
Prikladnaâ diskretnaâ matematika, no. 2 (2020), pp. 82-92.

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

An important trend in graph theory is the construction of graphs with given properties without directly checking for isomorphism. Programs that perform such constructions are called generators. Generators of undirected graphs with a given number of vertices, trees, regular graphs, bipartite graphs, tournaments, etc. are well known. A graph $G = (V, \alpha)$ is a subgraph of a graph $H = (W, \beta)$ if all vertices and edges of $G$ belong to $H$, that is, $V \subseteq W$ and $ \alpha \subseteq \beta$. If $G$ is a subgraph of $H$, then $H$ is a supergraph of $G$. In researches on graph theory, often the properties of a graph are studied through some of its parts. The inverse problem also appears: to construct graphs with given part as subgraph. Such a problem occurs, for example, in the study of fault-tolerant design of discrete systems. The algorithm for constructing for a given graph all its supergraphs with a given number of edges without checking for isomorphism is described. A special matrix code (route or M-code) and an algorithm for generating supergraphs by the method of canonical representatives based on it are proposed. The concept of the method of canonical representatives is that one representative in each class of isomorphic graphs is selected and is called canonical. A canonical representative function (canonical form) is a function $c$ with the properties that $c(G) = c (H)$ if and only if $G$ and $H$ are isomorphic. The graph $c(G)$ is called the canonical representative of the graph $G$. We introduce a routing code (M-code) for the graph $H$ relative to the graph $G$ and denote $C_G (H)$. Given the adjacency matrices of the graphs $G$ and $H$, construct the code $C_G (H)$ in two steps: first, write out the elements of the adjacency matrix of the graph $H$ at the corresponding positions of which there is $1$ in the adjacency matrix of the graph $G$, then those with a value of $0$. For undirected graphs, only elements located above the main diagonal are written out. Optimization of the proposed method and issues related to its parallel implementation are discussed.
Keywords: supergraph, canonical form, isomorphism rejection.
Mots-clés : isomorphism 
@article{PDM_2020_2_a6,
     author = {I. A. Kamil and H. H. K. Sudani and A. A. Lobov and M. B. Abrosimov},
     title = {Constructing all nonisomorphic supergraphs with isomorphism rejection},
     journal = {Prikladna\^a diskretna\^a matematika},
     pages = {82--92},
     publisher = {mathdoc},
     number = {2},
     year = {2020},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/PDM_2020_2_a6/}
}
TY  - JOUR
AU  - I. A. Kamil
AU  - H. H. K. Sudani
AU  - A. A. Lobov
AU  - M. B. Abrosimov
TI  - Constructing all nonisomorphic supergraphs with isomorphism rejection
JO  - Prikladnaâ diskretnaâ matematika
PY  - 2020
SP  - 82
EP  - 92
IS  - 2
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/PDM_2020_2_a6/
LA  - ru
ID  - PDM_2020_2_a6
ER  - 
%0 Journal Article
%A I. A. Kamil
%A H. H. K. Sudani
%A A. A. Lobov
%A M. B. Abrosimov
%T Constructing all nonisomorphic supergraphs with isomorphism rejection
%J Prikladnaâ diskretnaâ matematika
%D 2020
%P 82-92
%N 2
%I mathdoc
%U http://geodesic.mathdoc.fr/item/PDM_2020_2_a6/
%G ru
%F PDM_2020_2_a6
I. A. Kamil; H. H. K. Sudani; A. A. Lobov; M. B. Abrosimov. Constructing all nonisomorphic supergraphs with isomorphism rejection. Prikladnaâ diskretnaâ matematika, no. 2 (2020), pp. 82-92. http://geodesic.mathdoc.fr/item/PDM_2020_2_a6/

[1] Bogomolov A. M., Salii V. N., Algebraic Foundations of the Theory of Discrete Systems, Nauka Publ., M., 1997, 368 pp. (in Russian) | MR

[2] Harary F., Graph Theory, Addison-Wesley, 1969, 274 pp. | MR | Zbl

[3] Brinkmann G., “Isomorphism rejection in structure generation programs”, DIMACS Ser. Discr. Math. Theor. Comput. Sci., 51 (2000), 25–38 | DOI | MR | Zbl

[4] McKay B. D., Piperno A., “Practical graph isomorphism. II”, J. Symbolic Computation., 60 (2014), 94–112 | DOI | MR | Zbl

[5] Abrosimov M. B., “Comparison of sufficient degree based conditions for Hamiltonian graph”, Prikladnaya Diskretnaya Matematika, 2019, no. 45, 55–63 (in Russian)

[6] Abrosimov M. B., Fault Tolerance Graph Models, Saratov Univ. Publ., Saratov, 2012, 192 pp. (in Russian)

[7] Meringer M., “Fast generation of regular graphs and construction of cages”, J. Graph Theory, 30 (1999), 137–146 | 3.0.CO;2-G class='badge bg-secondary rounded-pill ref-badge extid-badge'>DOI | MR | Zbl

[8] Brinkmann G., Goedgebeur J., McKay B. D., “Generation of cubic graphs”, Discr. Math. Theoret. Comput. Sci., 13:2 (2011), 69–80 | MR | 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”, Izv. Saratov Univ. (N. S.), Ser. Math. Mech. Inform., 19:4 (2019), 479–486 (in Russian) | MR

[10] Abrosimov M. B., Sudani H. H. K., Lobov A. A., “Construction of all minimal edge extensions of the graph with isomorphism rejection”, Izv. Saratov Univ. (N. S.), Ser. Math. Mech. Inform., 20:1 (2020), 105–115 (in Russian)

[11] Volga Regional Center for New Information Technologies, , 2020 http://prcnit.sgu.ru