Известия Саратовского университета. Новая серия.

Серия Математика. Механика. Информатика

ISSN 1816-9791 (Print)
ISSN 2541-9005 (Online)


Для цитирования:

Абросимов М. Б. Характеризация орграфов с малым числом дополнительных дуг минимального вершинного 1-расширения // Известия Саратовского университета. Новая серия. Серия: Математика. Механика. Информатика. 2013. Т. 13, вып. 2, ч. 2. С. 3-9. DOI: 10.18500/1816-9791-2013-13-2-2-3-9, EDN: RHABFJ

Статья опубликована на условиях лицензии Creative Commons Attribution 4.0 International (CC-BY 4.0).
Опубликована онлайн: 
25.05.2013
Полный текст:
(downloads: 188)
Язык публикации: 
русский
Рубрика: 
УДК: 
519.17
EDN: 
RHABFJ

Характеризация орграфов с малым числом дополнительных дуг минимального вершинного 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)]
Поступила в редакцию: 
10.11.2012
Принята к публикации: 
17.04.2013
Опубликована: 
31.05.2013
Краткое содержание:
(downloads: 108)