Construction of minimum vertex extensions of a graph by the Read-Faradzhev method

I.A.K. Kamil, M.B. Abrosimov, A.A. Lobov


In 1976 John Hayes proposed a graph-based model to investigate node fault tolerance of discrete systems. A graph G* is vertex k-extension of a graph G if after removing any k vertices from G* result graph contains G. A vertex k-extension of the graph G is called minimal if it has the least number of vertices and edges among all vertex k-extensions of G. Later together with Frank Harary, the model was extended to failures of connections between elements. The problem of verifying a vertex k-extension of a graph is NP-complete. For some types of graphs, it was possible to find an analytical solution to the problem of constructing minimal vertex k-extensions: paths, cycles, stars, etc. In general, a graph can have many nonisomorphic minimal vertex k-extensions. The exhaustive algorithm for constructing all nonisomorphic minimal vertex k-extensions of a given graph can be used only for graphs with a small number of vertices. In some cases, it is possible to find the degree vector of the minimum vertex k-extension, which allows to search much faster. In this paper, we propose an algorithm for constructing all nonisomorphic minimal vertex k-extensions of a given graph with isomorphism rejection by the method of canonical representatives in the Read-Faradzhev form. The implementation of this algorithm in 4 modifications is considered and the results of their work are analyzed.

Full Text:

PDF (Russian)


Hayes J. P. A graph model for fault-tolerant computing system // IEEE Transactions on Computers, 1976. Vol. C-25, No 9. P. 875–884. DOI: 10.1109/TC.1976.1674712

Harary F., Hayes J. P. Edge fault tolerance in graphs // Networks. 1993. Vol.23. P.135–142. DOI: 10.1002/net.3230230207

Abrosimov M.B. Grafovye modeli otkazoustoichivosti. Saratov : Izdatel'stvo Saratovskogo universiteta, 2012, 192 p.

Bogomolov A.M., Salii V.N. Algebraicheskie osnovy teorii diskretnykh sistem. M.: Nauka 1997.

Abrosimov M.B. On the complexity of some problems related to graph extensions. Math. Notes, 2010. Vol. 88, no. 5, pp. 619–625. DOI: 10.1134/S0001434610110015

Abrosimov M.B. Minimal'nye rasshireniia grafov // Novye informatsionnye tekhnologii v issledovanii diskretnykh struktur. Tomsk: 2000. pp. 59–64.

Abrosimov M.B. Minimal'nye rasshireniia 4-,5-,6- i 7-vershinnykh grafov. Saratov gos. un-t. - Saratov, 2000. – 26 p.; Dep. v VINITI 06.09.2000, №2352-V00.

Brinkmann G. Isomorphism rejection in structure generation programs // Discrete Mathematical Chemistry, DIMACS Series in Discrete Mathematics and Theoretical Computer Science. 2000. Vol. 51. P. 25–38. DOI: 10.1090/dimacs/051/03

Abrosimov M.B., Kamil I.A.K., Lobov A.A. Postroenie vsekh neizomorfnykh minimal'nykh vershinnykh rasshirenii grafa metodom kanonicheskikh predstavitelei // Izv. Sarat. un-ta. Nov. ser. Ser. Matematika. Mekhanika. Informatika. 2019. Vol. 19, no. 4. pp. 479–486. DOI:

Grund R. Konstruktion schlichter Graphen mit gegebener Gradpartition // Bayreuther Mathematische Schriften. 1993. Vol.44. P.73–104.

Sukhov S.A. DSR Generator // Svid. o gos. registratsii programmy dlia EVM № 2016610073. Zaregistrirovana v Reestre programm dlia EVM 11.01.2016.

Meringer M. Fast generation of regular graphs and construction of cages // Journal of Graph Theory. 1999. Vol.30. P.137–146.

Brinkmann G. Fast generation of cubic graphs // Journal of Graph Theory. 1996. Vol.23(2). P.139–149.<139::AID-JGT5>3.0.CO;2-U

Brinkmann G., Goedgebeur J., McKay B. D. Generation of cubic graphs // Discrete Mathematics and Theoretical Computer Science. 2011. Vol.13(2). P.69–80.

Abrosimov M.B., Brinkmann G., Sukhov S.A. O kolichestve minimal'nykh 1-rasshirenii tsiklov s chislom vershin do 26 i 28 // Komp'iuternye nauki i informatsionnye tekhnologii : Materialy Mezhdunar. nauch. kof. – Saratov : Izdat. tsentr «Nauka», 2016. pp. 9-11.

Volga Regional Center for New Information Technologies. Available at:

Encyclopedia: World of Graphs. Available at:


  • There are currently no refbacks.

Abava  Absolutech Fruct 2020

ISSN: 2307-8162