Для цитирования:
Абросимов М. Б. О нижней оценке числа ребер минимального реберного 1-расширения сверхстройного дерева // Известия Саратовского университета. Новая серия. Серия: Математика. Механика. Информатика. 2011. Т. 11, вып. 3, ч. 2. С. 111-117. DOI: 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-расширения произвольного сверхстройного дерева и указывается семейство деревьев, на которых эта оценка достигается.
- Hayes J. P. A graph model for fault-tolerant computing system // IEEE Trans. Comput. 1976. Vol. 25. No 9. P. 875–884.
- Harary F., Hayes J. P. Edge fault tolerance in graphs // Networks. 1993. Vol. 23. P. 135–142.
- Harary F., Hayes J. P. Node fault tolerance in graphs // Networks. 1996. Vol. 27. P. 19–23.
- Harary F., Khurum M. One node fault tolerance for caterpillars and starlike trees // Internet J. Comput. Math. 1995. Vol. 56. P. 135–143.
- Кабанов М. А. Об отказоустойчивых реализациях графов // Теоретические задачи информатики и ее приложений. Саратов, 1997. Вып.1. С. 50–58.
- Абросимов М. Б. Минимальные расширения графов // Новые информационные технологии в исследовании дискретных структур. Томск, 2000. С. 59–64.
- Минимальные реберные расширения сверхстройных деревьев с малым числом вершин / М.Б. Абросимов, Д. Д. Комаров; Саратов. гос. ун-т. Саратов, 2010. 27 с. Деп. в ВИНИТИ 18.10.2010, No 589-В2010.
- Абросимов М. Б. О сложности некоторых задач, связанных с расширениями графов // Мат. заметки. 2010. Т. 88, No 5. С. 643–650.
- Богомолов А. М., Салий В. Н. Алгебраические основы теории дискретных систем. М., 1997. 368 с.
- Sloane N. J. A., Plouffe S. The Encyclopedia of Integer Sequences. San Diego, 1995. 587 p.
- Абросимов М. Б. Минимальные расширения неориентированных звезд // Теоретические проблемы информатики и ее приложений. Саратов, 2006. Вып. 7. С. 3–5.
- 1155 просмотров