Geodesic
On the generation of minimal graph extensions by the method of canonical representatives
Prikladnaya Diskretnaya Matematika. Supplement, no. 12 (2019), pp. 179-182

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

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, canonical code, generating canonical representatives.
Mots-clés : isomorphism 
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. Prikladnaya Diskretnaya Matematika. Supplement, no. 12 (2019), pp. 179-182. http://geodesic.mathdoc.fr/item/PDMA_2019_12_a49/
@article{PDMA_2019_12_a49,
     author = {I. A. Kamil and H. H. K. Sudani and A. A. Lobov and M. B. Abrosimov},
     title = {On the generation of minimal graph extensions by the method of canonical representatives},
     journal = {Prikladnaya Diskretnaya Matematika. Supplement},
     pages = {179--182},
     year = {2019},
     number = {12},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/PDMA_2019_12_a49/}
}
TY  - JOUR
AU  - I. A. Kamil
AU  - H. H. K. Sudani
AU  - A. A. Lobov
AU  - M. B. Abrosimov
TI  - On the generation of minimal graph extensions by the method of canonical representatives
JO  - Prikladnaya Diskretnaya Matematika. Supplement
PY  - 2019
SP  - 179
EP  - 182
IS  - 12
UR  - http://geodesic.mathdoc.fr/item/PDMA_2019_12_a49/
LA  - ru
ID  - PDMA_2019_12_a49
ER  - 
%0 Journal Article
%A I. A. Kamil
%A H. H. K. Sudani
%A A. A. Lobov
%A M. B. Abrosimov
%T On the generation of minimal graph extensions by the method of canonical representatives
%J Prikladnaya Diskretnaya Matematika. Supplement
%D 2019
%P 179-182
%N 12
%U http://geodesic.mathdoc.fr/item/PDMA_2019_12_a49/
%G ru
%F PDMA_2019_12_a49

[1] Hayes J. P., “A graph model for fault-tolerant computing system”, IEEE Trans. Comput., C.25:9 (1976), 875–884 | DOI | MR

[2] Harary F., Hayes J. P., “Edge fault tolerance in graphs”, Networks, 23 (1993), 135–142 | DOI | MR | Zbl

[3] Abrosimov M. B., Grafovye modeli otkazoustoichivosti, Izd-vo Sarat. un-ta, Saratov, 2012, 192 pp.

[4] Abrosimov M. B., “O slozhnosti nekotorykh zadach, svyazannykh s rasshireniyami grafov”, Matem. zametki, 2010, no. 5(88), 643–650 | DOI | Zbl

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