Constructing all nonisomorphic supergraphs with isomorphism rejection

I. A. Kamil ; H. H. K. Sudani ; A. A. Lobov ; M. B. Abrosimov

Prikladnaâ diskretnaâ matematika, no. 2 (2020), pp. 82-92

Résumé

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.

Détail

Keywords: supergraph, canonical form, isomorphism rejection.
Mots-clés : isomorphism