Izvestiya of Saratov University.

Mathematics. Mechanics. Informatics

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

For citation:

Komarov D. D. Minimal vertex 1-extensions of palm trees. Izvestiya of Saratov University. Mathematics. Mechanics. Informatics, 2014, vol. 14, iss. 2, pp. 233-241. DOI: 10.18500/1816-9791-2014-14-2-233-241

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: 57)

Minimal vertex 1-extensions of palm trees

Komarov Dmitrii Dmitrievich, Saratov State University

Minimal vertex 1-extension of graphs can be regarded as a model of optimal 1-node fault tolerant implementation of a system. This paper is about of the 1-vertex extensions of a graphs from a special class named palm trees.This article presents a solution to the problem of finding the minimal vertex 1-extension of palm trees with two leafs.

  1. Hayes J. P. A graph model for fault-tolerant computing system. IEEE Trans. Comput., 1976, vol.C.-25, no. 9, pp. 875—884.
  2. Abrosimov M. B. Complexity of some problems associated with the extension of graphs. Math. Notes, 2010, vol. 88, no. 5, pp. 619–625. DOI: 10.1134/S0001434610 110015.
  3. Abrosimov M. B. Graph models of fault tolerance. Saratov, Saratov Univ. Press, 2012, 192 p. (in Russian).
  4. Harary F., Khurum M. One node fault tolerance for caterpillars and starlike trees. Internet J. Comput. Math., 1995, vol. 56, pp. 135—143.
  5. Abrosimov M. B. On the number of additional edges of a minimal vertex 1-extension of a starlike tree. Izv. Saratov Univ. (N. S.), Ser. Math. Mech. Inform., 2012, vol. 12, iss. 2, pp. 103–113 (in Russian).
Short text (in English):
(downloads: 25)