UDC: 
519.17
Language: 
English

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

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.

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.

Full text: