Образец для цитирования:
Абросимов М. Б. О НИЖНЕЙ ОЦЕНКЕ ЧИСЛА РЕБЕР МИНИМАЛЬНОГО РЕБЕРНОГО 1-РАСШИРЕНИЯ СВЕРХСТРОЙНОГО ДЕРЕВА // Изв. Сарат. ун-та. Нов. сер. Сер. Математика. Механика. Информатика. 2011. Т. 11, вып. 3. С. 111-117. DOI: https://doi.org/10.18500/1816-9791-2011-11-3-2-111-117
О НИЖНЕЙ ОЦЕНКЕ ЧИСЛА РЕБЕР МИНИМАЛЬНОГО РЕБЕРНОГО 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.
