|
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.
Citation:
D. Yu. Osipov, “T-irreducible extensions for starlike trees”, Izv. Saratov Univ. Math. Mech. Inform., 15:3 (2015), 330–339
Linking options:
https://www.mathnet.ru/eng/isu600 https://www.mathnet.ru/eng/isu/v15/i3/p330
|
|