Izvestiya of Saratov University.

Mathematics. Mechanics. Informatics

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


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

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

T-irreducible Extensions for Starlike Trees

Autors: 
Osipov Dmitrii Yur'evich, Saratov State University
Abstract: 

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.

References: 
  1. Богомолов А. М., Салий В. Н. Алгебраические основы теории дискретных систем. М. : Наука, 2009.
  2. Курносова С. Г. Т-неприводимые расширения для некоторых классов графов // Теоретические проблемы информатики и ее приложений. Саратов : Изд-во Сарат. ун-та, 2004. Вып. 6. С. 113–125.
  3. Harary F., Khurum M. One node fault tolerance for caterpillars and starlike trees // Internet J. Comput. Math. 1995. Vol. 6. P. 135–143.
  4. Осипов Д. Ю. Об одном контрпримере для Т-неприводимых расширений сверхстройных деревьев // Прикладная дискретная математика. 2014. № 3(25). С. 98–102.
  5. Абросимов М. Б. Графовые модели отказоустойчивости. Саратов : Изд-во Сарат. ун-та, 2012. 192 с.
Received: 
25.04.2015
Accepted: 
27.08.2015
Published: 
30.09.2015