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

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

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

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

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

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

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

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

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

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

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

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

Розмноження

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

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

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

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

Локально лінійні графи можна побудувати з вільних від прогресій множин чисел. Нехай $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$Шаблон:R. Наприклад, з $p=3$ і $A=\{\pm 1\}$, результатом буде Граф Пелі з дев'ятьма вершинами.

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

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

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

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

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

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

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

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

Щільність

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

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

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