Izvestiya of Saratov University.

Mathematics. Mechanics. Informatics

ISSN 1816-9791 (Print)
ISSN 2541-9005 (Online)

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:
download
(downloads: 154)
Language: 
Russian
Heading: 
Computer Sciences
UDC: 
519.17
DOI: 
10.18500/1816-9791-2013-13-2-1-100-105
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. 

Key words: 
graph
T-irreducible extensions
union of paths and cycles
References: 
  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).
Received: 
15.08.2012
Accepted: 
20.01.2013
Published: 
27.02.2013
Short text (in English):
download
(downloads: 53)
  • 958 reads