| Математический сборник |
|
|
|
|
|
Критерий цикличности обобщенного крестового графа с помощью минимальных запрещенных миноров В. П. Ильюткоa, Д. П. Ильюткоb a Факультет вычислительной математики и кибернетики, Московский государственный университет имени М. В. Ломоносова b Механико-математический факультет, Московский государственный университет имени М. В. Ломоносова
Англоязычная версия:
Sbornik: Mathematics, 2022, Volume 213, Issue 12, Pages DOI: https://doi.org/10.4213/sm9670e 
Реферативные базы данных:
    § 1. ВведениеМногие известные свойства графов являются замкнутыми относительно перехода к минорам, т.е. к графам, полученным из данного графа с помощью операций удаления ребра, стягивания ребра в точку и удаления связных компонент. К таким свойствам, например, относятся свойства планарности графа, вложимости графа в ту или иную поверхность, вложимости графа в трехмерное пространство без “узлов”. Миноры играют большую роль в теории графов, например, они полезны при построении полиномиальных алгоритмов распознавания разных свойств графов: вложимости, незаузленности и т.п. Важной вехой в теории графов была серия работ Н. Робертсона, П. Сеймура и Х. Томаса (см. [1] и ссылки в ней) доказавших, что любое минорно замкнутое свойство, т.е. свойство графа, сохраняющееся при переходе к минорам, характеризуется конечным числом запрещенных графов. Иными словами, если граф не обладает таким свойством, то он содержит один из графов из конечного списка запрещенных графов в качестве минора. Заметим, что свойство графа иметь хроматическое число не больше данного и свойство реализуемости (цикличности) графа посредством хордовой диаграммы, см. определения ниже, к таковым не относятся. Оказывается, что нереализуемость графа посредством хордовой диаграммы (его нецикличность) описывается в терминах некоторого конечного числа графов и некоторых операций над графами [2]. В работах [3], [4] предложено исследовать аналог минорных свойств для крестовых графов (см. [5], [6]). Крестовые графы тесным образом связаны как с графами общего вида, так и с теорией узлов. Например, критерий Понтрягина–Куратовского планарности графа можно доказать, используя только крестовые графы, см. [7]. Приведем еще один простой пример. Свойство двудольности графа не является минорно замкнутым. Однако если у $4$-графа с крестовой структурой граф пересечений хордовой диаграммы некоторого его поворачивающего обхода, см. определения ниже, является двудольным, то двудольными являются все графы пересечений, соответствующие всем поворачивающим обходам, и это свойство равносильно планарности исходного крестового графа (см. [8], [9]) (все определения см. ниже). Таким образом, при переходе от графов пересечений к крестовым графам свойство, не являющееся минорным, (двудольность) превращается в минорно замкнутое свойство (планарность). Целью настоящей работы является построение некоторого обобщения теории миноров для крестовых графов, см. [3], [4]. А именно, каждому крестовому графу соответствует класс эквивалентности оснащенных графов по некоторым преобразованиям, см. определения ниже. Заметим, что такое соответствие не является взаимно однозначным, но каждый граф класса является циклическим, т.е. реализуется в виде графа пересечений некоторой хордовой диаграммы. Мы рассматриваем классы эквивалентности всех простых оснащенных графов по полученным преобразованиям, вводим понятие минора так, что свойство цикличности класса является минорно замкнутым, и находим все минимальные запрещенные миноры для цикличности класса. Аналогичная работа была проделана в статье [10], но основные результаты этой статьи опираются на леммы 1.7 и 1.9, которые верны лишь частично. Структура работы следующая. В § 2 мы даем основные понятия и определения. В § 3 мы формулируем и доказываем критерий цикличности обобщенного крестового графа. Большинство результатов получено написанием авторами независимо друг от друга программ на пакете Mathematica. Поскольку большинство наших результатов совпало с результатами из [10], а справедливость некоторых наших результатов, отличных от результатов из [10], проверяется руками, то мы смеем предположить, что список минимальных запрещенных миноров для цикличности обобщенного крестового графа верен. § 2. Основные определенияВ этом параграфе мы дадим все основные определения. Все рассматриваемые графы являются конечными. Пусть $G$ – произвольный граф с множеством вершин $V(G)$ и множеством ребер $E(G)$. Ребро графа – класс эквивалентности двух полуребер, составляющих его. Вершина $v\in V(G)$ имеет степень, равную $k$, если $v$ инцидентна ровно $k$ полуребрам. Граф, все вершины которого имеют одну и ту же степень $k$, называется $k$-валентным или просто $k$-графом. Нам будет удобно считать, что свободная петля, т.е. граф без вершин с одним циклическим ребром, является $k$-графом для любого $k$. Определение 2.1. Гамильтонов цикл на графе – это цикл, проходящий через все вершины графа по одному разу. Хордовая диаграмма – это $3$-граф, состоящий из фиксированного неориентированного гамильтонового цикла (окружности) и неориентированных ребер (хорд), соединяющих точки на окружности. Определение 2.2. Мы назовем две хорды зацепленными, если концы одной хорды лежат в разных связных компонентах множества, полученного из окружности удалением концов другой хорды. В противном случае хорды называются незацепленными. Определение 2.3. Граф пересечений хордовой диаграммы – это простой граф, т.е. граф без кратных ребер и петель, множество вершин которого находится во взаимно однозначном соответствии с множеством хорд хордовой диаграммы и две вершины соединены ребром в том и только том случае, если соответствующие хорды зацеплены. Простой граф называется циклическим, если он является графом пересечений некоторой хордовой диаграммы. Определение 2.4. $4$-граф называется крестовым графом, или графом с крестовой структурой или со структурой противоположности ребер, или оснащенным $4$-графом (см. [3]–[6], [8]), если в каждой вершине графа четыре исходящих из нее полуребра разбиты на две пары полуребер. Полуребра из одного семейства называются (формально) противоположными, а из разных – соседними. Очевидно, что простой граф является циклическим, если и только если его компоненты связности являются циклическими простыми графами. Поскольку мы исследуем цикличность простых графов, связанных с крестовыми графами, то без ограничения общности мы рассматриваем только связные крестовые графы. Для каждого связного крестового графа существует эйлеров цикл (см. [5], [8], [11]), т.е. цикл, проходящий все ребра графа ровно один раз. Кроме того, существует эйлеров цикл, поворачивающий в каждой вершине с полуребра на соседнее полуребро (см. [5], [8], [11]). Мы назовем такой эйлеров цикл поворачивающим обходом. В каждой вершине мы имеем один из двух случаев: либо ориентации, порожденные эйлеровым циклом, противоположных полуребер противоположны, либо они совпадают (рис. 1). Имея поворачивающий обход на крестовом графе, мы получаем оснащенную хордовую диаграмму (каждая хорда имеет метку $0$ или $1$, называемую оснащением) по следующему правилу. Двигаясь вдоль обхода, мы отмечаем на окружности, которая соответствует обходу, точки всякий раз, как только мы встречаем вершину графа. Потом мы соединяем ребром точки, соответствующие одной и той же вершине. Далее, хорда имеет оснащение $0$, если ориентации противоположных полуребер в соответствующей вершине противоположны, и хорда имеет оснащение $1$ в противном случае. По оснащенной хордовой диаграмме мы можем построить крестовый граф, для которого существует поворачивающий обход, дающий оснащенную хордовую диаграмму, совпадающую с данной оснащенной хордовой диаграммой. Очевидно, что существует много поворачивающих обходов, и любые два поворачивающих обхода получаются друг из друга последовательностью преобразований, изображенных на рис. 2, см. [5], [11]. Обобщим понятие крестового графа. Имея оснащенную хордовую диаграмму, мы можем построить ее оснащенный граф пересечений, приписав каждой вершине оснащение соответствующей хорды. Хорошо известно, что разные хордовые диаграммы могут иметь один и тот же граф пересечений, рис. 3, и существуют графы, которые не являются графами пересечений хордовых диаграмм, см. рис. 4 и [2]. В связи с этим определим обобщенный крестовый граф, рассматривая классы эквивалентности оснащенных (простых) графов по некоторым преобразованиям, к которым мы сейчас переходим. Множество всех вершин графа $G$, смежных с $v$ и отличных от $v$, называется окрестностью вершины $v$ и обозначается через $N_G(v)$. Определение 2.5. Локальное дополнение графа $G$ в вершине $v\in V(G)$ – это операция, которая меняет смежности только между всеми парами вершин $a,\,b\in N_G(v)$ и $a\ne b$ (остальные смежности остаются без изменений). Обозначим граф, полученный из $G$ с помощью операции локального дополнения в вершине $v$, через $\mathrm{LC}(G;v)$. Определим две операции над оснащенными простыми графами: $\bullet$ $\mathrm{RC}_1$: берем в графе $G$ две смежные вершины $u$ и $v$ с оснащением $0$ и заменяем граф $G$ на граф $\mathrm{LC}(\mathrm{LC}(\mathrm{LC}(G;u);v);u)$ (оснащения всех вершин сохраняются); $\bullet$ $\mathrm{RC}_2$: берем в графе $G$ одну вершину $v$ с оснащением $1$ и заменяем граф $G$ на граф $\mathrm{LC}(G;v)$ и меняем оснащение каждой вершины из $N_{G}(v)$. Определение 2.6. Преобразование графа $G$ в граф $\mathrm{LC}(\mathrm{LC}(\mathrm{LC}(G;u);v);u)$, где $u$ и $v$ – две смежные вершины графа $G$, называется шарнирным преобразованием графа $G$ в вершинах $u$ и $v$, и результат данного преобразования обозначается $\mathrm{piv}(G;u,v)$. Операцию $\mathrm{RC}_1$ назовем оснащенным шарнирным преобразованием, а $\mathrm{RC}_2$ – оснащенным локальным дополнением. Замечание 2.1. Если вершины $u$ и $v$ смежны, то легко показать изоморфность графов $\mathrm{piv}(G;u,v)$ и $\mathrm{piv}(G;v,u)$. Преобразования поворачивающих обходов на крестовых графах, изображенные на рис. 2, на языке оснащенных графов пересечений соответствующих оснащенных хордовых диаграмм соответствуют операциям $\mathrm{RC}_1$ и $\mathrm{RC}_2$. Определение 2.7. Обобщенный крестовый граф – это класс эквивалентности оснащенных простых графов по преобразованиям $\mathrm{RC}_1$ и $\mathrm{RC}_2$. § 3. Критерий цикличности обобщенного крестового графаЛегко видеть, что если какой-то представитель обобщенного крестового графа является циклическим, то и любой его представитель является циклическим (см. [12]). Назовем обобщенный крестовый граф циклическим, если он имеет циклический представитель. Определим минор обобщенного крестового графа $G$ как обобщенный крестовый граф, порожденный графом, полученным из какого-то представителя графа $G$ удалением произвольных $k$ вершин (напомним, что при удалении вершин из графа еще удаляются и все ребра, инцидентные данным вершинам). Заметим, что для циклического оснащенного графа удаление вершины соответствует разведению в соответствующей вершине крестового графа, т.е. операции Количества вершин разных представителей одного и того же обобщенного крестового графа одинаковы, и между вершинами имеется естественная биекция. Кроме того, количество разных миноров обобщенного крестового графа, полученных удалением одних и тех же $k\geqslant0$ вершин, не больше чем $2^k$. В реализуемом случае это очевидно, в общем случае см. [12], [13]. Следующая лемма следует из геометрического описания миноров в случае циклического обобщенного крестового графа. Лемма 3.1. Если обобщенный крестовый граф является циклическим, то любой его минор является циклическим. Наша цель – описать запрещенные миноры для цикличности обобщенного крестового графа, т.е. указать такой список графов, что необходимым и достаточным условием цикличности обобщенного крестового графа является отсутствие минора, порожденного каким-то графом из данного списка, см. [3], [4]. Очевидно, что достаточно описать минимальные запрещенные миноры, т.е. такие графы, что любой их минор, содержащий на одну вершину меньше, является циклическим. Далее, теорема 1.1 из работы [2] утверждает, что простой граф не является циклическим тогда и только тогда, когда найдется локально эквивалентный ему граф, т.е. граф, полученный из него с помощью конечной последовательности локальных дополнений в вершинах, содержащий индуцированный подграф, изоморфный одному из графов, изображенных на рис. 4. Таким образом, каждый представитель запрещенного минора локально эквивалентен графу, содержащему индуцированный подграф, изоморфный одному из графов, изображенных на рис. 4. Напомним, что индуцированный подграф – это подграф, полученный удалением некоторого числа вершин из данного графа. Опишем все запрещенные миноры к цикличности обобщенного крестового графа. Поиск этих миноров будем производить методами, использованными в [10]. Определение 3.1. Граф $H$ называется вершинным минором графа $G$, если $H$ изоморфен индуцированному подграфу графа, локально эквивалентного графу $G$. Лемма 3.2 (см. [14]). Пусть $H$ – вершинный минор простого графа $G$, $v\in V(G)\setminus V(H)$ и $w\in N_G(v)$. Тогда $H$ – вершинный минор одного из трех графов $G\setminus v$, $\mathrm{LC}(G;v)\setminus v$ и $\mathrm{piv}(G;v,w)\setminus v$ (здесь из трех графов мы удалили вершину $v$). Замечание 3.1. Заметим, что для любых двух вершин $w_1,w_2\in N_G(v)$ графы $\mathrm{piv}(G;v,w_1)\setminus v$ и $\mathrm{piv}(G;v,w_2)\setminus v$ локально эквивалентны. Поскольку мы рассматриваем графы с точностью до локальной эквивалентности, то, следуя работе [10], будем обозначать граф $\mathrm{piv}(G;v,w)\setminus v$, где $w\in N_G(v)$, через $G/v$. Определение 3.2. Пусть $H$ – произвольный простой граф. Простой граф $G$ называется $H$-единственным, если $H$ изоморфен вершинному минору графа $G$ и для каждой вершины $v\in V(G)$ не более одного графа среди графов $G\setminus v$, $\mathrm{LC}(G;v)\setminus v$ и $G/v$ имеет вершинный минор, изоморфный $H$. Лемма 3.3 (ср. [10]). Пусть $G$ – представитель минимального запрещенного минора. Тогда $G$ является либо $W_5$-, либо $BW_3$-, либо $W_7$-единственным. Доказательство. Граф $G$ содержит вершинный минор $H$, изоморфный либо $W_5$, либо $BW_3$, либо $W_7$, см. [2; теорема 1.1]. Допустим, что $G$ не является $H$-единственным. Тогда существует вершина $v$ такая, что по крайней мере два графа среди графов $G\setminus v$, $\mathrm{LC}(G;v)\setminus v$ и $G/v$ имеют вершинный минор, изоморфный $H$. Если один из таких графов – это граф $G\setminus v$, то обобщенный крестовый граф, порожденный графом $G\setminus v$, является запрещенным минором. Получаем противоречие с минимальностью запрещенного минора $\{G\}$.
