Izvestiya of Saratov University. Mathematics. Mechanics. Informatics, Tome 15 (2015) no. 3, pp. 330-339
Citer cet article
D. Yu. Osipov. T-irreducible extensions for starlike trees. Izvestiya of Saratov University. Mathematics. Mechanics. Informatics, Tome 15 (2015) no. 3, pp. 330-339. http://geodesic.mathdoc.fr/item/ISU_2015_15_3_a11/
@article{ISU_2015_15_3_a11,
author = {D. Yu. Osipov},
title = {T-irreducible extensions for starlike trees},
journal = {Izvestiya of Saratov University. Mathematics. Mechanics. Informatics},
pages = {330--339},
year = {2015},
volume = {15},
number = {3},
language = {ru},
url = {http://geodesic.mathdoc.fr/item/ISU_2015_15_3_a11/}
}
TY - JOUR
AU - D. Yu. Osipov
TI - T-irreducible extensions for starlike trees
JO - Izvestiya of Saratov University. Mathematics. Mechanics. Informatics
PY - 2015
SP - 330
EP - 339
VL - 15
IS - 3
UR - http://geodesic.mathdoc.fr/item/ISU_2015_15_3_a11/
LA - ru
ID - ISU_2015_15_3_a11
ER -
%0 Journal Article
%A D. Yu. Osipov
%T T-irreducible extensions for starlike trees
%J Izvestiya of Saratov University. Mathematics. Mechanics. Informatics
%D 2015
%P 330-339
%V 15
%N 3
%U http://geodesic.mathdoc.fr/item/ISU_2015_15_3_a11/
%G ru
%F ISU_2015_15_3_a11
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.
[1] Bogomolov A. M., Salii V. N., Algebraic foundations of the theory of discrete systems, Nauka, M., 2009 (in Russian) | MR
[2] Kurnosova S. G., “T-irreducible extensions for some classes graphs”, Theoretical Problems of Informatics and its applications, 6, Saratov Univ. Press, Saratov, 2004, 113–125 (in Russian)
[3] Harary F., Khurum M., “One node fault tolerance for caterpillars and starlike trees”, Internet J. Comput. Math., 6 (1995), 135–143 | DOI
[4] Osipov D. Yu., “On a Counterexample for a T-irreducible Extensions of Starlike Trees”, Applied Discrete Mathematics, 2014, no. 3(25), 98–102 (in Russian)
[5] Abrosimov M. B., Graph models of fault tolerance, Saratov Univ. Press, Saratov, 2012, 192 pp. (in Russian)