Izvestiya of Saratov University.

Mathematics. Mechanics. Informatics

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


For citation:

Abrosimov M. B. О числе дополнительных ребер минимального вершинного 1-расширения сверхстройного дерева. Izvestiya of Saratov University. Mathematics. Mechanics. Informatics, 2012, vol. 12, iss. 2, pp. 103-113. DOI: 10.18500/1816-9791-2012-12-2-103-113

This is an open access article distributed under the terms of Creative Commons Attribution 4.0 International License (CC-BY 4.0).
Published online: 
21.05.2012
Full text:
(downloads: 144)
Language: 
Russian
Heading: 
UDC: 
519.17

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

Autors: 
Abrosimov Mikhail Borisovich, Saratov State University
Abstract: 

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

References: 
  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