In 2001, it was conjectured that the minimal vertex 1-extension ofa graph G + G*, where G* is a minimal vertex 1-extension of graph G, is unique upto isomorphism and has the form G* + G*. We construct two counterexamples to thisconjecture showing that, in general, it is wrong. Also, we show that the statement is truefor many graphs.
Download file
Counter downloads: 76
- Title On minimal vertex 1-extensions of special type graph union
- Headline On minimal vertex 1-extensions of special type graph union
- Publesher
Tomsk State University - Issue Prikladnaya Diskretnaya Matematika - Applied Discrete Mathematics 4(14)
- Date:
- DOI
Keywords
fault tolerance, exact vertex extension, graph, minimal vertex extension, оптимальная отказоустойчивая реализация, предполный граф, точное вершинное 1-расширение, минимальное вершинное 1-расширение, графAuthors
References
Абросимов М. Б. Минимальные вершинные расширения 4-, 5-, 6- и 7-вершинных графов. Саратов: СГУ, 2000. 26 с. Деп. в ВИНИТИ 06.09.2000, №2352 В00.
Абросимов М. Б. Минимальные расширения графов: автореф. дис. ... канд. физ.-мат. наук. Саратов: СГУ, 2001. 16 с.
Harary F. and Hayes J. P. Node fault tolerance in graphs // Networks. 1996. V. 27. P. 19-23.
Абросимов М. Б. Минимальные расширения дополнений графов // Теоретические задачи информатики и ее приложений. Саратов: Изд-во Сарат. ун-та, 2001. Вып. 4. С. 11-19.
Абросимов М. Б. Минимальные k-расширения предполных графов // Изв. вузов. Математика. 2003. №6(493). С. 3-11.
Абросимов М. Б. О сложности некоторых задач, связанных с расширениями графов // Матем. заметки. 2010. №5(88). С. 643-650.
Hayes J. P. A graph model for fault-tolerant computing system // IEEE Trans. Comput. 1976. V.C.25. No. 9. P. 875-884.
Богомолов А. М., Салий В. Н. Алгебраические основы теории дискретных систем. М.: Наука, 1997.
On minimal vertex 1-extensions of special type graph union | Prikladnaya Diskretnaya Matematika - Applied Discrete Mathematics. 2011. № 4(14).
Download full-text version
Download fileCounter downloads: 211