Образец для цитирования:
Абросимов М. Б., Моденова О. В. Характеризация орграфов с малым числом дополнительных дуг минимального вершинного 1-расширения // Изв. Сарат. ун-та. Нов. сер. Сер. Математика. Механика. Информатика. 2013. Т. 13, вып. 2. С. 3-9. DOI: https://doi.org/10.18500/1816-9791-2013-13-2-2-3-9
Характеризация орграфов с малым числом дополнительных дуг минимального вершинного 1-расширения
: Граф G∗ называется вершинным 1-расширением графа G, если граф G можно вложить в каждый граф, получающийся из графа G∗ удалением любой его вершины вместе с инцидентными ребрами. Вершинное 1-расширение G∗графа G называется минимальным, если граф G∗ имеет на одну вершину больше, чем граф G, а среди всех вершинных 1-расширений графа G с тем же числом вершин граф G∗ имеет минимальное число ребер. Рассматривается задача описания ориентированных графов, минимальное вершинное 1-расширение которых имеет заданное число дополнительных дуг. Дается решение, когда число дополнительных дуг равно одному или двум.
Библиографический список
[1]
Абросимов М. Б., Графовые модели отказоустойчивости, Изд-во Сарат. ун-та, Саратов, 2012, 192 с. [Abrosimov M. B., Graph models of fault tolerance, Saratov Univ. Press, Saratov, 2012, 192 pp.]
[2]
Hayes J. P., “A graph model for fault-tolerant computing system”, IEEE Trans. Comput., C-25:9 (1976), 875–884
[3]
Абросимов М. Б., “О сложности некоторых задач, связанных с расширениями графов”, Мат. заметки, 88:5 (2010), 643–650 ; Abrosimov M. B., “On the Complexity of Some Problems Related to Graph Extensions”, Math. Notes, 88:5 (2010), 619–625
[4]
Абросимов М. Б., “Характеризация графов с заданным числом дополнительных ребер минимального вершинного 1-расширения”, Прикладная дискретная математика, 2012, № 1, 111–120 [Abrosimov M. B., “Characterization of graphs with a given number of additional edges in a minimal 1-vertex extension”, Applied Discrete Mathematics, 2012, no. 1, 111–120]
[5]
Абросимов М. Б., “Минимальные вершинные расширения направленных звезд”, Дискретная математика, 23:2 (2011), 93–102 [Abrosimov M. B., “Minimal vertex extensions of directed stars”, Diskr. Mat., 23:2 (2011), 93–102 (in Russian)]
