|
Эта публикация цитируется в 1 научной статье (всего в 1 статье)
Прикладная теория кодирования, автоматов и графов
О минимальном рёберном $1$-расширении гиперкуба
А. А. Лобов, М. Б. Абросимов Саратовский национальный исследовательский государственный университет им. Н. Г. Чернышевского, г. Саратов
Аннотация:
Граф $G^*$ с $n$ вершинами называется минимальным рёберным $k$-расширением $n$-вершинного графа $G$, если $G$ вкладывается в каждый граф, получающийся из $G^*$ удалением любых его $k$ рёбер, и $G^*$ имеет при этом минимально возможное число рёбер. Гиперкуб $Q_n$ – это регулярный $2^n$-вершинный граф порядка $n$, представляющий собой декартово произведение $n$ полных $2$-вершинных графов $K_2$. Предлагается семейство графов $Q^*_n$, представители которого при $n>1$ являются минимальными рёберными $1$-расширениями соответствующих гиперкубов. Вычислительный эксперимент показывает, что при $n\leq4$ эти расширения являются единственными с точностью до изоморфизма.
Ключевые слова:
граф, гиперкуб, рёберная отказоустойчивость, минимальное рёберное $1$-расширение.
Образец цитирования:
А. А. Лобов, М. Б. Абросимов, “О минимальном рёберном $1$-расширении гиперкуба”, ПДМ. Приложение, 2018, № 11, 109–111
Образцы ссылок на эту страницу:
https://www.mathnet.ru/rus/pdma392 https://www.mathnet.ru/rus/pdma/y2018/i11/p109
|
|