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, EDN: SHHIGN
This is an open access article distributed under the terms of Creative Commons Attribution 4.0 International License (CC-BY 4.0).
Published online:
09.06.2014
Full text:
(downloads: 149)
Language:
Russian
Heading:
UDC:
519.17
EDN:
SHHIGN
Minimal vertex 1-extensions of palm trees
Autors:
Komarov Dmitrii Dmitrievich, Saratov State University
Abstract:
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.
References:
- Hayes J. P. A graph model for fault-tolerant computing system. IEEE Trans. Comput., 1976, vol.C.-25, no. 9, pp. 875—884.
- 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.
- Abrosimov M. B. Graph models of fault tolerance. Saratov, Saratov Univ. Press, 2012, 192 p. (in Russian).
- Harary F., Khurum M. One node fault tolerance for caterpillars and starlike trees. Internet J. Comput. Math., 1995, vol. 56, pp. 135—143.
- 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).
Received:
10.11.2014
Accepted:
21.04.2014
Published:
30.05.2014
Short text (in English):
(downloads: 67)
- 845 reads