Дата публикации: 2020

Дата публикации в реестре: 2020-10-01T12:54:51Z

Аннотация:

Две основные меры связности графа — вершинная к и рёберная А — связаны с минимальной степенью вершины § графа известным соотношением Уитни: к С А С 6. Г. Чартрэнд и Ф. Харари доказали, что этот результат не улучшаем в том смысле, что для любых натуральных чисел a, b, с, таких, что a С b С с, можно построить граф, у которого к = a, А = b, § = c. В доказательстве Чартрэнда и Харари предлагается граф с числом вершин 2(c+1) и числом рёбер c(c+1)+b. В данной работе рассматривается вопрос построения соответствующей реализации с наименьшим возможным числом вершин и рёбер.

Тип: статьи в журналах

Источник: Прикладная дискретная математика. Приложение. 2020. № 13. С. 103-105