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

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

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

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

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

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

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

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

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

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

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

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

Розмноження

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

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

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

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

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

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

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

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

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

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

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

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

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

Щільність

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

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

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

Примітки

1. Dalibor Fronček. Locally linear graphs // Mathematica Slovaca. — 1989. — Т. 39, вип. 1. — С. 3–6.
2. Larrión F., Pizaña M. A., Villarroel-Flores R. Small locally nK₂ graphs // Ars Combinatoria. — 2011. — Т. 102. — С. 385–391.
3. Paul Erdős, Alfréd Rényi, Vera T. Sós. On a problem of graph theory // Studia Sci. Math. Hungar.. — 1966. — Т. 1. — С. 215–235.
4. Bohdan Zelinka. Polytopic locally linear graphs // Mathematica Slovaca. — 1988. — Т. 38, вип. 2. — С. 99–103.
5. Alice Devillers, Wei Jin, Cai Heng Li, Cheryl E. Praeger. Local 2-geodesic transitivity and clique graphs // Journal of Combinatorial Theory. — 2013. — Т. 120, вип. 2. — С. 500–508. — doi:10.1016/j.jcta.2012.10.004.. У позначеннях за цим посиланням сімейство ${\displaystyle 2r}$-регулярних графів позначено як ${\displaystyle F(r,2)}$.
6. Andrea Munaro. On line graphs of subcubic triangle-free graphs // Discrete Mathematics. — 2017. — Т. 340, вип. 6. — С. 1210–1226. — doi:10.1016/j.disc.2017.01.006.
7. Cong Fan. On generalized cages // Journal of Graph Theory. — 1996. — Т. 23, вип. 1. — С. 21–31. — doi:10.1002/(SICI)1097-0118(199609)23:1<21::AID-JGT2>3.0.CO;2-M.
8. Ruzsa I. Z., Szemerédi E. Triple systems with no six points carrying three triangles // Combinatorics (Proc. Fifth Hungarian Colloq., Keszthely, 1976), Vol. II. — North-Holland, 1978. — Т. 18. — С. 939–945. — (Colloq. Math. Soc. János Bolyai).
9. Brouwer A. E., Haemers W. H. Structure and uniqueness of the (81,20,1,6) strongly regular graph // Discrete Mathematics. — 1992. — Т. 106/107. — С. 77–82. — doi:10.1016/0012-365X(92)90532-K.
10. Berlekamp E. R., van Lint J. H., Seidel J. J. A strongly regular graph derived from the perfect ternary Golay code // A survey of combinatorial theory (Proc. Internat. Sympos., Colorado State Univ., Fort Collins, Colo., 1971). — North-Holland, 1973. — С. 25–30. — doi:10.1016/B978-0-7204-2262-7.50008-9.
11. Antonio Cossidente, Tim Penttila. Hemisystems on the Hermitian surface // Journal of the London Mathematical Society. — 2005. — Т. 72, вип. 3. — С. 731–741. — doi:10.1112/S0024610705006964.
12. Andriy V. Bondarenko, Danylo V. Radchenko. On a family of strongly regular graphs with ${\displaystyle \lambda =1}$ // Journal of Combinatorial Theory. — 2013. — Т. 103, вип. 4. — С. 521–531. — doi:10.1016/j.jctb.2013.05.005.
13. Махнёв А. А. О сильно регулярных графах с ${\displaystyle \lambda =1}$ // Матем. заметки. — 1988. — Т. 44, вип. 5. — С. 667–672, 702.
14. Sa'ar Zehavi, Ivo Fagundes David de Olivera. Not Conway's 99-graph problem. — 2017. — arXiv:1707.08047.
15. Akira Hiraki, Kazumasa Nomura, Hiroshi Suzuki. Distance-regular graphs of valency 6 and ${\displaystyle a_{1}=1}$ // Journal of Algebraic Combinatorics. — 2000. — Т. 11, вип. 2. — С. 101–134. — doi:10.1023/A:1008776031839.