График Фолкмана

Двудольный 4-регулярный граф с 20 узлами и 40 ребрами

В математической области теории графов граф Фолкмана — это 4- регулярный граф с 20 вершинами и 40 ребрами. Это регулярный двудольный граф с симметриями, переводящими каждое ребро в каждое другое ребро, но две стороны его двудольного графа не симметричны друг другу, что делает его наименьшим возможным полусимметричным графом . ^[1] Он назван в честь Джона Фолкмана , который построил его для этого свойства в 1967 году. ^[2]

Граф Фолкмана может быть построен либо с использованием модульной арифметики , либо как подразделенный дубль полного графа с пятью вершинами . Помимо исследования его симметрии, он также был исследован как контрпример для некоторых вопросов вложения графов .

Строительство

Полусимметричные графы определяются как регулярные графы (то есть графы, в которых все вершины касаются одинакового количества ребер), в которых каждые два ребра симметричны друг другу, но некоторые две вершины не симметричны. Джон Фолкман был вдохновлен на определение и исследование этих графов в статье 1967 года, после того как увидел неопубликованную рукопись Э. Даубера и Фрэнка Харари , в которой были приведены примеры графов, удовлетворяющих условию симметрии, но не условию регулярности. Оригинальная конструкция Фолкмана этого графа была частным случаем более общей конструкции полусимметричных графов с использованием модульной арифметики , основанной на простом числе , сравнимом с 1 mod 4. Для каждого такого простого числа существует число такое, что mod , и Фолкман использует модульную арифметику для построения полусимметричного графа с вершинами. Граф Фолкмана является результатом этой конструкции для и . ^[2] ${\displaystyle p}$ ${\displaystyle r}$ ${\displaystyle r^{2}=-1}$ ${\displaystyle p}$ ${\displaystyle 2pr}$ ${\displaystyle p=5}$ ${\displaystyle r=2}$

Построение графа Фолкмана из полного графа . Зелёные вершины подразделяют каждое ребро , а красные пары вершин являются результатом удвоения пяти вершин . ${\displaystyle K_{5}}$ ${\displaystyle K_{5}}$ ${\displaystyle K_{5}}$

Другое построение для графа Фолкмана начинается с полного графа на пяти вершинах, . Новая вершина помещается на каждое из десяти ребер , подразделяя каждое ребро на двухреберный путь. Затем каждая из пяти исходных вершин удваивается, заменяя ее двумя вершинами с теми же соседями. Десять вершин подразделения образуют одну сторону двураздела графа Фолкмана, а десять вершин в парах-близнецах, исходящих из удвоенных вершин, образуют другую сторону двураздела. ^{[3] [4]} ${\displaystyle K_{5}}$ ${\displaystyle K_{5}}$ ${\displaystyle K_{5}}$ ${\displaystyle K_{5}}$

Поскольку каждое ребро результата получается из удвоенной половины ребра , и поскольку имеет симметрии, переводящие каждое полуребро в каждое другое полуребро, результат является реберно-транзитивным. Он не является вершинно-транзитивным, поскольку вершины подразделения не являются близнецами ни с одной другой вершиной, что делает их отличными от удвоенных вершин, полученных из . ^[3] Каждый 4-регулярный полусимметричный граф, в котором некоторые две вершины имеют одинаковое соседство, может быть построен таким же образом, путем подразделения и последующего удвоения 4-регулярного симметричного графа, такого как или граф октаэдра . Однако существуют также более крупные 4-регулярные полусимметричные графы, которые не имеют никаких вершин-близнецов. ^{[4] [5]} ${\displaystyle K_{5}}$ ${\displaystyle K_{5}}$ ${\displaystyle K_{5}}$ ${\displaystyle K_{5}}$

Алгебраические свойства

Группа автоморфизмов графа Фолкмана (его группа симметрий) объединяет симметрии со способами обмена некоторых пар удвоенных вершин, для общего числа симметрий. Эта группа действует транзитивно на ребрах графа Фолкмана (она включает симметрию, переводящую любое ребро в любое другое ребро), но не на его вершинах. Граф Фолкмана является наименьшим неориентированным графом, который является реберно-транзитивным и регулярным, но не вершинно-транзитивным . ^[6] Такие графы называются полусимметричными графами и были впервые изучены Фолкманом в 1967 году, который открыл граф на 20 вершинах, который теперь назван в его честь. ^[2] ${\displaystyle 5!}$ ${\displaystyle K_{5}}$ ${\displaystyle 2^{5}}$ ${\displaystyle 5!\cdot 2^{5}=3840}$

Как и все полусимметричные графы, граф Фолкмана является двудольным . Его группа автоморфизмов включает симметрии, переводящие любую вершину в любую другую вершину, которая находится по ту же сторону двудольного разбиения, но ни одну, которая переводит вершину на другую сторону двудольного разбиения. Хотя можно прямо утверждать, что граф Фолкмана не является вершинно-транзитивным, это также можно объяснить с точки зрения теории групп: его симметрии действуют примитивно на вершинах, построенных как точки подразделения , но импримитивно на вершинах, построенных путем удвоения вершин . Каждая симметрия отображает удвоенную пару вершин в другую удвоенную пару вершин, но не существует группировки вершин подразделения, которая сохраняется симметриями. ^[7] ${\displaystyle K_{5}}$ ${\displaystyle K_{5}}$

