2025-11-17T18:31:12.470972

Distance mutual-visibility coloring: relations with (total) domination, exact distance graphs and graph products

Babu, Brešar, S et al.
The concept of mutual-visibility (MV) has been extended in several directions. A vertex subset $S$ of a graph $G$ is a $k$-distance mutual-visibility ($k$DMV) set if for any two vertices in $S$, there is a geodesic between them of length at most $k$ whose internal vertices are not in $S$. In this paper, we combine this with the MV coloring as follows. For any integer $k\geq1$, a $k$DMV coloring of $G$ is a partition of $V(G)$ into $k$DMV sets, and the $k$DMV chromatic number $χ_{μ_k}(G)$ is the minimum cardinality of such a partition. When $k=1$ or $k\ge {\rm diam}(G)$, it equals the clique cover number $θ(G)$ or the MV chromatic number $χ_μ(G)$, respectively. So, our attention is given to $1<k<{\rm diam}(G)$ with $k=2$ producing the most interesting results. We prove that $χ_{μ_2}(G)\le|V(G)|/2$ and present large families of graphs that attain the bound. In addition, $χ_{μ_2}(G)$ is bounded from above by the total domination number $γ_t(G)$ if $G$ is isolate-free, while in graphs $G$ with girth $g(G)\geq7$, $χ_{μ_2}(G)$ is bounded from below by the domination number $γ(G)$. A surprising relation with the exact distance-2 graphs is found, which results in $θ(G^{[\natural2]})=γ_{t}(G)$ for any isolate-free graph $G$ with $g(G)\geq7$. The relation is explored further in lexicographic product graphs, where we prove the sharp inequalities $χ_{μ_{2}}(G\circ H)\leq θ(G^{[\natural2]})\leq θ\big{(}(G\circ H)^{[\natural2]}\big{)}$. We also prove a sharp lower (resp. upper) bound on $χ_{μ_2}$ (resp. $χ_{μ_k}$) for the Cartesian (resp. strong) product of two connected graphs and show that they are widely sharp. Finally, we characterize the block graphs $G$ with $χ_{μ_k}(G)=χ_μ(G)$, where $k={\rm diam}(G)-1$.
academic

Раскраска взаимной видимости на расстоянии: связи с (полным) доминированием, графами точного расстояния и произведениями графов

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

  • ID статьи: 2510.10284
  • Название: Distance mutual-visibility coloring: relations with (total) domination, exact distance graphs and graph products
  • Авторы: Saneesh Babu, Boštjan Brešar, Aparna Lakshmanan S, Babak Samadi
  • Классификация: math.CO (комбинаторика)
  • Дата публикации: 11 октября 2025 г.
  • Ссылка на статью: https://arxiv.org/abs/2510.10284

Аннотация

В данной работе исследуется проблема раскраски k-взаимной видимости на расстоянии, которая является расширением концепции взаимной видимости, введённой Di Stefano в 2022 году. Для подмножества вершин S графа G множество S называется k-множеством взаимной видимости на расстоянии (k-DMV множество), если между любыми двумя вершинами в S существует геодезическая длины не более k, внутренние вершины которой не принадлежат S. Авторы объединяют это понятие с раскраской взаимной видимости и определяют число раскраски k-DMV χ_μ_k(G). Исследование показывает, что наиболее интересные результаты получаются при k=2, доказано, что χ_μ_2(G) ≤ |V(G)|/2, и установлены глубокие связи с числом доминирования, числом полного доминирования и графами точного расстояния.

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

  1. Происхождение проблемы: Концепция взаимной видимости была впервые предложена Di Stefano в 2022 году и связана с классической задачей о трёх неколлинеарных точках и проблемой переориентации мобильных роботов на плоскости.
  2. Исследовательская мотивация:
    • Хотя концепция взаимной видимости является новой, она получила широкое внимание (более 20 цитирований в MathSciNet)
    • Существующие исследования сосредоточены главным образом на максимальной мощности множеств взаимной видимости, отсутствует систематическое изучение задач раскраски
    • Ограничение на расстояние k делает коммуникацию более эффективной и имеет практическое применение
  3. Практическое значение: В компьютерных сетях или социальных сетях вершины со свойством взаимной видимости могут представлять сущности, требующие эффективной и конфиденциальной коммуникации, гарантируя, что сообщения не передаются через другие сущности.

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

  1. Введение нового понятия: Впервые определено число раскраски k-взаимной видимости на расстоянии χ_μ_k(G), объединяющее число покрытия кликами (k=1) и число раскраски взаимной видимости (k≥diam(G))
  2. Установление базовых границ:
    • Доказано, что χ_μ_2(G) ≤ ⌈|V(G)|/2⌉, и приведены семейства графов, достигающих эту границу
    • Для графов без изолированных вершин χ_μ_2(G) ≤ γ_t(G)
    • Для графов с обхватом не менее 7 χ_μ_2(G) ≥ γ(G)
  3. Обнаружение связи с графами точного расстояния: Доказано, что для графов G без изолированных вершин и обхватом не менее 7 имеет место θ(G♮2) = γ_t(G)
  4. Систематическое изучение произведений графов:
    • Лексикографическое произведение: χ_μ_2(G∘H) ≤ θ(G♮2) ≤ θ((G∘H)♮2)
    • Сильное произведение: χ_μ_k(G⊠H) ≤ χ_μ_k(G)χ_μ_k(H)
    • Декартово произведение: χ_μ_2(G□H) ≥ max{χ_μ_2(G)ρ_2(H), χ_μ_2(H)ρ_2(G)}
  5. Характеризация специальных классов графов: Полная характеризация блочных графов, удовлетворяющих χ_μ_k(G) = χ_μ(G) (где k = diam(G)-1)

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

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

