Число независимой связности в графах при ограничениях на обхват

Основная информация

• ID статьи: 2411.01687
• Название: Independent Bondage Number in Graphs under Girth Constraints
• Авторы: E.G.K.M. Gamlath, Andrew Pham, Bing Wei
• Классификация: math.CO (комбинаторная математика)
• Дата публикации: 15 октября 2025 г. (препринт arXiv)
• Ссылка на статью: https://arxiv.org/abs/2411.01687

Аннотация

Для конечного простого графа $G$ число независимой связности (independent bondage number) графа $G$ определяется как минимальный размер множества рёбер, удаление которых приводит к графу со строго большим числом независимого доминирования, чем у графа $G$. Хотя число связности графов при ограничениях на обхват уже изучалось, результаты для числа независимой связности остаются весьма ограниченными. В данном исследовании устанавливаются верхние границы числа независимой связности плоских графов при заданных ограничениях на обхват, расширяя результаты Фишермана, Раутенбаха и Фольцманна о числе связности, а также результаты Бородина и Ивановой о структуре плоских графов. В частности, выявляются дополнительные структурные конфигурации и устанавливаются границы числа независимой связности для плоских графов, удовлетворяющих условиям $\delta(G) \geq 2$ и $g(G) \geq 5$, $\delta(G) \geq 3$ и $g(G) \geq 4$, а также $\delta(G) \geq 2$ и $g(G) \geq 10$.

Исследовательский контекст и мотивация

Определение проблемы и её значимость

1. Основные концепции:
   • Множество независимого доминирования: множество вершин, которое одновременно является независимым множеством и доминирующим множеством
   • Число независимого доминирования $\gamma_i(G)$: мощность минимального множества независимого доминирования
   • Число независимой связности $b_i(G)$: минимальный размер множества рёбер $B$ такого, что $\gamma_i(G-B) > \gamma_i(G)$
2. Научная значимость:
   • Измеряет уязвимость структуры независимого доминирования сети при отказе рёбер
   • Имеет важное прикладное значение при анализе отказов каналов связи в взаимосвязанных сетях
   • Расширяет область исследований классической теории доминирования
3. Ограничения существующих исследований:
   • Традиционное число связности $b(G)$ систематически изучалось при ограничениях на обхват
   • Результаты, касающиеся числа независимой связности $b_i(G)$, крайне ограничены, особенно при ограничениях на обхват
   • Отсутствуют результаты о постоянных верхних границах для конкретных классов графов
4. Мотивация исследования:
   • Вдохновлено результатами Фишермана и др. (2003) о числе связности плоских графов при ограничениях на обхват
   • Естественное исследование того, может ли число независимой связности также достичь аналогичных постоянных верхних границ при ограничениях на обхват
   • Заполнение пробела в теории числа независимой связности

Основные вклады

1. Установлены четыре основные теоремы о постоянных верхних границах:
   • При $\delta(G) \geq 3$ и $g(G) \geq 4$: $b_i(G) \leq 6$
   • При $\delta(G) \geq 2$ и $g(G) \geq 5$: $b_i(G) \leq 5$
   • При $\delta(G) \geq 2$ и $g(G) \geq 7$: $b_i(G) \leq 4$
   • При $\delta(G) \geq 2$ и $g(G) \geq 10$: $b_i(G) \leq 3$
2. Выявлены различные критические конфигурации графов:
   • Для $\delta(G) \geq 2$ и $g(G) \geq 5$: выявлены 10 неизбежных конфигураций
   • Для $\delta(G) \geq 3$ и $g(G) \geq 4$: выявлены 3 критические конфигурации
   • Для каждой конфигурации построены соответствующие множества независимой связности
3. Расширена существующая теоретическая база:
   • Обобщены результаты Фишермана и др. о числе связности на число независимой связности
   • Использована и развита теория структуры плоских графов Бородина и Ивановой
4. Предложена систематическая методология доказательства:
   • Применён метод разрядки (discharging method) для выявления неизбежных структур
   • Для каждой структуры предоставлено конструктивное доказательство существования множества независимой связности

Подробное описание методов

Теоретическая база

Система определений:

• Число независимой связности графа $G$: $b_i(G) = \min\{|B| : B \subseteq E(G), \gamma_i(G-B) > \gamma_i(G)\}$
• Обхват $g(G)$: длина кратчайшего цикла в графе
• Минимальная степень $\delta(G)$: минимальная степень вершины в графе

Ключевые леммы:

Теорема 1 (Priddy, Wang, Wei): Для непустого графа G,
b_i(G) ≤ min{d(u) + d(v) - |N(u) ∩ N(v)| - 1 : uv ∈ E(G)}

Основной метод: техника разрядки

Принцип метода разрядки:

