Сертифицированный доминирующий набор ⇐ Васина Википедия

[wiki_en]

В теории графов «сертифицированное доминирующее множество» графа (дискретная математика)|граф — это тип доминирующего множества, в котором каждая вершина в множестве имеет либо ноль, либо по крайней мере две окрестности (теория графов)|соседей вне множества. Концепция была представлена Детлаффом, Леманской, Топпом, Циманном и Жилиньским в 2018 году.
Концепция моделирует сценарий с участием чиновников и гражданских лиц в социальной сети. Учитывая набор D чиновников и набор W гражданских лиц, каждое гражданское лицо должно обслуживаться каким-либо чиновником, и всякий раз, когда чиновник обслуживает гражданское лицо, должен быть хотя бы еще один гражданский человек, который может наблюдать за чиновником, выступая в качестве свидетеля, чтобы предотвратить потенциальное злоупотребление. Сертифицированное число доминантов представляет собой минимальное количество официальных лиц, необходимое для обеспечения такой услуги.

== Определение ==

Пусть G = (V, E) — граф. Доминирующее множество D \subseteq V называется «сертифицированным доминирующим множеством», если для каждой вершины v \in D количество соседей v в V \setminus D равно нулю или не менее двух. Аналогично, ни одна вершина в D не имеет ровно одного соседа за пределами D.

