Локальная дробная метрическая размерность ротационно-симметричных плоских графов, возникающих из плоских хордовых циклов

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

• ID статьи: 2105.07808
• Название: Local fractional metric dimension of rotationally symmetric planar graphs arisen from planar chorded cycles
• Авторы: Shahbaz Ali, Raúl M. Falcón, Muhammad Khalid Mahmood
• Классификация: math.CO (комбинаторика)
• Дата публикации: 17 мая 2021 г. (препринт arXiv)
• Ссылка на статью: https://arxiv.org/abs/2105.07808

Аннотация

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

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

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

1. Происхождение проблемы метрической размерности: Введена независимо Слейтером и Харари & Мельтером в 1970-х годах с целью определения минимального количества вершин в графе, которые могут однозначно представлять все вершины через векторы расстояний
2. Сложность проблемы: Проблема метрической размерности является NP-трудной, однако получены явные решения для различных типов графов
3. Практическая ценность: Имеет важные приложения в навигации роботов, распознавании образов, обработке изображений, представлении химических соединений, комбинаторной оптимизации и сетевых технологиях

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

1. Теоретическая необходимость: Имран и соавторы поставили задачу характеризации семейств (ротационно-симметричных) плоских графов с постоянной метрической размерностью
2. Технологическое развитие: В 2000 году Чартранд и соавторы сформулировали проблему метрической размерности как задачу целочисленного программирования; впоследствии Керри и Оэллерманн предложили релаксацию линейного программирования, введя концепцию дробной метрической размерности
3. Локализованное исследование: В 2018 году Бениш и соавторы ввели концепцию локальной дробной метрической размерности, касающейся только соседних вершин; эта область исследований всё ещё находится на начальной стадии

Ограничения существующих методов

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

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

1. Конструкция новых семейств графов: Описано новое семейство ротационно-симметричных плоских графов $G_m(G)$, построенное на основе слияния рёбер плоских хордовых циклов
2. Вычисление размерности: Установлена локальная дробная метрическая размерность всех ротационно-симметричных плоских графов, порождённых плоскими хордовыми циклами порядка $n ≤ 6$
3. Асимптотический анализ: Предоставлен анализ асимптотического поведения локальной дробной метрической размерности этих семейств графов
4. Теоретическая коррекция: Исправлены ошибочные результаты в литературе относительно локальной дробной метрической размерности колёсных графов
5. Полнота классификации: Проведён всесторонний анализ всех неизоморфных случаев четырёхугольных, пятиугольных и шестиугольных хордовых циклов

Методология

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

Исследуется локальная дробная метрическая размерность ротационно-симметричных плоских графов $G_m(G)$, где $G$ — плоский хордовый цикл порядка $n$, а $m ≥ 2$ — количество копий.

Метод конструкции графа

Для $m$ непересекающихся копий $G_1, G_2, ..., G_m$ плоского хордового цикла $G$ граф $G_m(G)$ строится посредством следующей последовательности слияний рёбер:

1. $G_1(G) := G_1 \cdot G_2(v_2^1v_3^1, v_{n-1}^2v_n^2 : v_{n-1}^2v_n^2)$
2. $G_k(G) := G_{k-1}(G) \cdot G_{k+1}(v_2^kv_3^k, v_{n-1}^{k+1}v_n^{k+1} : v_{n-1}^{k+1}v_n^{k+1})$, для $k \in \{2,...,m-1\}$
3. $G_m(G) := G_{m-1}(G) \cdot G_m(v_2^mv_3^m, v_{n-1}^1v_n^1 : v_{n-1}^1v_n^1)$

Полученный граф $G_m(G)$ является ротационно-симметричным плоским графом порядка $m \cdot (n-2)$.

Определение ключевых концепций

Локальная дробная метрическая размерность

Для графа $G$ локальная дробная метрическая размерность определяется как: $\text{ldim}_f(G) := \min\left\{\sum_{v \in V(G)} \vartheta(v) : \vartheta \text{ — локальная разрешающая функция } G\right\}$

где локальная разрешающая функция $\vartheta: V(G) \to [0,1]$ удовлетворяет условию: $\sum_{u \in R\{v,w\}} \vartheta(u) \geq 1$ для всех пар смежных вершин $vw \in E(G)$.

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

Лемма 2.1: Для конечного связного графа $G$ порядка $n ≥ 2$:

• $\text{ldim}_f(G) \leq \text{dim}_f(G)$
• $\frac{n}{n - \text{ldim}(G) + 1} \leq \text{ldim}_f(G) \leq \frac{n}{\ell(G)} \leq \frac{n}{2}$
• $\text{ldim}_f(G) = 1$ тогда и только тогда, когда $G$ — двудольный граф
• $\text{ldim}_f(G) = \frac{n}{2}$ тогда и только тогда, когда каждая вершина в $V(G)$ имеет истинного двойника

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

1. Систематический анализ: Впервые проведён полный анализ всех ротационно-симметричных графов, построенных на основе плоских хордовых циклов порядка не более 6
2. Методы вычисления: Применено линейное программирование для определения точных значений или верхних границ локальной дробной метрической размерности
3. Асимптотический анализ: Установлены закономерности асимптотического поведения локальной дробной метрической размерности для различных семейств графов
4. Коррекция ошибок: Исправлены ошибочные результаты в работе 2 относительно локальной дробной метрической размерности колёсных графов

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

Анализ классов графов

В работе анализируются следующие классы графов:

• Четырёхугольные хордовые циклы: Q₁, Q₂ (2 типа)
• Пятиугольные хордовые циклы: P₁ — P₆ (6 типов)
• Шестиугольные хордовые циклы: H₁ — H₁₇ (17 типов)

Методы вычисления

1. Линейное программирование: Для каждого класса графов построена соответствующая задача линейного программирования
2. Использование симметрии: Применена ротационная симметрия графа для упрощения вычислений
3. Анализ разрешающей окрестности: Вычислены размеры разрешающей окрестности $|R\{v,w\}|$ для критических пар рёбер

Оценочные показатели

• Точные значения локальной дробной метрической размерности
• Асимптотические верхние границы
• Сравнение с теоретическими нижними границами

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

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

Случай четырёхугольников

Предложение 3.1: Для $m ≥ 2$:

• $\text{ldim}_f(G_m(Q_1)) = \begin{cases} \frac{3}{2}, & \text{если } m = 2 \\ \frac{m}{2}, & \text{в противном случае} \end{cases}$
• $\text{ldim}_f(G_m(Q_2)) = \begin{cases} \frac{3}{2}, & \text{если } m \leq 4 \\ \frac{m}{4}, & \text{в противном случае} \end{cases}$

Случай пятиугольников

Теорема 4.1: Установлены верхние границы локальной дробной метрической размерности для всех пятиугольных хордовых циклов $P_1$ — $P_6$, например:

• $\text{ldim}_f(G_m(P_2)) \leq \begin{cases} \frac{2m}{m+1}, & \text{если } m \text{ нечётно} \\ \frac{6m}{3m+2}, & \text{в противном случае} \end{cases}$

Случай шестиугольников

Теорема 4.2: Для шестиугольных хордовых циклов $H_1$ — $H_{17}$:

• $\text{ldim}_f(G_m(H_1)) = \text{ldim}_f(G_m(H_2)) = 1$ (двудольные графы)
• Для остальных случаев приведены соответствующие формулы верхних границ

Исправленные результаты для колёсных графов

Лемма 3.1: Для колёсного графа $W_n$ порядка $n ≥ 4$: