Рубрика: 

Характеризация орграфов с малым числом дополнительных дуг минимального вершинного 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)]

 

Краткое содержание (на английском языке):