Пусть графы $\mathrm{LC}(G;v)\setminus v$ и $G/v$ имеют вершинный минор, изоморфный $H$. Рассмотрим следующие случаи (принимая во внимание, что граф $G$ связен): вершина $v$ имеет оснащение $1$; вершина $v$ имеет оснащение $0$ и найдется вершина $w\in N_G(v)$ с оснащением $0$; вершина $v$ имеет оснащение $0$ и любая вершина $w\in N_G(v)$ имеет оснащение $1$. В первом случае мы получаем, что оснащенный граф $\mathrm{LC}(G;v)$ является представителем обобщенного крестового графа $\{G\}$, порожденного $G$, и, следовательно, $\mathrm{LC}(G;v)\setminus v$ порождает запрещенный минор, т.е. опять получаем противоречие с минимальностью запрещенного минора $\{G\}$. Во втором случае мы получаем, что оснащенный граф $\mathrm{piv}(G;v,w)$ является представителем обобщенного крестового графа $\{G\}$, и, следовательно, $G/v$ порождает запрещенный минор, т.е. опять получаем противоречие с минимальностью запрещенного минора $\{G\}$. В третьем случае получаем, что оснащенный граф $\mathrm{LC}(\mathrm{LC}(G;w);v)$ является представителем обобщенного крестового графа $\{G\}$. Поскольку граф $\mathrm{LC}(\mathrm{LC}(G;w);v)\setminus v$ локально эквивалентен графу $\mathrm{LC}(\mathrm{LC}(\mathrm{LC}(G;w);v);w)\setminus v\cong G/v$, то $\mathrm{LC}(\mathrm{LC}(G;w);v)\setminus v$ порождает запрещенный минор, т.е. опять получаем противоречие с минимальностью запрещенного минора $\{G\}$. Лемма доказана. Опишем все $W_5$-, $BW_3$-, $W_7$-единственные графы. Сначала приведем леммы, которые помогают при описании таких графов. Лемма 3.4 (см. [10]). Пусть $G$ – $H$-единственный граф, и $H$ – вершинный минор графа $G'$, который, в свою очередь, является вершинным минором графа $G$. Тогда $G'$ тоже является $H$-единственным. Лемма 3.5 (см. [10]). Пусть $H$ – простой граф. Если для некоторого $k>|V(H)|$ не существует $H$-единственного графа, то каждый $H$-единственный граф имеет не более $k-1$ вершин. Лемма 3.6 (ср. [10]). 1) Каждый $W_5$-единственный граф локально эквивалентен графу, изоморфному одному из $14$ графов, изображенных на рис. 5. 2) Каждый $W_7$-единственный граф либо локально эквивалентен графу $W_7$, либо имеет вершинный минор, изоморфный графу $W_5$. 3) Каждый $BW_3$-единственный граф либо локально эквивалентен графу $BW_3$, либо имеет вершинный минор, изоморфный графу $W_5$. Доказательство. Поскольку $H$-единственный граф ищется с точностью до локальной эквивалентности (см. следствие 3.1), то мы можем считать, что он содержит индуцированный подграф, изоморфный $H$.
1) Каждый $W_5$-единственный граф должен содержать по крайней мере шесть вершин. Если $W_5$-единственный граф содержит шесть вершин, то мы получаем с точностью до локальной эквивалентности один граф, $W_5$ (мощность класса локальной эквивалентности равна $2$). Пусть $W_5$-единственный граф содержит семь вершин. Рассмотрим все неизоморфные связные простые графы, имеющие семь вершин и содержащие индуцированный подграф, изоморфный $W_5$. Используя программу, написанную авторами на Wolfram Mathematica, мы получаем $15$ графов, из них девять являются $W_5$-единственными и локально эквивалентными друг другу. В данном случае получаем с точностью до локальной эквивалентности один $W_5$-единственный граф $W_{5;7}$ (класс локальной эквивалентности имеет мощность $46$). Заметим, что графы $BW_3$ и $W_7$ не являются вершинными минорами графа $W_{5;7}$. Обозначим через $\mathrm{FG}_7$ множество, состоящее из оставшихся шести графов, которые не являются $W_5$-единственными. Пусть $W_5$-единственный граф содержит восемь вершин. Используя лемму 3.4, мы рассмотрим все неизоморфные связные простые графы, имеющие восемь вершин, содержащие индуцированный подграф, изоморфный $W_{5;7}$, и не содержащие индуцированных подграфов, изоморфных какому-либо графу из $\mathrm{FG}_7$. Используя программу, мы получаем $55$ графов, которые разбиваются на десять классов локальной эквивалентности, из них четыре класса содержат $W_5$-единственные графы. В данном случае получаем четыре экземпляра $W_5$-единственного графа $W_{5;8.1}$, $W_{5;8.2}$, $W_{5;8.3}$ и $W_{5;8.4}$ (по одному представителю из каждого класса). Мощности классов локальной эквивалентности равны $298$, $433$, $254$ и $117$ соответственно. Заметим, что граф $W_7$ не является вершинным минором ни одного из графов $W_{5;8.1}$, $W_{5;8.2}$, $W_{5;8.3}$ и $W_{5;8.4}$, а $BW_3$ является вершинным минором графов $W_{5;8.3}$ и $W_{5;8.4}$, причем эти графы являются $BW_3$-единственными. Обозначим через $\mathrm{FG}_8$ множество, состоящее из оставшихся 25 графов, которые не являются $W_5$-единственными. Пусть $W_5$-единственный граф содержит девять вершин. Используя лемму 3.4, мы рассмотрим все неизоморфные связные простые графы, имеющие девять вершин, содержащие индуцированные подграфы, изоморфные хотя бы одному из графов $W_{5;8.1}$, $W_{5;8.2}$, $W_{5;8.3}$ и $W_{5;8.4}$ и не содержащие индуцированных подграфов, изоморфных какому-либо графу из $\mathrm{FG}_7$ или $\mathrm{FG}_8$. Используя программу, мы получаем $278$ графов, которые разбиваются на $47$ классов локальной эквивалентности, из них семь классов содержат $W_5$-единственные графы. В данном случае получаем семь $W_5$-единственных графов $W_{5;9.1}$, $W_{5;9.2}$, $W_{5;9.3}$, $W_{5;9.4}$, $W_{5;9.5}$, $W_{5;9.6}$ и $W_{5;9.7}$ (по одному представителю из каждого класса). Мощности классов локальной эквивалентности равны $806$, $818$, $844$, $305$, $1246$, $840$ и $166$ соответственно. Заметим, что граф $W_7$ является вершинным минором графов $W_{5;9.5}$ и $W_{5;9.6}$, причем эти графы являются $W_7$-единственными, а $BW_3$ является вершинным минором графов $W_{5;9.1}$ и $W_{5;9.5}$, причем эти графы являются $BW_3$-единственными. Обозначим через $\mathrm{FG}_9$ множество, состоящее из оставшихся 235 графов, которые не являются $W_5$-единственными. Пусть $W_5$-единственный граф содержит десять вершин. Используя лемму 3.4, мы рассмотрим все неизоморфные связные простые графы, имеющие десять вершин, содержащие индуцированные подграфы, изоморфные хотя бы одному из графов $W_{5;9.1}$, $W_{5;9.2}$, $W_{5;9.3}$, $W_{5;9.4}$, $W_{5;9.5}$, $W_{5;9.6}$ и $W_{5;9.7}$ и не содержащие индуцированных подграфов, изоморфных какому-либо графу из $\mathrm{FG}_7$ или $\mathrm{FG}_8$, или $\mathrm{FG}_9$. Используя программу, мы получаем $85$ графов, которые разбиваются на $49$ классов локальной эквивалентности, из них один класс содержит $W_5$-единственные графы. В данном случае получаем один $W_5$-единственный граф $W_{5;10}$ (мощность класса локальной эквивалентности равны $267$). Заметим, что граф $W_7$ не является вершинным минором графа $W_{5;10}$, а $BW_3$ является, причем $W_{5;10}$ является $BW_3$-единственным. Обозначим через $\mathrm{FG}_{10}$ множество, состоящее из оставшихся 84 графов, которые не являются $W_5$-единственными. Если мы рассмотрим все неизоморфные связные простые графы, имеющие $11$ вершин, содержащие индуцированный подграф, изоморфный $W_{5;10}$, и не содержащие индуцированных подграфов, изоморфных какому-либо графу из $\mathrm{FG}_7$ или $\mathrm{FG}_8$, или $\mathrm{FG}_9$, или $\mathrm{FG}_{10}$, то используя программу, мы получим три графа, которые не являются $W_5$-единственными. Таким образом, не существует $W_5$-единственных графов, имеющих больше десяти вершин. 2) Каждый $W_7$-единственный граф должен содержать по крайней мере восемь вершин. Если $W_7$-единственный граф содержит восемь вершин, то мы получаем с точностью до локальной эквивалентности один граф, $W_7$ (мощность класса локальной эквивалентности равна $22$). Пусть $W_7$-единственный граф содержит девять вершин. Рассмотрим все неизоморфные связные простые графы, имеющие девять вершин и содержащие индуцированный подграф, изоморфный $W_7$. Используя программу, мы получаем $35$ графов, которые разбиваются на $6$ классов локальной эквивалентности, из них четыре класса содержат $W_7$-единственные графы. В данном случае получаем четыре $W_7$-единственных графа $W_{7;9.1}$, $W_{7;9.2}$, $W_{7;9.3}$ и $W_{7;9.4}$ (по одному представителю из каждого класса), см. рис. 6. Мощности классов локальной эквивалентности равны $2408$, $1246$, $840$ и $672$ соответственно. Осталось заметить, что граф $W_{7;9.2}$ локально эквивалентен графу $W_{5;9.5}$, а $W_{7;9.3}$ – $W_{5;9.6}$, и $W_5$ является вершинным минором графов $W_{7;9.1}$ и $W_{7;9.4}$, причем эти графы не являются $W_5$-единственными ($W_{7;9.1}$ является $BW_3$-единственными). 3) Каждый $BW_3$-единственный граф должен содержать по крайней мере семь вершин. Если $BW_3$-единственный граф содержит семь вершин, то мы получаем с точностью до локальной эквивалентности один граф, $BW_3$ (мощность класса локальной эквивалентности равна $9$). Пусть $BW_3$-единственный граф содержит восемь вершин. Рассмотрим все неизоморфные связные простые графы, имеющие восемь вершин и содержащие индуцированный подграф, изоморфный $BW_3$. Используя программу, написанную авторами на Wolfram Mathematica, мы получаем $39$ графов, которые разбиваются на семь классов локальной эквивалентности, из них четыре класса содержат $BW_3$-единственные графы. В данном случае получаем четыре $BW_3$-единственных графа $BW_{3;8.1}$, $BW_{3;8.2}$, $BW_{3;8.3}$ и $BW_{3;8.4}$ (по одному представителю из каждого класса), см. рис. 7. Мощности классов локальной эквивалентности равны $254$, $117$, $476$ и $28$ соответственно. Осталось заметить, что граф $BW_{3;8.1}$ локально эквивалентен графу $W_{5;8.3}$, а $BW_{3;8.2}$ – $W_{5;8.4}$ и $W_5$ является вершинным минором графов $BW_{3;8.3}$ и $BW_{3;8.4}$, причем эти графы не являются $W_5$-единственными. Лемма 3.6 доказана. Замечание 3.2. Лемма 1.7 из [10] утверждает, что существует одиннадцать $W_5$-единственных графов. Как видим, эта лемма неверна. Также, как мы думаем, число под каждым графом на рис. 4 из [10] должно соответствовать мощности класса локальной эквивалентности соответствующего графа. Почти все мощности, за исключением первой, указаны неправильно. Лемма 1.9 из [10] утверждает, что граф $Q_3$, остов куба, является $BW_3$-единственным графом. Легко проверить, что утверждение тоже неверно. Теорема 3.1. Обобщенный крестовый граф является циклическим, если и только если он не содержит минора, порожденного одним из $166$ графов, изображенных на рис. 8–15 (петли на рисунках соответствуют оснащению 1, т.е. вершины с оснащением 1, и только они, на рисунках изображены вершинами с петлями). Доказательство. Из лемм 3.3 и 3.6 следует, что представитель каждого минимального запрещенного минора локально эквивалентен $BW_3$, $W_7$ или одному из $14$ графов, изображенных на рис. 5. Для каждого из $16$ графов рассмотрим все ему локально эквивалентные графы, добавим всевозможные оснащения вершин к каждому из полученных графов, разобьем полученное множество графов на классы эквивалентности по преобразованиям $\mathrm{RC}_1$ и $\mathrm{RC}_2$ и проверим каждый класс на минимальность. В результате с помощью программы, написанной авторами на Wolfram Mathematica, мы получаем следующее.
Граф $W_5$ дает $29$ оснащенных графов, которые порождают пять обобщенных крестовых графов, и все они являются минимальными запрещенными минорами, см. рис. 8. Граф $BW_3$ дает $560$ оснащенных графов, которые порождают $32$ обобщенных крестовых графов, и все они минимальные запрещенные миноры, см. рис. 9. Граф $W_{5;7}$ дает $2226$ оснащенных графов, которые порождают $114$ обобщенных крестовых графов, и $38$ из них являются минимальными запрещенными минорами, см. рис. 10. Граф $W_7$ дает $2711$ оснащенных графов, которые порождают $48$ обобщенных крестовых графов, и все они минимальные запрещенные миноры, см. рис. 11. Граф $W_{5;8.1}$ дает $5128$ оснащенных графов, которые порождают $561$ обобщенный крестовый граф, и три из них являются минимальными запрещенными минорами, см. рис. 12. Граф $W_{5;8.2}$ дает $16594$ оснащенных графов, которые порождают $933$ обобщенных крестовых графов, и $21$ из них являются минимальными запрещенными минорами, см. рис. 13. Граф $W_{5;8.3}$ дает $7840$ оснащенных графов, которые порождают $579$ обобщенных крестовых графов, и $13$ из них являются минимальными запрещенными минорами, см. рис. 14. Графы $W_{5;8.4}$, $W_{5;9.5}$ и $W_{5;9.6}$ дают $1484$, $5536$ и $6848$ оснащенных графов соответственно, которые порождают $142$, $1330$ и $894$ обобщенных крестовых графов соответственно, и ни один из них не является минимальным запрещенным минором. Графы $W_{5;9.1}$, $W_{5;9.2}$, $W_{5;9.3}$, $W_{5;9.4}$, $W_{5;9.7}$ и $W_{5;10}$ дают $5568$, $5960$, $7290$, $1690$, $662$ и $1210$ оснащенных графов соответственно, которые порождают $1339$, $1398$, $1490$, $530$, $267$ и $441$ обобщенных крестовых графов соответственно, и шесть из них (по одному для каждого первоначального графа) являются минимальными запрещенными минорами, см. рис. 15. Теорема 3.1 доказана. Замечание 3.3. Таким образом, мы получили тот же самый список минимальных запрещенных миноров, который был приведен на рис. 5 из [10]. Авторы выражают благодарность В. О. Мантурову и И. М. Никонову за внимание к работе и полезные замечания. 
Цитирование в формате AMSBIB
\RBibitem{IlyIly22} |
|
||||||||||||||||||||||||||
|
Обратная связь: |
Пользовательское соглашение
|
Регистрация посетителей портала |
Логотипы |
|