Локально лінійний граф

Граф Пелі з дев'ятьма вершинами є локально лінійним. Один із шести трикутників виділено зеленим.

Локально лінійний граф — неорієнтований граф у якому кожне ребро $uv$ належить рівно одному трикутнику $uvw$.Тобто для будь-якої вершини $v$ будь-який окіл $v$ має бути суміжним рівно ще одній вершині, сусідній з $v$. Локально лінійні графи називають також локально парованими графами.

Прикладами локально лінійних графів є трикутні кактуси, реберні графи 3-регулярних графів без трикутників і прямий добуток дрібніших локально лінійних графів. Деякі кнезеровські графи, і деякі регулярні графи також локально лінійні.

Деякі локально лінійні графи мають майже квадратичну кількість ребер. Питання, наскільки щільні ці графи, може бути одним із формулювань задачі Ружі — Семереді. Відомі також найщільніші планарні графи, які можуть бути локально лінійними.

Побудови та приклади

Кубооктаедр, планарний локально лінійний граф, який можна утворити як реберний граф куба або приклеюванням антипризм у внутрішню та зовнішню грані 4-циклу

Для локально лінійних графів відомі деякі побудови.

Приклеювання та добутки

Графи товаришування, утворені склеюванням разом набору трикутників в одній спільній вершині, локально лінійні. Це єдині скінченні графи, що мають сильнішу властивість, що будь-яка пара вершин (суміжних чи ні) мають рівно одну спільну сусідню вершину. Загальніше, будь-який трикутний кактус, граф, у якому всі прості цикли трикутні і всі пари простих циклів мають максимум одну спільну вершину, локально лінійні.

Нехай $G$ і $H$ — будь-які два локально лінійні графи. Виберемо трикутник з кожного з графів і склеїмо два графи разом, ототожнивши пари в цих трикутниках (це вид операції на графах суми за клікою). Тоді отриманий граф залишається локально лінійним.

Прямий добуток будь-яких двох локально лінійних графів залишається лінійно локальним, оскільки будь-які трикутники у добутку приходять з одного чи іншого множника. Наприклад, Граф Пелі з дев'ятьма вершинами (граф 3-3 дуопризми) є прямим добутком двох трикутників. Графи Геммінга $H(d,3)$ є добутками $d$ трикутників, тому також локально лінійні.

Розмноження

Якщо граф $G$ є 3-регулярним графом без трикутників, то реберний граф $L(G)$ є графом, утвореним перетворенням кожного ребра графа $G$ на нову вершину і зв'язуванням двох вершин ребром у $L(G)$, якщо відповідні ребра графа $G$ мають спільну кінцеву вершину. Ці графи є 4-регулярними та локально лінійними. Будь-який 4-регулярний локально-лінійний граф можна побудувати так. Наприклад, граф кубооктаедра можна утворити в цей спосіб як реберний граф куба, а граф Пелі з дев'ятьма вершинами є реберним графом комунального графа $K_{3,3}$. Реберний граф графа Петерсена, інший граф цього типу, має властивість, аналогічну властивості кліток, що це найменший можливий граф, у якому найбільша кліка має три вершини, кожна вершина належить двом клікам, що не перетинаються, а найкоротший цикл із ребрами з різних клік має овжину 5.

Складніший процес розмноження застосовують до планарних графів. Нехай $G$ — планарний граф, вкладений у площину так, що кожна грань чотирикутна, як у графа куба. Якщо приклеїти квадратну антипризму до грані графа $G$, а потім видалити оригінальні ребра графа $G$, отримаємо новий локально лінійний планарний граф. Кількість ребер і вершин результату можна обчислити за формулою Ейлера для многогранника: якщо $G$ має $n$ вершин, то він має $n-2$ граней, а після заміни граней $G$ антипризмами отримаємо $5(n-2)+2$ вершин та $12(n-2)$ ребер. Наприклад, з двох граней (внутрішньої та зовнішньої) 4-циклу в такий спосіб можна отримати кубооктаедр.

Алгебрична побудова

