Известия Саратовского университета. Новая серия.

Серия Математика. Механика. Информатика

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


Для цитирования:

Лобов А. А., Абросимов М. Б. Вершинные расширения 4-слойных графов и гиперкубов // Известия Саратовского университета. Новая серия. Серия : Математика. Механика. Информатика. 2022. Т. 22, вып. 4. С. 536-548. DOI: 10.18500/1816-9791-2022-22-4-536-548

Статья опубликована на условиях лицензии Creative Commons Attribution 4.0 International (CC-BY 4.0).
Опубликована онлайн: 
30.11.2022
Полный текст:
(downloads: 153)
Язык публикации: 
русский
Рубрика: 
Тип статьи: 
Научная статья
УДК: 
519.17
EDN: 
BHQKFP

Вершинные расширения 4-слойных графов и гиперкубов

Авторы: 
Лобов Александр Андреевич, Саратовский национальный исследовательский государственный университет имени Н. Г. Чернышевского
Абросимов Михаил Борисович, Саратовский национальный исследовательский государственный университет имени Н. Г. Чернышевского
Аннотация: 

Дж. П. Хейз предложил математическую модель отказоустойчивых реализаций технических систем на основе графов, которой в более абстрактном виде соответствуют вершинные и рёберные расширения графов. Граф $G^*$ называется вершинным $k$"-расширением графа $G$, если граф $G$ вкладывается в каждый граф, полученный из $G^*$ удалением любых $k$ вершин. Если никакая собственная часть графа $G^*$ не является вершинным $k$-расширением графа $G$, то расширение $G^*$ называется неприводимым. Если вершинное $k$-расширение имеет минимально возможное число вершин и рёбер, то оно называется минимальным. Задача поиска минимальных расширений для произвольного графа является вычислительно сложной. Только для некоторых классов графов удалось найти частичное или полное описание их минимальных вершинных расширений. В данной работе предложена общая схема построения вершинных 1- и 2-расширений для почти всех двудольных графов, в том числе и для гиперкубов. Гиперкуб является интересным графом с точки зрения его свойств и возможности использования в качестве топологии вычислительной системы. Минимальные вершинные расширения для гиперкубов неизвестны. На практике используются тривиальные 1-расширения, которые получаются добавлением одной вершины и соединением её со всеми остальными. Неприводимое 1-расширение для 16-вершинного гиперкуба, которое предлагается в данной работе, содержит на одно ребро меньше, чем тривиальное 1-расширение. Также в статье определяется количество неизоморфных расширений для каждого гиперкуба, которые можно построить с использованием предложенных схем, и доказывается неприводимость вершинных 1-расширений гиперкуба.

Благодарности: 
Работа выполнена при поддержке Минобрнауки России в рамках выполнения государственного задания (проект № FSRR-2020-0006).
Список источников: 
  1. Богомолов А. М., Салий В. Н. Алгебраические основы теории дискретных систем. Москва : Физматлит, 1997. 368 с. EDN: XYCVTZ
  2. Абросимов М. Б. Графовые модели отказоустойчивости. Саратов : Изд-во Саратовского ун-та, 2012. 192 с. EDN: QMXQLB
  3. Hayes J. P. A graph model for fault-tolerant computing system // IEEE Transactions on Computers. 1976. Vol. C-25, № 9. P. 875–884. https://doi.org/10.1109/TC.1976.1674712
  4. Harary F., Hayes J. P. Edge fault tolerance in graphs // Networks. 1993. Vol. 23, iss. 2. P. 135–142. https://doi.org/10.1002/net.3230230207
  5. Harary F., Hayes J. P. Node fault tolerance in graphs // Networks. 1996. Vol. 27, iss. 1. P. 19–23. https://doi.org/10.1002/(SICI)1097-0037(199601)27:1<19::AID-NET2>3.0.CO;2-H
  6. Абросимов М. Б. О сложности некоторых задач, связанных с расширениями графов // Математические заметки. 2010. Т. 88, вып. 5. С. 643–650. https://doi.org/10.4213/mzm8403, EDN: RLRFEF
  7. Абросимов М. Б., Камил Ихаб А. К., Лобов А. А. Построение всех неизоморфных минимальных вершинных расширений графа методом канонических представителей // Известия Саратовского университета. Новая серия. Серия: Математика. Механика. Информатика. 2019. Т. 19, вып. 4. С. 479–486. https://doi.org/10.18500/1816-9791-2019-19-4-479-486, EDN: YXOMDX
  8. Абросимов М. Б., Судани Х. Х. К., Лобов А. А. Построение минимальных рёберных расширений графа без проверки на изоморфизм // Известия Саратовского университета. Новая серия. Серия: Математика. Механика. Информатика. 2020. Т. 20, вып. 1. С. 105–115. https://doi.org/10.18500/1816-9791-2020-20-1-105-115, EDN: PXDRGJ
  9. Harary F., Hayes J. P., Wu H.-J. A survey of the theory of hypercube graphs // Computers & Mathematics with Applications. 1988. Vol. 15, iss. 4. P. 277–289. https://doi.org/10.1016/0898-1221(88)90213-1
  10. Biggs N. L. Distance-transitive graphs // Algebraic Graph Theory. Cambridge : Cambridge University Press, 1974. P. 155–163. https://doi.org/10.1017/CBO9780511608704.021 
Поступила в редакцию: 
23.07.2022
Принята к публикации: 
18.08.2022
Опубликована: 
30.11.2022