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

Izv. Saratov Univ. Math. Mech. Inform., 2013 Volume 13, Issue 2(1), Pages 100–105 (Mi isu402)

Computer science

T-irreducible extension for union of paths and cycles

D. U. Osipov

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

Abstract: A graph $H$ with $n+1$ nodes is an extension of a graph $G$ with $n$ nodes 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.

Key words: graph, T-irreducible extensions, union of paths and cycles.

UDC: 519.17

DOI: 10.18500/1816-9791-2013-13-2-1-100-105



Bibliographic databases:


© Steklov Math. Inst. of RAS, 2025