Т-неприводимое расширение

T-irreducible Extensions for Starlike Trees

Authors: Osipov D. Y.

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.

T-irreducible extension for union of paths and cycles

Authors: Osipov D. Y.

 A graphH with nodes is an extension of a graph G with nnodes if each maximal subgraph of H contains G. Trivial extension of a graph G is the connection of graph G and the singleton graph (i.e. we add one node to the graph G and this node join with each node of G). T-irreducible extension of graph G is an extension of the graph G which is obtained by removing maximal set of edges from the trivial extension of G. One of T-irreducible extensions is constructed for an arbitrary union of cycles and paths.