1. Начальное распределение заряда: распределение заряда в соответствии с тремя естественными способами, вытекающими из формулы Эйлера
   • Заряд вершины: $d(v) - 6$, заряд грани: $2\ell(f) - 6$ (разрядка вершин)
   • Заряд вершины: $2d(v) - 6$, заряд грани: $\ell(f) - 6$ (разрядка граней)
   • Заряд вершины: $d(v) - 4$, заряд грани: $\ell(f) - 4$ (сбалансированная разрядка)
2. Правила перераспределения заряда: разработаны специальные правила для передачи заряда от положительно заряженных вершин/граней к отрицательно заряженным
3. Выявление структур: путём анализа финального распределения заряда доказывается неизбежность определённых структур

Конкретная стратегия реализации

Для случая $\delta(G) \geq 2$ и $g(G) \geq 5$:

Правила разрядки:

• (R1) Каждая вершина степени 2 получает по $\frac{1}{2}$ заряда от каждой соседней вершины и каждой инцидентной грани
• (R2) Каждая вершина степени 3 получает по $\frac{1}{3}$ заряда от каждой инцидентной грани
• (R3) Правила распределения заряда для конкретных вершин степени 6
• (R4) Правила распределения заряда для конкретных вершин степени 5

Проверка ключевых фактов:

• Факт 1: каждая вершина степени ≤4 имеет финальный заряд 0
• Факт 2: взаимная исключаемость распределения заряда для вершин степени 5+
• Факты 3-8: гарантия неотрицательности заряда для различных вершин и граней

Основные результаты

Теорема 7: Характеризация структур при $\delta(G) \geq 2$ и $g(G) \geq 5$

Каждый плоский граф $G$, удовлетворяющий условиям, содержит одну из следующих конфигураций:

• (a) Ребро $(2,4^-)$ или $(3,3^-)$
• (b) Вершина $v \in S(5^+, [d(v)-1]^+)$, остальные соседи которой являются вершинами степени 4 или вершинами из $S(5^+,1^+)$
• (c)-(j) Восемь сложных конфигураций, включающих вершины степени 5 с соседями степени 2, разделяющими 5-грань

Теорема 8: Верхняя граница числа независимой связности

Для плоского графа $G$ с $\delta(G) \geq 2$ и $g(G) \geq 5$: $b_i(G) \leq 5$

Схема доказательства:

1. Для каждой конфигурации строится множество рёбер $B$ размера ≤5
2. Доказывается, что удаление $B$ приводит к строгому увеличению числа независимого доминирования
3. Используется доказательство от противного и свойства множеств независимого доминирования

Другие основные результаты

Теорема 10: $\delta(G) \geq 3$ и $g(G) \geq 4$ ⟹ $b_i(G) \leq 6$

Следствие 1: $\delta(G) \geq 2$ и $g(G) \geq 7$ ⟹ $b_i(G) \leq 4$ (на основе леммы Крэнстона-Веста)

Теорема 13: $\delta(G) \geq 2$ и $g(G) \geq 10$ ⟹ $b_i(G) \leq 3$

Технические инновации

Методологические инновации

1. Первое систематическое применение метода разрядки к исследованию числа независимой связности
2. Разработка новых стратегий распределения заряда: специально разработаны для особенностей числа независимой связности
3. Установление полной схемы выявления структур и построения множеств связности

Теоретические вклады

1. Расширение классических результатов: обобщение от числа связности к числу независимой связности
2. Заполнение теоретического пробела: предоставление первых систематических результатов о числе независимой связности при ограничениях на обхват
3. Выявление новых структур графов: обнаружение критических конфигураций, влияющих на число независимой связности

Техники доказательства

1. Тонкий анализ заряда: детальная проверка фактов обеспечивает корректность процесса разрядки
2. Конструктивные доказательства: явное построение множества независимой связности для каждой конфигурации
3. Полнота анализа случаев: исчерпывающее рассмотрение всех возможных структурных конфигураций

Связанные работы

Историческое развитие

1. 1979 год: Гарей и Джонсон доказали NP-полноту задачи о числе доминирования
2. 1983 год: Бауэр и др. ввели концепцию устойчивости доминирования
3. 1990 год: Финк и др. формально определили число связности
4. 2003 год: Фишерман и др. установили верхние границы числа связности при ограничениях на обхват

Исследования числа независимой связности

1. 2018 год: Придди, Ванг и Вэй первыми систематически исследовали число независимой связности
2. 2021 год: Фам и Вэй установили постоянные верхние границы для плоских графов с $\delta(G) \geq 3$
3. Данная работа: первое исследование числа независимой связности при ограничениях на обхват

Сравнение технических методов

• Традиционные методы: в основном основаны на анализе ограничений степени и локальных структур
• Метод данной работы: сочетание ограничений на обхват и техники разрядки, обеспечивающее более тонкую характеризацию структур

Заключение и обсуждение

Основные выводы

Установлена полная система верхних границ числа независимой связности плоских графов при ограничениях на обхват: