2025-11-23T03:01:16.593819

Determining the b-chromatic number of subdivision-vertex neighbourhood coronas

Falcón, Venkatachalam, Margaret
Let $G$ and $H$ be two graphs, each one of them being a path, a cycle or a star. In this paper, we determine the $b$-chromatic number of every subdivision-vertex neighbourhood corona $G\boxdot H$ or $G\boxdot K_n$, where $K_n$ is the complete graph of order $n$. It is also established for those graphs $K_n\boxdot G$ having $m$-degree not greater than $n+2$. All the proofs are accompanied by illustrative examples.
academic

Определение b-хроматического числа корон подразделения-вершины соседства

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

  • ID статьи: 2302.13667
  • Название: Determining the b-chromatic number of subdivision-vertex neighbourhood coronas
  • Авторы: Raúl M. Falcón (Universidad de Sevilla, Spain), M. Venkatachalam, S. Julie Margaret (Kongunadu Arts and Science College, India)
  • Классификация: math.CO (Комбинаторика)
  • Дата публикации: 27 февраля 2023 г.
  • Ссылка на статью: https://arxiv.org/abs/2302.13667

Аннотация

Пусть GG и HH — два графа, каждый из которых является путём, циклом или звездой. В данной работе определено b-хроматическое число каждого графа корон подразделения-вершины соседства G⊡HG\boxdot H или G⊡KnG\boxdot K_n, где KnK_n — полный граф порядка nn. Для графов Kn⊡GK_n\boxdot G с m-степенью не превышающей n+2n+2 также установлены соответствующие результаты. Все доказательства сопровождаются иллюстративными примерами.

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

Предпосылки проблемы

  1. Концепция b-хроматического числа: Ирвинг и Манлав в 1999 году ввели понятие b-хроматической раскраски графа, которая представляет собой специальную правильную k-раскраску, требующую, чтобы каждый цвет имел b-вершину (вершину, смежную со всеми вершинами других цветов).
  2. Вычислительная сложность: Определение b-хроматического числа графа является NP-трудной задачей в общем случае, но полиномиально разрешимо для деревьев.
  3. Исследование произведений графов: Существует обширное исследование b-хроматических чисел различных произведений графов, таких как декартово произведение, прямое произведение, сильное произведение, лексикографическое произведение и др.

Мотивация исследования

  1. Совершенствование теории: Коронные графы подразделения-вершины соседства (SVN corona) представляют собой важный метод конструирования графов, однако исследование их b-хроматических чисел относительно недостаточно.
  2. Систематизация методов: Необходимо систематическое исследование b-хроматических чисел SVN корон основных классов графов (пути, циклы, звёзды, полные графы).
  3. Практическое значение: b-хроматическое число имеет важное применение в раскраске сетей, распределении частот и других практических задачах.

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

  1. Полное определение b-хроматических чисел SVN корон основных классов графов: Для путей PnP_n, циклов CnC_n, звёзд SnS_n и их SVN корон с путями, циклами, звёздами и полными графами получены точные формулы b-хроматических чисел.
  2. Установление частичных результатов для SVN корон полных графов: Для Kn⊡GK_n\boxdot G с m-степенью не превышающей n+2n+2 определено b-хроматическое число.
  3. Предоставление конструктивных методов доказательства: Все результаты доказаны путём построения конкретных оптимальных b-хроматических раскрасок с подробными графическими примерами.
  4. Разработка систематической аналитической базы: Установлена общая методология и технические инструменты для анализа b-хроматических чисел SVN корон.

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

Определение задачи

Входные данные: Два графа GG и HH, где G,H∈{Pn,Cn,Sn,Kn}G,H \in \{P_n, C_n, S_n, K_n\}Выходные данные: b-хроматическое число SVN корона G⊡HG\boxdot H — φ(G⊡H)\varphi(G\boxdot H)Ограничения: Для случая Kn⊡GK_n\boxdot G требуется m(Kn⊡G)≤n+2m(K_n\boxdot G) \leq n+2

Конструкция SVN корона

Процесс построения SVN корона G⊡HG\boxdot H для графов GG и HH:

  1. Начинаем с подразделённого графа S(G)S(G) (вставляем новую вершину на каждое ребро)
  2. Добавляем ∣V(G)∣|V(G)| вершинно-непересекающихся копий графа HH
  3. Соединяем все вершины в окрестности каждой исходной вершины uiu_i из S(G)S(G) со всеми вершинами (i+1)(i+1)-й копии HH

