Структура та екстремальні властивості графів з парними відстанями між точками не з'єднання
by
ONLINE
Доповідь присвячена графам з умовами на парність відстаней між точками з'єднання та точками не з'єднання. Раніше авторами було показано, що графи з непарними відстанями між точками не з'єднання (NCO-графи) є реберними графами сильних унікальних незалежних дерев (SUIT), а графи з парними відстанями між ними (NCE-графи) є двочастковими графами, у яких усі точки не з'єднання лежать в одній частці. У даній доповіді за аналогією розглянуто блокову структуру цих класів: доведено, що для довільного графа блоків існує NCE-граф з таким самим графом блоків, а граф можна підрозбити до NCE-графа тоді й лише тоді, коли його точки не з'єднання утворюють незалежну множину. Також розглянуто слабкі версії цих класів і графи з непарними відстанями між точками з'єднання та не з'єднання (CNCO-графи). Для останніх використано підхід знакових графів: CNCO-граф характеризується тим, що кожен породжений шлях довжини два має ребра з однаковим знаком, а множина точок з'єднання є незалежною. На завершення, використовуючи ці результати, розв'язано екстремальні задачі. Показано, що мінімальні NCE-графи є в точності SUIT, доведено точну верхню оцінку на кількість ребер та охарактеризовано максимальні NCE-графи.
Покликання:
https://bbb.imath.kiev.ua/rooms/rac-2gs-3gk-zzl/join