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: dG⊡H(v)={dG(v),если v∈V(G)2∣V(H)∣+2,если v∈I(G)dG(ui)+dH(vj),если v=vi,jd_{G\boxdot H}(v) = \begin{cases} 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 (Pn⊡PtP_n \boxdot P_t): φ(Pn⊡Pt)={4,если n=3 и t∈{3,4}5,если (n=3 и t≥5) или n∈{4,5}n−1,если 6≤n≤2t+32t+3,в остальных случаях\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: Аналогично даны точные формулы для Pn⊡CtP_n \boxdot C_t, Pn⊡StP_n \boxdot S_t, Pn⊡KtP_n \boxdot K_t.

b-хроматические числа SVN корон циклов

Теорема 11 (Cn⊡PtC_n \boxdot P_t): φ(Cn⊡Pt)={5,если n∈{3,4}n,если 5≤n≤2t+22t+3,в остальных случаях\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-хроматических чисел, включая ключевой результат: φ(Sn⊡Kt′)=min⁡{n,t′+2}+t′\varphi(S_n \boxdot K_{t'}) = \min\{n, t'+2\} + t'

b-хроматические числа SVN корон полных графов

Теоремы 20-24: При ограничении m-степени даны b-хроматические числа для Kn⊡GK_n\boxdot G, например: φ(Kn⊡Pt)={n+1,при определённых условияхn+2,при других условиях\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(ui)=(i+1) mod min⁡{m(Pn⊡Pt),n}c(u_i) = (i+1) \bmod \min\{m(P_n \boxdot P_t), n\}

4. Систематизация классификации по случаям

Проводится тонкая классификация по диапазонам параметров, обеспечивающая охват всех возможных ситуаций.

Экспериментальная верификация

Графическая верификация

Статья предоставляет множество графических примеров для проверки теоретических результатов:

  • Рисунок 2: Оптимальная b-хроматическая раскраска P10⊡P3P_{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. Ограничение для полных графов: Результаты для Kn⊡GK_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): Классические результаты раскраски графов