О минимальном реберном 1-расширении гиперкуба А. А. Лобов, М. Б. Абросимов
Material type: ArticleSubject(s): графы | гиперкубы | реберные графы | отказоустойчивость | минимальное реберное 1-расширениеGenre/Form: статьи в журналах Online resources: Click here to access online In: Прикладная дискретная математика. Приложение № 11. С. 109-111Abstract: Граф G* с n вершинами называется минимальным рёберным k-расширением n-вершинного графа G, если G вкладывается в каждый граф, получающийся из G* удалением любых его k рёбер, и G* имеет при этом минимально возможное число рёбер. Гиперкуб Qn — это регулярный 2” -вершинный граф порядка n, представляющий собой декартово произведение n полных 2-вершинных графов K2. Предлагается семейство графов Qn, представители которого при n > 1 являются минимальными рёберными 1-расширениями соответствующих гиперкубов. Вычислительный эксперимент показывает, что при n ^ 4 эти расширения являются единственными с точностью до изоморфизма.Библиогр.: 7 назв.
Граф G* с n вершинами называется минимальным рёберным k-расширением n-вершинного графа G, если G вкладывается в каждый граф, получающийся из G* удалением любых его k рёбер, и G* имеет при этом минимально возможное число рёбер. Гиперкуб Qn — это регулярный 2” -вершинный граф порядка n, представляющий собой декартово произведение n полных 2-вершинных графов K2. Предлагается семейство графов Qn, представители которого при n > 1 являются минимальными рёберными 1-расширениями соответствующих гиперкубов. Вычислительный эксперимент показывает, что при n ^ 4 эти расширения являются единственными с точностью до изоморфизма.
There are no comments on this title.