For citation:
Osipov D. Y. T-irreducible Extensions for Starlike Trees. Izvestiya of Saratov University. Mathematics. Mechanics. Informatics, 2015, vol. 15, iss. 3, pp. 330-339. DOI: 10.18500/1816-9791-2015-15-3-330-339, EDN: UKIVHD
T-irreducible Extensions for Starlike Trees
We deal with a sort of optimal extensions of graphs, so called T-irreducible extensions. T-irreducible extension of a graph G is an extension of G obtained by removing a maximal set of edges from the trivial extension of G. A difficult starlike tree is a starlike tree that has at least one difficult node. T-irreducible extensions for nondifficult starlike trees were constructed by M. B. Abrosimov, T-irreducible extensions for palms (one of subclasses of starlike trees) were constructed by S. G. Kurnosova. Counterexamples were found to a method of Harary and Khurum, who tried to construct possible T-irreducible extensions for starlike trees. T-irreducible extensions for difficult starlike trees are constructed.
- Богомолов А. М., Салий В. Н. Алгебраические основы теории дискретных систем. М. : Наука, 2009.
- Курносова С. Г. Т-неприводимые расширения для некоторых классов графов // Теоретические проблемы информатики и ее приложений. Саратов : Изд-во Сарат. ун-та, 2004. Вып. 6. С. 113–125.
- Harary F., Khurum M. One node fault tolerance for caterpillars and starlike trees // Internet J. Comput. Math. 1995. Vol. 6. P. 135–143.
- Осипов Д. Ю. Об одном контрпримере для Т-неприводимых расширений сверхстройных деревьев // Прикладная дискретная математика. 2014. № 3(25). С. 98–102.
- Абросимов М. Б. Графовые модели отказоустойчивости. Саратов : Изд-во Сарат. ун-та, 2012. 192 с.
- 1013 reads