Izvestiya of Saratov University.

Mathematics. Mechanics. Informatics

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

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: 
Full text:
(downloads: 107)

Minimal Edge Extensions of Palm Trees

Komarov Dmitrii Dmitrievich, Saratov State University

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.

  1. Harary F., Hayes J. P. Edge fault tolerance in graphs. Networks, 1993, no. 23, pp. 135–142.
  2. Abrosimov M. B. Complexity of some problems associated with the extension of graphs. Math. Notes, 2010, vol. 88, no. 5, pp. 643–650.
  3. 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).
Short text (in English):
(downloads: 33)