'''Сертифицированное доминантное число''' G, обозначаемое \gamma_{\text{cer(G), представляет собой минимальную мощность сертифицированного доминирующего множества в G. Сертифицированный доминирующий набор минимальной мощности называется \gamma_{\text{cer'''-set'''.
Вершины D можно классифицировать на основе их соседей в V \setminus D. Вершина в D без соседей в V \setminus D называется «затененной», вершина в D ровно с одним соседом в V \setminus D называется «полузатененной», а вершина в D с минимум двумя соседями в V \setminus D называется «подсвеченным». Доминирующий набор сертифицирован тогда и только тогда, когда он не содержит полузатененных вершин.

== Свойства и примеры ==

Для любого графа G порядка n:

* Набор вершин V всегда является сертифицированным доминирующим набором, поэтому 1 \leq \gamma_{\text{cer(G) \leq n.
* \gamma_{\text{cer(G) \neq n - 1 для любого графика.
* Каждая опорная вершина|опорная вершина G принадлежит каждому сертифицированному доминирующему множеству.
* \gamma_{\text{cer(G) = 1 тогда и только тогда, когда G имеет порядок не ниже третьего и содержит универсальную вершину|универсальную вершину.
* Если G_1, G_2, \ldots, G_k — компонент связности (теория графов)|компоненты связности G, то \gamma_{\text{cer(G) = \sum_{i=1}^{k} \gamma_{\text{cer(G_i).

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

* Для графа пути|path P_n:
**\gamma_{\text{cer(P_n) = 1, если n = 1 или n = 3
**\gamma_{\text{cer(P_n) = 2, если n = 2
**\gamma_{\text{cer(P_n) = 4, если n = 4
**\gamma_{\text{cer(P_n) = \lceil n/3 \rceil иначе
* Для графика цикла|cycle C_n с n \geq 3:
**\gamma_{\text{cer(C_n) = \lceil n/3 \rceil
* Для полного графика K_n:
**\gamma_{\text{cer(K_n) = 1, если n = 1 или n \geq 3
**\gamma_{\text{cer(K_n) = 2, если n = 2
* Для полного двудольного графа K_{m,n} с 1 \leq m \leq n:
**\gamma_{\text{cer(K_{m,n}) = 1, если m = 1 и n > 1
**\gamma_{\text{cer(K_{m,n}) = 2 иначе
* Для кругового графика W_n:
**\gamma_{\text{cer(W_n) = 1

=== Границы и связь с числом доминирования ===

Поскольку каждое сертифицированное доминирующее множество является доминирующим, \gamma(G) \leq \gamma_{\text{cer(G) для всех графов G. Для связного графа G сертифицированное число доминирования соответствует:

:\gamma_{\text{cer(G) \leq \gamma(G) + |S_1(G)|

где \gamma(G) — число доминирования, а S_1(G) — набор слабых опорных вершин (опорных вершин, смежных ровно с одним Листом (теория графов)|листом). Эта оценка точна, поскольку равенство справедливо для произведения Corona|corona любого графа без изолированных вершин. Как следствие, \gamma_{\text{cer(G) \leq 2\gamma(G). Кроме того, если вершины сильной опоры G в целом примыкают к листьям k, то \gamma_{\text{cer(G) \leq n - k.

Равенство \gamma_{\text{cer(G) = \gamma(G) выполняется в нескольких случаях:

* Если G не имеет слабой опорной вершины (в частности, если \delta(G) \geq 2), то \gamma_{\text{cer(G) = \gamma(G).
* Если G имеет уникальный минимальный доминирующий набор, то \gamma_{\text{cer(G) = \gamma(G).
* Если \gamma(G - v) \geq \gamma(G) для каждой вершины v, принадлежащей хотя бы одному \gamma-множеству из G, то \gamma_{\text{cer(G) = \gamma(G).
* Если G — связный граф без P4|P_4-свободный граф и G \neq K_2, то \gamma_{\text{cer(G) = \gamma(G).

В более общем смысле, для связного графа G порядка не менее трех, \gamma_{\text{cer(G) = \gamma(G) тогда и только тогда, когда G имеет \gamma-множество D такое, что каждая вершина в D имеет не менее двух соседей в V \setminus D.

Граф G называется '''\gamma\gamma_{\text{cer-perfect''', если \gamma(H) = \gamma_{\text{cer(H) для каждого индуцированного связного подграфа H \neq K_2 графа G. Граф является \gamma\gamma_{\text{cer-идеальным тогда и только тогда, когда он не содержит P_4.

=== Графики с большим сертифицированным числом доминирования ===

Граф G порядка n удовлетворяет условию \gamma_{\text{cer(G) = n тогда и только тогда, когда G является дополнением (теория графов)|дополнением полного графа, коронным произведением|короной графа или непересекающимся объединением того и другого.

«Диадемный граф» — это граф, полученный из короны H \circ K_1 путем добавления новой вершины и присоединения ее к одной опорной вершине H \circ K_1. Граф G порядка n \geq 3 удовлетворяет условию \gamma_{\text{cer(G) = n - 2 тогда и только тогда, когда G равен C_3, C_4 или диадемному графу, возможно, в сочетании с короной графа и изолированными вершинами.

=== Эффекты модификаций графика ===

Добавление ребра в связный граф не может увеличить сертифицированное число доминирования: \gamma_{\text{cer(G + e) \leq \gamma_{\text{cer(G). Однако как удаление ребра из графа, так и добавление ребра в «несвязный» граф могут произвольно увеличить сертифицированное число доминирования.

Добавление листовой вершины может произвольно увеличить сертифицированное число доминирования, но добавление нелистовой вершины v в граф G удовлетворяет условиям \gamma_{\text{cer(G + v) \leq \gamma_{\text{cer(G) + 1.

=== Неравенства типа Нордхауса–Гаддума ===

Для графа G порядка n \geq 5 с дополнением (теория графов)|дополнением \overline{G:

:\gamma_{\text{cer(G) + \gamma_{\text{cer(\overline{G}) \leq n + 2
:\gamma_{\text{cer(G) \cdot \gamma_{\text{cer(\overline{G}) \leq 2n

Равенство выполняется в обоих неравенствах одновременно тогда и только тогда, когда G или \overline{G} является короной некоторого графа.

Если \min\{\delta(G), \delta(\overline{G})\} \geq 2, выполняются более сильные границы:

:\gamma_{\text{cer(G) + \gamma_{\text{cer(\overline{G}) \leq \left\lfloor \frac{n}{2} \right\rfloor + 2
:\gamma_{\text{cer(G) \cdot \gamma_{\text{cer(\overline{G}) \leq n

== Вычислительная сложность ==

Задача определения сертифицированного числа доминирования является NP-трудной даже для двудольного графа|двудольного плоского графа|плоских субкубических графов без листьев. Это следует из равенства \gamma_{\text{cer(G) = \gamma(G) для графов без слабых опорных вершин и известной NP-трудности проблемы доминирования в таких классах графов.

== См. также ==

* Доминирующий набор
* Коронавирусный продукт
* Теорема Нордхауса-Гаддума

Объекты теории графов
NP-полные задачи
Вычислительные задачи в теории графов

Подробнее: https://en.wikipedia.org/wiki/Certified_dominating_set