Кнезерів граф $KG_{a,b}$ має ${\tbinom {a}{b}}$ вершин, що представляють $b$-елементні підмножини $a$-елементної множини. Дві вершини суміжні, якщо відповідні підмножини не перетинаються. Коли $a=3b$ результуючий граф локально лінійний, оскільки для кожних двох не перетинних $b$-елементних підмножин є рівно одна $b$-елементна підмножина (доповнення їх об'єднання), яка не перетинається з обома множинами. Отриманий локально лінійний граф має ${\tbinom {3b}{b}}$ вершин та ${\tfrac {1}{2}}{\tbinom {3b}{b}}{\tbinom {2b}{b}}$ ребер. Наприклад, для $b=2$ кнезерів граф $KG_{6,2}$ локально лінійний з 15 вершинами та 45 ребрами.

Локально лінійні графи можна побудувати з вільних від прогресій множин чисел. Нехай $p$ — просте число і нехай $A$ — підмножина чисел за модулем $p$, таких, що ніякі три члени $A$ не формують арифметичної прогресії за модулем $p$. (Тобто $A$ є множиною Салема — Спенсера за модулем $p$.) Тоді існує тричастковий граф, у якому кожна частка має $p$ вершин, $3|A|p$ ребер та кожне ребро належить єдиному трикутнику. Тоді, згідно з цією побудовою, $n=3p$ і число ребер дорівнює $n^{2}/e^{O({\sqrt {\log n}})}$. Для побудови цього графа пронумеруємо вершини на кожній частці тричасткового графа від $0$ до $p-1$ і побудуємо трикутники вигляду $(x,x+a,x+2a)$ за модулем $p$ для кожного $x$ в інтервалі від $0$ до $p-1$ і кожного $a$ з $A$. Граф, утворений об'єднанням цих трикутників, має очікувану властивість, що будь-яке ребро належить єдиному трикутнику. Якби це було не так, існував би трикутник $(x,x+a,x+a+b)$, де $a$, $b$ і $c=(a+b)/2$ належали б $A$, що порушує припущення про відсутність арифметичних прогресій $(a,c,b)$ в $A$. Наприклад, з $p=3$ і $A=\{\pm 1\}$, результатом буде Граф Пелі з дев'ятьма вершинами.

Регулярні та сильно регулярні графи

Будь-який локально лінійний граф повинен мати парний степінь кожної вершини, оскільки ребро в кожній вершині можна розбити на пари для трикутників. Прямий добуток двох локально лінійних регулярних графів також локально лінійний і регулярний зі степенем, що дорівнює сумі ступенів множників. Отже, існують регулярні локально лінійні графи будь-якого парного степеня. $2r$-регулярні локально лінійні графи повинні мати принаймні $6r-3$ вершин, оскільки стільки є в трикутниках та сусідах. (Жодні дві вершини трикутника не можуть мати спільних сусідів без порушення локальної лінійності.) Регулярні графи з таким самим числом вершин можливі, тільки коли $r$ 1, 2, 3 або 5 і єдиним чином визначені для кожного з цих чотирьох випадків. Чотири регулярні графи, на яких досягається ця межа як функція від числа вершин, — це 2-регулярний трикутник $K_{3}$ (3 вершини), 4-регулярний граф Пелі (9 вершин), 6-регулярний кнезерів граф $KG_{6,2}$ (15 вершин) та 10-регулярне доповнення графа Шлефлі (27 вершин). Останній у списку 10-регулярний граф із 27 вершинами також є графом перетинів 27 прямих на кубічній поверхні.

Сильно регулярний граф можна описати четвіркою параметрів $(n,k,\lambda ,\mu )$, де $n$ — число вершин, $k$ — число інцидентних вершині ребер, $\lambda$ — число спільних сусідів для будь-якої суміжної пари вершин і $\mu$ — число спільних сусідів для будь-якої несуміжної пари вершин. Коли $\lambda =1$, граф локально лінійний. Локально лінійні графи, як згадано вище, сильно регулярні, а їх параметри рівні

• трикутник (3,2,1,0),
• граф Пелі з дев'ятьма вершинами (9,4,1,2),
• кнезерів граф $KG_{6,2}$ (15,6,1,3),
• доповнення графа Шлефлі (27,10,1,5).

Інші локально лінійні строго регулярні графи:

• граф Брауера — Хемерса (81,20,1,6),
• граф Берлекемпа — ван Лінта — Зейделя (243,22,1,2),
• граф Косіденте — Пенттіли (378,52,1,8),
• граф Геймса (729,112,1,20).

Іншими потенційно правильними комбінаціями з $\lambda =1$ є (99,14,1,2) і (115,18,1,3), але не відомо, чи існують сильно регулярні графи з такими параметрами. Питання існування сильно регулярного графа з параметрами (99,14,1,2) відоме як задача Конвея про 99-вершинний граф і Джон Конвей запропонував приз 1000 доларів тому, хто її розв'яже.

Існує безліч локально лінійних дистанційно-регулярних графів степеня 4 або 6. Крім сильно регулярних графів однакового степеня, вони включають реберний граф графа Петерсена, граф Геммінга $H(3,3)$ і половинку графа Фостера.

Щільність

Найщільніші можливі локально-лінійні планарні графи, утворені вклеюванням антипризми (червоні вершини і чорні ребра) в кожну квадратну грань планарного графа (сині вершини і пунктирні жовті ребра).

Одне з формулювань задачі Ружі — Семереді ставить питання про найбільшу кількість ребер у локально лінійному графі з $n$ вершинами. Як довели Імре З. Ружа та Ендре Семереді, це найбільше число дорівнює $o(n^{2})$, але також дорівнює $\Omega (n^{2-\varepsilon })$ для будь-кого $\varepsilon >0$. Побудова локально лінійних графів із вільних від прогресій множин веде до найщільніших відомих локально лінійних графів із $n^{2}/\exp O({\sqrt {\log n}})$ ребрами.

Серед планарних графів найбільша кількість ребер у локально лінійному графі з $n$ вершинами дорівнює ${\tfrac {12}{5}}(n-2)$. Граф кубооктаедра є першим у нескінченній послідовності поліедральних графів з $n=5k+2$ вершинами та ${\tfrac {12}{5}}(n-2)=12k$ ребрами для $k=2,3,\dots$, побудованими шляхом розширення квадратних граней $K_{2,k}$ антипризми. Ці приклади показують, що ця верхня межа точна.