Локально линейный граф - Locally linear graph

Девять вершин Граф Пэли локально линейно. Один из его шести треугольников выделен зеленым.

В теория графов, а локально линейный граф является неориентированный граф в которой окрестности каждого вершина является индуцированное соответствие. То есть для каждой вершины ${\displaystyle v}$, каждый сосед ${\displaystyle v}$ должен быть смежным ровно с одним другим соседом ${\displaystyle v}$. Равно как и каждое ребро ${\displaystyle uv}$ такого графа принадлежит единственному треугольнику ${\displaystyle uvw}$.^[1] Локально линейные графы также называются локально согласованными графами.^[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}}$.Линейный график Граф Петерсена, другой граф этого типа, обладает свойством, аналогичным клетки в том, что это наименьший возможный граф, в котором наибольший клика имеет три вершины, каждая вершина входит ровно в две непересекающиеся по ребрам клики, а кратчайший цикл с ребрами из различных клик имеет длину пять.^[7]

Более сложный процесс расширения применяется к планарные графы.Позволять ${\displaystyle G}$ - плоский граф, вложенный в плоскость таким образом, что каждая грань является четырехугольником, например график куба. Обязательно, если ${\displaystyle G}$ имеет ${\displaystyle n}$ вершины, он имеет ${\displaystyle n-2}$ лица. Склеивание квадратная антипризма на каждое лицо ${\displaystyle G}$, а затем удалив исходные края ${\displaystyle G}$, создает новый локально линейный планарный граф с ${\displaystyle 5(n-2)+2}$ вершины и ${\displaystyle 12(n-2)}$ края.^[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}$ это Набор Салема – Спенсера по модулю ${\displaystyle p}$.) Тогда существует трехчастный граф, в котором каждая сторона трехчастного раздела имеет ${\displaystyle p}$ вершин, есть ${\displaystyle 3|A|p}$ ребра, и каждое ребро принадлежит уникальному треугольнику. Чтобы построить этот граф, пронумеруйте вершины на каждой стороне тройного разбиения из ${\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 и однозначно определены для каждого из этих четырех случаев. Четыре регулярных графа, удовлетворяющие этой границе по количеству вершин, являются 3-вершинным 2-правильным треугольником ${\displaystyle K_{3}}$, 9-вершинный 4-регулярный граф Пэли, 15-вершинный 6-регулярный граф Кнезера ${\displaystyle KG_{6,2}}$, а 27-вершинная 10-регулярная дополнительный граф из Граф Шлефли. Последний 27-вершинный 10-регулярный граф также представляет собой граф пересечений из 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)}$, а вдвое Граф Фостера.^[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. Фрончек, Далибор (1989), «Локально линейные графы», Mathematica Slovaca, 39 (1): 3–6, HDL:10338.dmlcz / 136481, Г-Н  1016323
2. Ларрион, Ф .; Pizaña, M.A .; Вильярроэль-Флорес, Р. (2011), "Маленький локально нК₂ графики " (PDF), Ars Combinatoria, 102: 385–391, Г-Н  2867738
3. Эрдеш, Пол; Реньи, Альфред; Сос, Вера Т. (1966), «К проблеме теории графов» (PDF), Studia Sci. Математика. Hungar., 1: 215–235
4. Зелинка, Богдан (1988), "Политопические локально линейные графы", Mathematica Slovaca, 38 (2): 99–103, HDL:10338.dmlcz / 133017, Г-Н  0945363
5. Девиллерс, Алиса; Джин, Вэй; Ли, Цай Хэн; Прегер, Шерил Э. (2013), «Локальная 2-геодезическая транзитивность и кликовые графы», Журнал комбинаторной теории, Серия А, 120 (2): 500–508, Дои:10.1016 / j.jcta.2012.10.004, Г-Н  2995054. В обозначениях этой ссылки семейство ${\displaystyle 2r}$-регулярные графы обозначаются как ${\displaystyle F(r,2)}$.
6. Мунаро, Андреа (2017), «О линейных графах субкубических графов без треугольников», Дискретная математика, 340 (6): 1210–1226, Дои:10.1016 / j.disc.2017.01.006, Г-Н  3624607
7. Фан, Конг (1996), "Обобщенные клетки", Журнал теории графов, 23 (1): 21–31, Дои:10.1002 / (SICI) 1097-0118 (199609) 23: 1 <21 :: AID-JGT2> 3.0.CO; 2-M, Г-Н  1402135
8. Ружа, И.З.; Семереди, Э. (1978), «Тройные системы без шести точек, несущие три треугольника», Комбинаторика (Proc. Fifth Hungarian Colloq., Keszthely, 1976), Vol. II, Коллок. Математика. Soc. Янош Бойяи, 18, Амстердам и Нью-Йорк: Северная Голландия, стр. 939–945, Г-Н  0519318
9. Брауэр, А.Э.; Хемерс, В. Х. (1992), "Структура и единственность (81,20,1,6) сильно регулярного графа", Сборник статей в честь Джека ван Линта, Дискретная математика, 106/107: 77–82, Дои:10.1016 / 0012-365X (92) 90532-К, Г-Н  1181899
10. Берлекамп, Э.; ван Линт, Дж. Х.; Зайдель, Дж. Дж. (1973), «Сильно регулярный граф, полученный из совершенного тернарного кода Голея», Обзор комбинаторной теории (Proc. Internat. Sympos., Colorado State Univ., Fort Collins, Colo., 1971), Амстердам: Северная Голландия: 25–30, Дои:10.1016 / B978-0-7204-2262-7.50008-9, ISBN  9780720422627, Г-Н  0364015
11. Коссиденте, Антонио; Пенттила, Тим (2005), "Полусистемы на эрмитовой поверхности", Журнал Лондонского математического общества, Вторая серия, 72 (3): 731–741, Дои:10.1112 / S0024610705006964, Г-Н  2190334
12. Бондаренко, Андрей В .; Радченко, Данило В. (2013), "О семействе сильно регулярных графов с ${\displaystyle \lambda =1}$", Журнал комбинаторной теории, Серия B, 103 (4): 521–531, arXiv:1201.0383, Дои:10.1016 / j.jctb.2013.05.005, Г-Н  3071380
13. Махнев, А. А. (1988), "Сильно регулярные графы с ${\displaystyle \lambda =1}$", Академия Наук СССР, 44 (5): 667–672, 702, Дои:10.1007 / BF01158426, Г-Н  0980587, S2CID  120911900
14. Зехави, Саар; Давид де Оливера, Иво Фагундес (2017), Не проблема Конвея с 99-графами, arXiv:1707.08047
15. Хираки, Акира; Номура, Казумаса; Судзуки, Хироши (2000), "Дистанционно регулярные графы валентности 6 и ${\displaystyle a_{1}=1}$", Журнал алгебраической комбинаторики, 11 (2): 101–134, Дои:10.1023 / А: 1008776031839, Г-Н  1761910