Regular vertex 1-extension for 2-di-mension meshes | Applied Discrete Mathematics. Supplement. 2021. № 14. DOI: 10.17223/2226308X/14/36

Regular vertex 1-extension for 2-di-mension meshes

In the paper, a schema of vertex 1-extension for 2-dimensional mesh is proposed. The extension is 4-regular graph. The schema can be applied to meshes n х m, n 2 and m 2. The extension is minimal for some meshes. Some extensions made by schema are not minimal. An example of such mesh is given.

Download file

Counter downloads: 24

Keywords

graph, mesh, fault tolerance, vertex extension

Authors

Name	Organization	E-mail
Lobov A.A.	Saratov National Research State University named after N.G. Chernyshevsky	aisanekai@mail.ru
Abrosimov M. B.	Saratov National Research State University named after N.G. Chernyshevsky	mic@rambler.ru

Всего: 2

References

Камил И. А. К. Вычислительный эксперимент по построению отказоустойчивых реализаций графов с числом вершин до 9 // Intern. J. Open Inform. Technol. 2020. V. 8. No. 9. P. 43-47.

Каравай М. Ф. Минимизированное вложение произвольных гамильтоновых графов в отказоустойчивый граф и реконфигурация при отказах. II. Решетки и k-отказоустойчивость // Автоматика и телемеханика. 2005. №2. С. 175-189.

Каравай М. Ф. Минимизированное вложение произвольных гамильтоновых графов в отказоустойчивый граф и реконфигурация при отказах. I // Автоматика и телемеханика. 2004. № 12. С. 159-178.

Абросимов М.Б. О сложности некоторых задач, связанных с расширениями графов // Матем. заметки. 2010. № 5(88). С. 643-650.

Harary F. and Hayes J. P. Node fault tolerance in graphs // Networks. 1996. V. 27. P. 19-23.

Hayes J. P. A graph model for fault-tolerant computing system // IEEE Trans. Comput. 1976. No. 9. P. 875-884.

Абросимов М. Б. Графовые модели отказоустойчивости. Саратов: Изд-во Сарат. ун-та, 2012.