Характеристический многочлен графа Фолкмана равен . ^[8] ${\displaystyle (x-4)x^{10}(x+4)(x^{2}-6)^{4}}$

Другие свойства

Граф Фолкмана с вершинами, расположенными в гамильтоновом цикле . Ребра, не используемые в этом цикле, образуют второй гамильтонов цикл гамильтонова разложения .

Граф Фолкмана имеет гамильтонов цикл и, что более строго, гамильтоново разложение на два гамильтоновых цикла. Как и у любого двудольного графа, его хроматическое число равно двум, а его хроматический индекс (минимальное количество цветов, необходимое для раскраски его ребер так, чтобы никакие два ребра одного цвета не встречались в вершине) равен его максимальной степени, ^[9] которая в данном случае равна четырем. Например, такую ​​раскраску можно получить, используя два цвета попеременно для каждого цикла гамильтонова разложения.

Его радиус равен 3, а диаметр равен 4. Если — одна из удвоенных вершин конструкции , то все остальные вершины находятся не более чем в трех шагах от . Однако существуют пары вершин подразделения из конструкции (исходящих из непересекающихся ребер ), которые находятся на расстоянии четырех шагов друг от друга. Поскольку граф содержит много 4-циклов, его обхват равен 4, минимально возможному для двудольного графа. Он также 4- вершинно-связан и 4- рёберно-связан . Его древовидная ширина и кликовая ширина равны 5. ^[10] ${\displaystyle v}$ ${\displaystyle K_{5}}$ ${\displaystyle v}$ ${\displaystyle K_{5}}$

Граф Фолкмана имеет род 3: он может быть вложен в тройной тор , но не в любую более простую ориентированную поверхность. ^{[11] [12]} Он имеет толщину книги 3, но требует пять страниц для «рассеиваемого» книжного вложения, в котором каждая страница является паросочетанием , опровергая гипотезу Фрэнка Бернхарта и Пола Кайнена о том, что для рассасываемых книжных вложений регулярных графов требуется только количество страниц, равное их степени. ^[3]

Ссылки

1. Boesch, F.; Tindell, R. (1984), «Циркулянты и их связности», Журнал теории графов , 8 (4): 487–499, doi :10.1002/jgt.3190080406, MR  0766498
2. Folkman, J. (1967), "Регулярные линейно-симметричные графы", Журнал комбинаторной теории , 3 (3): 215–232, doi : 10.1016/S0021-9800(67)80069-3
3. Alam, Jawaherul Md.; Bekos, Michael A.; Dujmović, Vida ; Gronemann, Martin; Kaufmann, Michael; Pupyrev, Sergey (2021), "On dispersable book embeddings", Theoretical Computer Science , 861 : 1–22, arXiv : 1803.10030 , doi : 10.1016/j.tcs.2021.01.035, MR  4221556
4. Potočnik, Primož; Wilson, Stephen E. (2014), «Связывание структур колец и четырехвалентных полусимметричных графов», Ars Mathematica Contemporanea , 7 (2): 341–352, doi : 10.26493/1855-3974.311.4a8 , MR  3240442
5. Поточник, Примож; Уилсон, Стив (2007), «Тетравентные реберно-транзитивные графы обхвата не более 4», Журнал комбинаторной теории , Серия B, 97 (2): 217–236, doi : 10.1016/j.jctb.2006.03.007 , MR  2290322
6. Скиена, Стивен (1990), Реализация дискретной математики: комбинаторика и теория графов с помощью Mathematica , Рединг, Массачусетс: Addison-Wesley, стр. 186–187
7. Зив-Ав, Матан (2013), Взаимодействие между когерентными конфигурациями и некоторыми классами объектов в экстремальной комбинаторике (PDF) (докторская диссертация), Университет Бен-Гуриона, стр. 24–25
8. Вайсштейн, Эрик В. , «Граф Фолкмана», MathWorld
9. Гэлвин, Фред (1995), «Списочный хроматический индекс двудольного мультиграфа», Журнал комбинаторной теории , Серия B, 63 (1): 153–158, doi : 10.1006/jctb.1995.1011 , MR  1309363
10. Хейл, Марийн; Сейдер, Стефан (2015), «Подход SAT к ширине клики», ACM Transactions on Computational Logic , 16 (3): 24:1–24:27, arXiv : 1304.5498 , doi : 10.1145/2736696
11. Кондер, Марстон ; Стоукс, Клара (2019), «Новые методы поиска вложений минимального рода графов на ориентируемых и неориентируемых поверхностях», Ars Mathematica Contemporanea , 17 (1): 1–35, doi : 10.26493/1855-3974.1800.40c , hdl : 2292/57926 , MR  3992757
12. Бринкманн, Гуннар (2022), «Практический алгоритм для вычисления рода», Ars Mathematica Contemporanea , 22 (4), Статья № 1, arXiv : 2005.08243 , doi : 10.26493/1855-3974.2320.c2d, MR  4498572, S2CID  218674244