Cite this article as:
Осипов Д. Ю. T-irreducible extension for union of paths and cycles . Izv. Saratov Univ. (N. S.), Ser. Math. Mech. Inform., 2013, vol. 13, iss. 2, pp. 100-105. DOI: https://doi.org/10.18500/1816-9791-2013-13-2-1-100-105
T-irreducible extension for union of paths and cycles
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.
1. Bogomolov A. M., Salii V. N. Algebraicheskie osnovy
teorii diskretnykh sistem [Algebraic foundations of the
theory of discrete systems]. Moscow, Nauka, 1997, 368 p.
(in Russian).
2. Hayes P. A graph model for fault-tolerant computing
system. IEEE Trans. Comput., 1976, vol. 25, pp. 875–884.
3. Abrosimov M. B. Minimal’nye rasshireniia ob"edineniia
nekotorykh grafov [Minimal extensions for union of
some graphs. Teoreticheskie problemy informatiki i ee
prilozhenii [Theoretical Problems of Informatics and its
applications]. Saratov, 2001, iss. 4, pp. 3–11 (in Russian).
4. Salii V. N. Zero knowledge proofs in problems on
extensions of graphs. Vestnik Tomskogo Gos. Univ.,
2001, iss. 6, pp. 63–65 (in Russian).
5. Kurnosova S. G. T-neprivodimye rasshireniia dlia
nekotorykh klassov grafov [T-irreducible extensions
for some classes graphs]. Teoreticheskie problemy
informatiki i ee prilozhenii [Theoretical Problems of
Informatics and its applications]. Saratov, 2004, iss. 6,
pp. 113–125 (in Russian).
6. Osipov D. Yu. T-neprivodimye rasshireniia dlia ob"edineniia
tsepei i tsiklov [T-irreducible extensions for
union of paths and cycles]. Komp’iuternye nauki i
informatsionnye tekhnologii. Saratov, 2012, pp. 245–246
(in Russian).
