For citation:
Osipov D. Y. T-irreducible extension for union of paths and cycles. Izvestiya of Saratov University. Mathematics. Mechanics. Informatics, 2013, vol. 13, iss. 2, pp. 100-105. DOI: 10.18500/1816-9791-2013-13-2-1-100-105, EDN: SJJBAH
This is an open access article distributed under the terms of Creative Commons Attribution 4.0 International License (CC-BY 4.0).
Published online:
27.02.2013
Full text:
(downloads: 179)
Language:
Russian
Heading:
UDC:
519.17
EDN:
SJJBAH
T-irreducible extension for union of paths and cycles
Autors:
Osipov Dmitrii Yur'evich, Saratov State University
Abstract:
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.
References:
- 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).
- Hayes P. A graph model for fault-tolerant computing system. IEEE Trans. Comput., 1976, vol. 25, pp. 875–884.
- 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).
- Salii V. N. Zero knowledge proofs in problems on extensions of graphs. Vestnik Tomskogo Gos. Univ., 2001, iss. 6, pp. 63–65 (in Russian).
- 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).
- 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).
Received:
15.08.2012
Accepted:
20.01.2013
Published:
27.02.2013
Short text (in English):
(downloads: 70)
- 1093 reads