Для цитирования:
Абросимов М. Б. О числе дополнительных ребер минимального вершинного 1-расширения сверхстройного дерева // Известия Саратовского университета. Новая серия. Серия: Математика. Механика. Информатика. 2012. Т. 12, вып. 2. С. 103-113. DOI: 10.18500/1816-9791-2012-12-2-103-113
О числе дополнительных ребер минимального вершинного 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, № 9. P. 875–884.
- Harary F., Hayes J. P. Node fault tolerance in graphs // Networks. 1996. Vol. 27. P. 19–23.
- Harary F., Hayes J. P. Edge fault tolerance in graphs // Networks. 1993. Vol. 23. P. 135–142.
- Harary F., Khurum M. One node fault tolerance for caterpillars and starlike trees // Intern. J. Comput. Math. 1995. Vol. 56. P. 135–143.
- Кабанов М. А. Об отказоустойчивых реализациях графов // Теоретические задачи информатики и ее приложений. Саратов, 1997. Вып. 1. С. 50–58.
- Абросимов М. Б. Минимальные расширения графов // Новые информационные технологии в исследовании дискретных структур. Томск, 2000. С. 59–64.
- Абросимов М. Б., Комаров Д. Д. Минимальные вершинные расширения сверхстройных деревьев с малым числом вершин / Сарат. гос. ун-т. Саратов, 2010. 38 с. Деп. в ВИНИТИ 18.10.2010, № 590-В2010.
- Абросимов М. Б. О сложности некоторых задач, связанных с расширениями графов // Мат. заметки. 2010. Т. 88, № 5. С. 643–650.
- Абросимов М. Б. О нижней оценке числа ребер минимального реберного 1-расширения сверхстройного дерева // Изв. Сарат. ун-та. Нов. сер. 2011. Т. 11. Сер. Математика. Механика. Информатика, вып. 3, ч. 2. С. 111–117.
- Богомолов А. М., Салий В. Н. Алгебраические основы теории дискретных систем. М., 1997. 368 с.
- Абросимов М. Б. Минимальные расширения неориентированных звезд // Теоретические проблемы информатики и ее приложений. Саратов, 2006. Вып. 7. С. 3–5
- 1184 просмотра