For citation:
Komarov D. D. Minimal Edge Extensions of Palm Trees. Izvestiya of Saratov University. Mathematics. Mechanics. Informatics, 2013, vol. 13, iss. 3, pp. 99-104. DOI: 10.18500/1816-9791-2013-13-3-99-104
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.08.2013
Full text:
(downloads: 165)
Language:
Russian
Heading:
UDC:
519.17
Minimal Edge Extensions of Palm Trees
Autors:
Komarov Dmitrii Dmitrievich, Saratov State University
Abstract:
Minimal edge extension of graphs can be regarded as a model of optimal edge fault tolerant implementation of a system. The problem of finding the minimal edge extensions of an arbitrary graph is NP-complete, that’s why it is of interest to find classes of graphs for which it is possible to build a minimal edge extension analytically. This paper is about of the one-edge extensions of a graphs from a special class named palm trees. In this paper presents a kind of one-edge extension for some palm trees and the proof that it is minimal.
Key words:
References:
- Harary F., Hayes J. P. Edge fault tolerance in graphs. Networks, 1993, no. 23, pp. 135–142.
- Abrosimov M. B. Complexity of some problems associated with the extension of graphs. Math. Notes, 2010, vol. 88, no. 5, pp. 643–650.
- Bogomolov A. M., Saliy V. N. Algebraicheskie osnovy teorii diskretnykh sistem [Algebraic foundations of the theory of discrete systems]. Moscow, Nauka, 1997, 368 p. (in Russian).
Received:
19.02.2013
Accepted:
18.07.2013
Published:
30.08.2013
Short text (in English):
(downloads: 65)
- 852 reads