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

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