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

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

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


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

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

Статья опубликована на условиях лицензии Creative Commons Attribution 4.0 International (CC-BY 4.0).
Опубликована онлайн: 
31.08.2011
Полный текст:
(downloads: 220)
Язык публикации: 
русский
Рубрика: 
УДК: 
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. No 9. P. 875–884.
  2. Harary F., Hayes J. P. Edge fault tolerance in graphs // Networks. 1993. Vol. 23. P. 135–142.
  3. Harary F., Hayes J. P. Node fault tolerance in graphs // Networks. 1996. Vol. 27. P. 19–23.
  4. Harary F., Khurum M. One node fault tolerance for caterpillars and starlike trees // Internet J. Comput. Math. 1995. Vol. 56. P. 135–143.
  5. Кабанов М. А. Об отказоустойчивых реализациях графов // Теоретические задачи информатики и ее приложений. Саратов, 1997. Вып.1. С. 50–58.
  6. Абросимов М. Б. Минимальные расширения графов // Новые информационные технологии в исследовании дискретных структур. Томск, 2000. С. 59–64.
  7. Минимальные реберные расширения сверхстройных деревьев с малым числом вершин / М.Б. Абросимов, Д. Д. Комаров; Саратов. гос. ун-т. Саратов, 2010. 27 с. Деп. в ВИНИТИ 18.10.2010, No 589-В2010.
  8. Абросимов М. Б. О сложности некоторых задач, связанных с расширениями графов // Мат. заметки. 2010. Т. 88, No 5. С. 643–650.
  9. Богомолов А. М., Салий В. Н. Алгебраические основы теории дискретных систем. М., 1997. 368 с.
  10. Sloane N. J. A., Plouffe S. The Encyclopedia of Integer Sequences. San Diego, 1995. 587 p.
  11. Абросимов М. Б. Минимальные расширения неориентированных звезд // Теоретические проблемы информатики и ее приложений. Саратов, 2006. Вып. 7. С. 3–5.