RUS  ENG
Full version
JOURNALS // Izvestiya of Saratov University. Mathematics. Mechanics. Informatics // Archive

Izv. Saratov Univ. Math. Mech. Inform., 2015 Volume 15, Issue 3, Pages 330–339 (Mi isu600)

Computer Sciences

T-irreducible extensions for starlike trees

D. Yu. Osipov

Saratov State University, 83, Astrakhanskaya st., 410012, Saratov, Russia

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.

Key words: graph, T-irreducible extension, starlike tree, difficult and nondifficult starlike trees.

UDC: 519.17

DOI: 10.18500/1816-9791-2015-15-3-330-339



Bibliographic databases:


© Steklov Math. Inst. of RAS, 2025