Cite this article as:
Abrosimov M. B., Lobov A. A., Sudani H. H. Construction of All Minimal Edge Extensions of the Graph with Isomorphism Rejection. Izv. Saratov Univ. (N. S.), Ser. Math. Mech. Inform., 2020, vol. 20, iss. 1, pp. 105-115. DOI: https://doi.org/10.18500/1816-9791-2020-20-1-105-115
Construction of All Minimal Edge Extensions of the Graph with Isomorphism Rejection
In 1993 Frank Harary and John P. Hayes proposed a graph model for investigating edge fault tolerance of discrete systems. The technical system is mapped to a graph. The elements of the system correspond to the vertices of the graph, and links between the elements correspond to edges or arcs of the graph. Failure of a system element refers to the removal of the corresponding vertex from the system graph along with all its edges. The formalization of a fault tolerant system implementation is the extension of the graph. The graph G∗ is called the edge k-extension of the graph G if, after removing any k edges from the graph G∗ result graph contains the graph G. The edge k-extension of a graph G is called minimal if it has the least number of vertices and edges among all edge k-extensions of a graph G. An algorithm for constructing all nonisomorphic minimal edge k-extensions of a given graph using methods of canonical representatives and Read – Faradjev are proposed.
- Hayes J. P. A graph model for fault-tolerant computing system // IEEE Trans. Computers. 1976. Vol. C-25, № 9. P. 875–884. DOI: https://doi.org/10.1109/ TC.1976.1674712
- Harary F., Hayes J. P. Edge fault tolerance in graphs // Networks. 1993. Vol. 23. P. 135– 142. DOI: https://doi.org/10.1002/net.3230230207
- Абросимов М. Б. Графовые модели отказоустойчивости. Саратов : Изд-во Сарат. ун-та, 2012. 192 с.
- Богомолов А. М., Салий В. Н. Алгебраические основы теории дискретных систем. М. : Наука, 1997. 368 с.
- Абросимов М. Б. О сложности некоторых задач, связанных с расширениями графов // Матем. заметки. 2010. Т. 88, вып. 5. С. 643–650. DOI: https://doi.org/10.4213/mzm8403
- Абросимов М. Б., Камил И. А. К., Лобов А. А. Построение всех неизоморфных минимальных вершинных расширений графа методом канонических представителей // Изв. Сарат. ун-та. Нов. сер. Сер. Математика. Механика. Информатика. 2019. Т. 19, вып. 4. С. 479–486. DOI: https://doi.org/10.18500/1816-9791-2019-19-4-479-486
- Абросимов М. Б. Минимальные расширения графов // Новые информационные технологии в исследовании дискретных структур. Томск : ИД Том. гос. ун-та, 2000. С. 59–64.
- Абросимов М. Б. Минимальные расширения 4-, 5-, 6- и 7-вершинных графов. Сарат. гос. ун-т. Саратов, 2000. 26 с. ; Деп. в ВИНИТИ 06.09.2000, № 2352-В00.
- 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: https://doi.org/10.1090/dimacs/051/03
- McKay B. D. Graph formats. URL: http://users.cecs.anu.edu.au/bdm/data/formats.html (дата обращения: 01.05.2019).
- McKay B. D., Piperno A. Practical Graph Isomorphism, II // Journal of Symbolic Computation. 2014. Vol. 60. P. 94–112. DOI: https://doi.org/10.1016/j.jsc.2013.09.003
- Поволжский региональный центр новых информационных технологий : [сайт]. URL: http://prcnit.sgu.ru (дата обращения: 01.05.2019).
- Мир графов. URL: http://graphworld.ru (дата обращения: 01.05.2019).