|
Applied Theory of Automata and Graphs
On the generation of minimal graph extensions by the method of canonical representatives
I. A. Kamil, H. H. K. Sudani, A. A. Lobov, M. B. Abrosimov Saratov State University
Abstract:
A graph $G^*$ is a $k$-vertex (edge) extension of a graph $G$ if every graph obtained by removing any $k$ vertices (edges) from $G^*$ contains $G$. A $k$-vertex (edge) extension $G^*$ of graph $G$ is said to be minimal if it contains minimum possible vertices and has the minimum number of edges among all $k$-vertex (edge) extension of graph $G$. The paper proposes an algorithm for generating all non-isomorphic minimal vertex (edge) $k$-extensions of a given graph with isomorphism rejection technique by using method of generating canonical representatives.
Keywords:
fault tolerance, graph extension, isomorphism, canonical code, generating canonical representatives.
Citation:
I. A. Kamil, H. H. K. Sudani, A. A. Lobov, M. B. Abrosimov, “On the generation of minimal graph extensions by the method of canonical representatives”, Prikl. Diskr. Mat. Suppl., 2019, no. 12, 179–182
Linking options:
https://www.mathnet.ru/eng/pdma465 https://www.mathnet.ru/eng/pdma/y2019/i12/p179
|
|