Izvestiya of Saratov University.

Mathematics. Mechanics. Informatics

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

For citation:

Abrosimov M. B. On Lower Bound of Edge Number of Minimal Edge 1-Extension of Starlike Tree. Izvestiya of Saratov University. Mathematics. Mechanics. Informatics, 2011, vol. 11, iss. 3, pp. 111-117. DOI: 10.18500/1816-9791-2011-11-3-2-111-117

This is an open access article distributed under the terms of Creative Commons Attribution 4.0 International License (CC-BY 4.0).
Published online: 
31.08.2011
Full text:
download
(downloads: 220)
Language: 
Russian
Heading: 
Computer Sciences
UDC: 
519.17
DOI: 
10.18500/1816-9791-2011-11-3-2-111-117

On Lower Bound of Edge Number of Minimal Edge 1-Extension of Starlike Tree

Autors: 
Abrosimov Mikhail Borisovich, Saratov State University
Abstract: 

For a given graph G with n nodes, we say that graph G∗ is its 1-edge extension if for each edge e of G∗ the subgraph G∗ −e contains graph G up to isomorphism. Graph G∗ is minimal 1-edge extension of graph G if G∗ has n nodes and there is no 1-edge extension with n nodes of graph G having fewer edges than G. A tree is called starlike if it has exactly one node of degree greater than two. We give a lower bound of edge number of minimal edge 1-extension of starlike tree and provide family on which this bound is achieved.

Key words: 
minimal edge extension
starlike tree
fault tolerance
References: 
  1. Hayes J. P. A graph model for fault-tolerant computing system // IEEE Trans. Comput. 1976. Vol. 25. No 9. P. 875–884.
  2. Harary F., Hayes J. P. Edge fault tolerance in graphs // Networks. 1993. Vol. 23. P. 135–142.
  3. Harary F., Hayes J. P. Node fault tolerance in graphs // Networks. 1996. Vol. 27. P. 19–23.
  4. Harary F., Khurum M. One node fault tolerance for caterpillars and starlike trees // Internet J. Comput. Math. 1995. Vol. 56. P. 135–143.
  5. Кабанов М. А. Об отказоустойчивых реализациях графов // Теоретические задачи информатики и ее приложений. Саратов, 1997. Вып.1. С. 50–58.
  6. Абросимов М. Б. Минимальные расширения графов // Новые информационные технологии в исследовании дискретных структур. Томск, 2000. С. 59–64.
  7. Минимальные реберные расширения сверхстройных деревьев с малым числом вершин / М.Б. Абросимов, Д. Д. Комаров; Саратов. гос. ун-т. Саратов, 2010. 27 с. Деп. в ВИНИТИ 18.10.2010, No 589-В2010.
  8. Абросимов М. Б. О сложности некоторых задач, связанных с расширениями графов // Мат. заметки. 2010. Т. 88, No 5. С. 643–650.
  9. Богомолов А. М., Салий В. Н. Алгебраические основы теории дискретных систем. М., 1997. 368 с.
  10. Sloane N. J. A., Plouffe S. The Encyclopedia of Integer Sequences. San Diego, 1995. 587 p.
  11. Абросимов М. Б. Минимальные расширения неориентированных звезд // Теоретические проблемы информатики и ее приложений. Саратов, 2006. Вып. 7. С. 3–5.
  • 1154 reads