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

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

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


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

Абросимов М. Б. О числе дополнительных ребер минимального вершинного 1-расширения сверхстройного дерева // Известия Саратовского университета. Новая серия. Серия: Математика. Механика. Информатика. 2012. Т. 12, вып. 2. С. 103-113. DOI: 10.18500/1816-9791-2012-12-2-103-113

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

О числе дополнительных ребер минимального вершинного 1-расширения сверхстройного дерева

Авторы: 
Абросимов Михаил Борисович, Саратовский национальный исследовательский государственный университет имени Н. Г. Чернышевского
Аннотация: 

Граф G* называется вершинным 1-расширением графа G, если граф G можно вложить в каждый граф, получающийся из графа G* удалением любой его вершины вместе с инцидентными ребрами. Вершинное 1-расширение G* графа G называется минимальным, если граф G* имеет на одну вершину больше, чем граф G, а среди всех вершинных 1-расширений графа G с тем же числом вершин граф G* имеет минимальное число ребер. Дерево называется сверхстройным (звездоподобным), если только одна его вершина имеет степень больше двух. В работе дается нижняя и верхняя оценки числа дополнительных ребер минимального вершинного 1-расширения произвольного сверхстройного дерева и указываются семейства деревьев, на которых эти оценки достигаются. 

Список источников: 
  1. Hayes J. P. A graph model for fault-tolerant computing system // IEEE Trans. Comput. 1976. Vol. 25, № 9. P. 875–884.
  2. Harary F., Hayes J. P. Node fault tolerance in graphs // Networks. 1996. Vol. 27. P. 19–23.
  3. Harary F., Hayes J. P. Edge fault tolerance in graphs // Networks. 1993. Vol. 23. P. 135–142.
  4. Harary F., Khurum M. One node fault tolerance for caterpillars and starlike trees // Intern. J. Comput. Math. 1995. Vol. 56. P. 135–143.
  5. Кабанов М. А. Об отказоустойчивых реализациях графов // Теоретические задачи информатики и ее приложений. Саратов, 1997. Вып. 1. С. 50–58.
  6. Абросимов М. Б. Минимальные расширения графов // Новые информационные технологии в исследовании дискретных структур. Томск, 2000. С. 59–64.
  7. Абросимов М. Б., Комаров Д. Д. Минимальные вершинные расширения сверхстройных деревьев с малым числом вершин / Сарат. гос. ун-т. Саратов, 2010. 38 с. Деп. в ВИНИТИ 18.10.2010, № 590-В2010.
  8. Абросимов М. Б. О сложности некоторых задач, связанных с расширениями графов // Мат. заметки. 2010. Т. 88, № 5. С. 643–650.
  9. Абросимов М. Б. О нижней оценке числа ребер минимального реберного 1-расширения сверхстройного дерева // Изв. Сарат. ун-та. Нов. сер. 2011. Т. 11. Сер. Математика. Механика. Информатика, вып. 3, ч. 2. С. 111–117.
  10. Богомолов А. М., Салий В. Н. Алгебраические основы теории дискретных систем. М., 1997. 368 с.
  11. Абросимов М. Б. Минимальные расширения неориентированных звезд // Теоретические проблемы информатики и ее приложений. Саратов, 2006. Вып. 7. С. 3–5
Поступила в редакцию: 
25.06.2012
Принята к публикации: 
25.06.2012
Опубликована: 
25.07.2012