Cite this article as:
Komarov D. . Minimal vertex 1-extensions of palm trees. Izv. Saratov Univ. (N. S.), Ser. Math. Mech. Inform., 2014, vol. 14, iss. 2, pp. 233-241. DOI: https://doi.org/10.18500/1816-9791-2014-14-2-233-241
Language:
Russian
Heading:
UDC:
519.17
Minimal vertex 1-extensions of palm trees
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
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):
45
Full text:
70