Для графа G и положительного целого числа k раскраска k-взаимной видимости на расстоянии представляет собой разбиение V(G) на несколько k-DMV множеств. Множество k-DMV M удовлетворяет условию: для любых двух вершин u,v в M существует геодезическая u,v длины не более k, внутренние вершины которой не принадлежат M.

Вход: Граф G = (V,E), положительное целое число k Выход: Разбиение V(G) на {S_1, S_2, ..., S_t}, такое что каждое S_i является k-DMV множеством Цель: Минимизировать количество множеств в разбиении t

Основные технические методы

1. Установление базовой теории

Наблюдение 1: Для графа G с диаметром d имеет место цепь монотонности: χ_μ(G) = χ_μ_d(G) ≤ χ_μ_(G) ≤ ... ≤ χ_μ_1(G) = θ(G)

Наблюдение 2: Базовая нижняя граница χ_μ_k(G) ≥ ⌈|V(G)|/μ_k(G)⌉

2. Глубокий анализ случая k=2

Теорема 4: Для любого связного графа G χ_μ_2(G) ≤ ⌈n/2⌉

Идея доказательства: Посредством индуктивного построения на остовном дереве граф разлагается на структуры, которые могут быть раскрашены двумя цветами.

Теорема 5: Если G не имеет изолированных вершин, то χ_μ_2(G) ≤ γ_t(G)

Метод доказательства: Конструктивное доказательство, использующее множество полного доминирования D = {v_1,...,v_γ_t(G)}, определяется D_i = N_G(v_i)\⋃_^{i-1}N_G(v_j), доказывается, что каждое D_i является 2-DMV множеством.

3. Связь обхвата и числа доминирования

Лемма 6: Если g(G) ≥ 7, то каждый цветовой класс C в χ_μ_2(G)-раскраске является подмножеством замкнутой окрестности некоторой вершины.

Теорема 7: Если g(G) ≥ 7, то χ_μ_2(G) ≥ γ(G)

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

  1. Унифицированная схема: Объединение покрытия кликами, раскраски взаимной видимости в единую схему k-DMV раскраски
  2. Точная характеризация условия обхвата: Доказано, что обхват 7 является минимальным значением, гарантирующим χ_μ_2(G) ≥ γ(G)
  3. Связь с графами точного расстояния: Впервые установлена глубокая связь между 2-DMV раскраской и графами точного расстояния-2
  4. Систематический анализ произведений графов: Для трёх основных типов произведений графов получены точные верхние и нижние границы

Экспериментальная установка

Методы теоретической верификации

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

  1. Пути и циклы: Вычислены точные значения χ_μ_k для P_n и C_n
  2. Специальные семейства: Построены семейства графов, достигающие различных границ
  3. Произведения графов: Проанализированы свойства конкретных произведений графов, таких как P_n⊠K_m

Анализ ключевых примеров

Предложение 2:

  • Для пути P_n: χ_μ_k(P_n) = ⌈n/2⌉
  • Для цикла C_n: χ_μ_k(C_n) = ⌈n/3⌉ (при n ≤ 3k), ⌈n/2⌉ (иначе)