Ключевые технические инструменты

1. Концепция m-степени

Для графа GG порядка nn m-степень определяется как: m(G):=∣{i∈{1,…,n}:d(vi−1)≥i−1}∣m(G) := |\{i \in \{1,\ldots,n\} : d(v_{i-1}) \geq i-1\}| где вершины упорядочены по неубыванию степеней.

2. Основные границы

  • Нижняя граница: χ(G)≤φ(G)\chi(G) \leq \varphi(G) (хроматическое число не превышает b-хроматическое число)
  • Верхняя граница: φ(G)≤Δ(G)+1\varphi(G) \leq \Delta(G) + 1 (b-хроматическое число не превышает максимальную степень плюс один)
  • Граница m-степени: φ(G)≤m(G)\varphi(G) \leq m(G)

3. Формула степеней для SVN корона

Для вершины vv в G⊡HG\boxdot H:

d_G(v), & \text{если } v \in V(G) \\ 2|V(H)| + 2, & \text{если } v \in I(G) \\ d_G(u_i) + d_H(v_j), & \text{если } v = v_{i,j} \end{cases}$$ ### Стратегия анализа Статья использует метод классификации по случаям, применяемый к различным комбинациям классов графов: 1. **SVN корона путей** (раздел 3) 2. **SVN корона циклов** (раздел 4) 3. **SVN корона звёзд** (раздел 5) 4. **SVN корона полных графов** (раздел 6) В каждом случае верхняя граница доказывается построением конкретной b-хроматической раскраски. ## Основные результаты ### b-хроматические числа SVN корон путей **Теорема 6** ($P_n \boxdot P_t$): $$\varphi(P_n \boxdot P_t) = \begin{cases} 4, & \text{если } n=3 \text{ и } t \in \{3,4\} \\ 5, & \text{если } (n=3 \text{ и } t \geq 5) \text{ или } n \in \{4,5\} \\ n-1, & \text{если } 6 \leq n \leq 2t+3 \\ 2t+3, & \text{в остальных случаях} \end{cases}$$ **Теоремы 7-9**: Аналогично даны точные формулы для $P_n \boxdot C_t$, $P_n \boxdot S_t$, $P_n \boxdot K_t$. ### b-хроматические числа SVN корон циклов **Теорема 11** ($C_n \boxdot P_t$): $$\varphi(C_n \boxdot P_t) = \begin{cases} 5, & \text{если } n \in \{3,4\} \\ n, & \text{если } 5 \leq n \leq 2t+2 \\ 2t+3, & \text{в остальных случаях} \end{cases}$$ ### b-хроматические числа SVN корон звёзд **Теорема 17**: Для SVN корон звёзд и основных классов графов установлены полные формулы b-хроматических чисел, включая ключевой результат: $$\varphi(S_n \boxdot K_{t'}) = \min\{n, t'+2\} + t'$$ ### b-хроматические числа SVN корон полных графов **Теоремы 20-24**: При ограничении m-степени даны b-хроматические числа для $K_n\boxdot G$, например: $$\varphi(K_n \boxdot P_t) = \begin{cases} n+1, & \text{при определённых условиях} \\ n+2, & \text{при других условиях} \end{cases}$$ ## Технические инновации ### 1. Конструктивный метод доказательства - Не только доказаны верхние границы, но и через явное построение оптимальных b-хроматических раскрасок доказаны нижние границы - Каждое построение сопровождается подробными графическими примерами, повышающими проверяемость результатов ### 2. Концепция b-радужного множества Введено понятие b-радужного множества для упрощения идентификации b-вершин, обозначаемых в графе различными символами: - Крест ×: вершины определённого b-радужного множества - Треугольник △: другие b-вершины - Круг ●: обычные вершины ### 3. Техника модульной арифметики Широко используется модульная арифметика в конструкциях раскрасок для обеспечения периодичности и корректности раскраски, например: $$c(u_i) = (i+1) \bmod \min\{m(P_n \boxdot P_t), n\}$$ ### 4. Систематизация классификации по случаям Проводится тонкая классификация по диапазонам параметров, обеспечивающая охват всех возможных ситуаций. ## Экспериментальная верификация ### Графическая верификация Статья предоставляет множество графических примеров для проверки теоретических результатов: - Рисунок 2: Оптимальная b-хроматическая раскраска $P_{10} \boxdot P_3$ - Рисунки 3-4: Раскраски SVN корон путей при различных параметрах - Рисунок 11: Примеры раскраски SVN корон циклов - Рисунки 17-18: Конструкции раскраски SVN корон звёзд ### Верификация конструкций Доказательство каждой теоремы включает конкретный алгоритм построения раскраски, позволяющий прямо проверить: 1. Корректность раскраски (смежные вершины имеют разные цвета) 2. Существование b-вершин (каждый цвет имеет b-вершину) 3. Оптимальность (достижение теоретической границы) ## Связанные работы ### История исследований b-хроматического числа 1. **Irving-Manlove (1999)**: Первое введение понятия b-хроматического числа 2. **Исследования различных произведений графов**: b-хроматические числа декартова произведения, прямого произведения, сильного произведения и др. широко изучены 3. **Специальные классы графов**: b-хроматические числа путей, циклов, звёзд, полных графов известны ### Место данной работы - **Заполнение пробела**: Исследование b-хроматических чисел SVN корон относительно недостаточно - **Методологическая инновация**: Предоставлена систематическая конструктивная методология - **Полнота результатов**: Даны полные результаты для комбинаций основных классов графов ## Заключение и обсуждение ### Основные выводы 1. **Полнота**: Для SVN корон основных классов графов (пути, циклы, звёзды, полные графы) получены полные результаты определения b-хроматических чисел 2. **Точность**: Все результаты представляют точные значения, а не приближения или границы 3. **Конструктивность**: Предоставлены конкретные методы построения оптимальных раскрасок ### Ограничения 1. **Ограничение на классы графов**: Рассмотрены только основные классы; результаты для общих графов требуют дальнейших исследований 2. **Ограничение для полных графов**: Результаты для $K_n\boxdot G$ требуют условия ограничения m-степени 3. **Сложность**: В некоторых случаях классификация по случаям довольно сложна ### Направления будущих исследований 1. **Расширение классов графов**: Исследование b-хроматических чисел SVN корон более общих классов графов 2. **Алгоритмические исследования**: Разработка эффективных алгоритмов вычисления b-хроматических чисел 3. **Исследование приложений**: Применение результатов к практическим задачам раскраски сетей ## Глубокая оценка ### Преимущества 1. **Значительный теоретический вклад**: Систематическое решение проблемы b-хроматических чисел важного класса произведений графов 2. **Строгая методология**: Конструктивный метод доказательства обеспечивает надёжность результатов 3. **Ясное изложение**: Множество графических примеров и иллюстраций облегчают понимание сложных доказательств 4. **Полнота результатов**: Охватывают все важные комбинации основных классов графов ### Недостатки 1. **Ограниченная техническая инновация**: Главным образом систематическое применение существующих методов, отсутствие принципиально новых техник 2. **Неясная практическая ценность**: Отсутствует обсуждение применения к реальным сценариям 3. **Отсутствие анализа вычислительной сложности**: Не рассмотрена временная сложность алгоритмов построения ### Влияние 1. **Теоретическая ценность**: Важное дополнение к теории b-хроматических чисел графов 2. **Методологическая ценность**: Конструктивные методы могут быть обобщены на исследование других произведений графов 3. **Ценность полноты**: Заполнение пробела в исследовании b-хроматических чисел SVN корон ### Области применения 1. **Теоретические исследования**: Фундаментальные исследования в теории графов и комбинаторной оптимизации 2. **Проектирование сетей**: Задачи раскраски сетей с учётом ограничений соседства 3. **Разработка алгоритмов**: Использование в качестве базового модуля для более сложных алгоритмов раскраски графов ## Библиография Статья цитирует 25 связанных работ, включая: - Irving & Manlove (1999): Исходное определение b-хроматического числа - Kouider & Mahéo и др.: Исследования b-хроматических чисел различных произведений графов - Liu & Lu (2013): Спектральная теория SVN корон - Brooks (1941): Классические результаты раскраски графов