Предложение 12: Для P_n⊠K_m (n≥4, m≥2, k∈{2,...,n-2}): χ_μ_k(P_n⊠K_m) = 2⌊n/(k+2)⌋ + correction_term

Результаты экспериментов

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

  1. Точность базовых границ:
    • χ_μ_2(G) ≤ ⌈|V(G)|/2⌉ верно для всех графов и достигается путями, длинными циклами и т.д.
    • χ_μ_2(G) ≤ γ_t(G) верно для графов без изолированных вершин, и могут быть построены семейства графов, для которых разница произвольно велика
  2. Оптимальность условия обхвата:
    • Построен контрпример с обхватом 6, где γ(G) = 5 > χ_μ_2(G) = 3
    • Доказано, что обхват 7 является минимальным условием, гарантирующим χ_μ_2(G) ≥ γ(G)
  3. Точность результатов для произведений графов:
    • Граница для сильного произведения χ_μ_k(G⊠H) ≤ χ_μ_k(G)χ_μ_k(H) достигается бесконечными семействами графов
    • Нижняя граница для декартова произведения достигается торическими графами и т.д.

Удивительная связь с графами точного расстояния

Теорема 8: Если G не имеет изолированных вершин и g(G) ≥ 7, то θ(G♮2) = χ_i_μ_2(G) = γ_t(G)

Этот результат устанавливает равенство между тремя на первый взгляд не связанными параметрами графа и имеет важное теоретическое значение.

Специальные свойства гиперкубов

Предложение 16: Для n-мерного гиперкуба Q_n χ_μ_2(Q_n) ≤ γ(Q_n)

Гипотеза: χ_μ_2(Q_n) = γ(Q_n) верно для всех n

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

  1. Исследования взаимной видимости: Di Stefano (2022) введение базовых концепций, расширение Cera и др. на k-дистанционный случай
  2. Раскраска взаимной видимости: Klavžar и др. (2025) первое исследование проблемы раскраски взаимной видимости
  3. Графы точного расстояния: Введены в 1980-х годах, в последнее время вновь привлекают внимание
  4. Теория доминирования: Классическая область исследования теории графов, установлены новые связи с данной работой

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

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

  1. Раскраска k-взаимной видимости на расстоянии предоставляет новую перспективу для изучения структурных свойств графов
  2. Случай k=2 демонстрирует глубокие связи с теорией доминирования и графами точного расстояния
  3. Поведение при различных произведениях графов раскрывает сущностные характеристики данного параметра
  4. Условие обхвата играет ключевую роль в определении границ параметра

Ограничения

  1. Основные результаты сосредоточены на случае k=2, исследование общего случая k ограничено
  2. Точность некоторых границ верифицирована только для специальных семейств графов
  3. Вопросы вычислительной сложности не рассмотрены

Направления будущих исследований

Статья предлагает три конкретные открытые проблемы:

Проблема 1: Охарактеризовать блочные графы G, удовлетворяющие χ_μ_2(G) = θ(G)

Проблема 2: Для связных графов G,H верно ли χ_μ_2(G□H) ≥ max{χ_μ_2(G)γ(H), χ_μ_2(H)γ(G)}?

Проблема 3: Верно ли χ_μ_2(Q_n) = γ(Q_n) для всех гиперкубов?

Глубокая оценка

Преимущества

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

Недостатки

  1. Отсутствие анализа вычислительной сложности: Не обсуждается вычислительная сложность χ_μ_k(G)
  2. Ограниченность приложений: Хотя упоминаются приложения в сетевой коммуникации, отсутствует анализ конкретных сценариев применения
  3. Отсутствие алгоритмов: Не предложены эффективные алгоритмы для вычисления или аппроксимации χ_μ_k(G)

Влияние

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

Сценарии применения

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

Библиография

Статья цитирует 18 связанных работ, включая:

  • Di Stefano (2022): исходная литература по концепции взаимной видимости
  • Cera и др.: расширение на k-дистанционную взаимную видимость
  • Klavžar и др.: первое исследование раскраски взаимной видимости
  • Классические учебники по теории графов и литературу по теории доминирования

Общая оценка: Это высокачественная теоретическая работа по теории графов, вносящая значительный вклад в развивающееся направление исследований взаимной видимости. Статья не только устанавливает полную теоретическую схему, но и обнаруживает глубокие связи с классическими концепциями теории графов, закладывая прочную основу для развития этой области. Хотя в аспектах приложений и алгоритмов требуются дальнейшие исследования, её теоретическая ценность и инновационность делают её важной литературой в этой области.