Главная
Статьи





09.10.2022


09.10.2022


09.10.2022


09.10.2022


08.10.2022






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

08.10.2022

Локально линейный граф — неориентированный граф в окрестности каждой вершины порождённым паросочетанием. То есть для любой вершины v {displaystyle v} любая окрестность v {displaystyle v} должна быть смежной в точности ещё одной вершине, соседней вершине v {displaystyle v} . Эквивалентно, любое ребро u v {displaystyle uv} такого графа принадлежит единственному треугольнику u v w {displaystyle uvw} . Локально линейные графы называются также локально паросочетаемыми графами.

Примеры локально линейных графов включают треугольные кактусы, рёберные графы 3-регулярных графов без треугольников и прямое произведение более мелких локально линейных графов. Определённые кнезеровские графы, и некоторые сильно регулярные графы также локально линейны.

Некоторые локально линейные графы имеют почти квадратичное число рёбер. Вопрос, как плотны эти графы, может быть одной из формулировок Проблема Ружи – Семереди. Известны также наиболее плотные планарные графы, которые могут быть локально линейными.

Построения и примеры

Известны некоторые построения для локально линейных графов.

Приклеивания и произведения

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

Пусть G {displaystyle G} и H {displaystyle H} будут любыми двумя локально линейными графами, выберем треугольник из каждого из графов и склеим два графа вместе путём отождествления пар в этих треугольниках (это вид операции суммы по клике на графах). Тогда результирующий граф остаётся локально линейным.

Прямое произведение графов любых двух локально линейных графов остаётся линейно локальным, поскольку любые треугольники в произведении приходят из одного или другого множителя. Например, Граф Пэли с девятью вершинами (граф 3-3 дуопризмы) является прямым произведением двух треугольников. Графы Хэмминга H ( d , 3 ) {displaystyle H(d,3)} являются произведениями d {displaystyle d} треугольников, а потому снова локально линейны.

Размножение

Если граф G {displaystyle G} является 3-регулярным графом без треугольников, то рёберный граф L ( G ) {displaystyle L(G)} является графом, образованным путём преобразования каждого ребра графа G {displaystyle G} в новую вершину и связыванием двух вершин ребром в L ( G ) {displaystyle L(G)} , если соответствующие рёбра графа G {displaystyle G} имеют общую конечную вершину. Эти графы являются 4-регулярными и локально линейными. Любой 4-регулярный локально линейный граф может быть построен таким образом. Например, граф кубооктаэдра может быть образован этим способом как рёберный граф куба, а граф Пэли с девятью вершинами является рёберным графом коммунального графа K 3 , 3 {displaystyle K_{3,3}} . Рёберный граф графа Петерсена, другой граф этого типа, имеет свойство, аналогичное свойству клеток, что это наименьший возможный граф, в котором наибольшая клика имеет три вершины, каждая вершина принадлежит двум непересекающимся кликам, а самый короткий цикл с рёбрами из различных клик имеет длину пять.

Более сложный процесс размножения применяется к планарным графам. Пусть G {displaystyle G} будет планарным графом, вложенным в плоскость таким образом, что каждая грань четырёхугольна, как у графа куба. Необходимо, если G {displaystyle G} имеет n {displaystyle n} вершин, чтобы грань имел n − 2 {displaystyle n-2} графов. Если вклеить квадратную антипризму в грань графа G {displaystyle G} , а затем удалить оригинальные рёбра графа G {displaystyle G} , получим новый локально линейный планарный граф с 5 ( n − 2 ) + 2 {displaystyle 5(n-2)+2} вершинами и 12 ( n − 2 ) {displaystyle 12(n-2)} рёбрами. Например, кубооктаэдр может быть получен таким образом из двух граней (внутренняя и внешняя) 4-цикла.

Алгебраическое посторение

Кнезеровский граф K G a , b {displaystyle KG_{a,b}} имеет ( a b ) {displaystyle { binom {a}{b}}} вершин, представляющий b {displaystyle b} -элементные подмножества a {displaystyle a} -элементного множества. Две вершины смежны, если соответствующие подмножества не пересекаются. Когда a = 3 b {displaystyle a=3b} , результирующий граф локально линеен, поскольку для каждых двух не пересекающихся b {displaystyle b} -элементных подмножеств имеется в точности одно b {displaystyle b} -элементное подмножество (дополнение их объединения), которое не пересекается с обоими множествами. Получающийся локально линейный граф имеет ( 3 b b ) {displaystyle { binom {3b}{b}}} вершин и 1 2 ( 3 b b ) ( 2 b b ) {displaystyle { frac {1}{2}}{ binom {3b}{b}}{ binom {2b}{b}}} рёбер. Например, для b = 2 {displaystyle b=2} кнезеровский граф K G 6 , 2 {displaystyle KG_{6,2}} локально линеен с 15 вершинами и 45 рёбрами.

Локально линейные графы могут также быть построены из свободных от прогрессий множеств чисел. Пусть p {displaystyle p} будет простым числом и пусть A {displaystyle A} будет подмножеством чисел по модулю p {displaystyle p} , таких, что никакие три члена A {displaystyle A} не формируют арифметическую прогрессию по модулю p {displaystyle p} . (То есть A {displaystyle A} является множеством Салема — Спенсера по модулю p {displaystyle p} .) Тогда существует трёхдольный граф, в котором каждая доля имеет p {displaystyle p} вершин, имеет 3 | A | p {displaystyle 3|A|p} рёбер и каждое ребро принадлежит единственному треугольнику. Тогда, согласно этому построению, n = 3 p {displaystyle n=3p} и число рёбер равно n 2 / e O ( log ⁡ n ) {displaystyle n^{2}/e^{O({sqrt {log n}})}} . Для построения этого графа, пронумеруем вершины на каждой стороне трёхдольного графа от 0 {displaystyle 0} до p − 1 {displaystyle p-1} и строим треугольнике вида ( x , x + a , x + 2 a ) {displaystyle (x,x+a,x+2a)} по модулю p {displaystyle p} для каждого x {displaystyle x} в интервале от 0 {displaystyle 0} до p − 1 {displaystyle p-1} и каждого a {displaystyle a} из A {displaystyle A} . Граф, образованный объединением этих треугольников, имеет ожидаемое свойство, что любое ребро принадлежит единственному треугольнику. Если бы это было не так, существовал бы треугольник ( x , x + a , x + a + b ) {displaystyle (x,x+a,x+a+b)} , где a {displaystyle a} , b {displaystyle b} и c = ( a + b ) / 2 {displaystyle c=(a+b)/2} принадлежали бы A {displaystyle A} , что нарушает предположение об отсутствии арифметических прогрессий ( a , c , b ) {displaystyle (a,c,b)} в A {displaystyle A} . Например, с p = 3 {displaystyle p=3} и A = { ± 1 } {displaystyle A={pm 1}} , результатом будет Граф Пэли с девятью вершинами.

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

Любой локально линейный граф должен иметь чётную степень для каждой вершины, поскольку ребро в каждой вершине может быть разбито на пары на треугольники. Прямое произведение двух локально линейных регулярных графов снова локально линейно и регулярно со степенью, равной сумме степеней множителей. Таким образом, существует регулярные локально линейные графы любой чётной степени. 2 r {displaystyle 2r} -Регулярные локально линейные графы должны иметь по меньшей мере 6 r − 3 {displaystyle 6r-3} вершин, поскольку столько есть в треугольниках и соседях. (Никакие две вершины треугольника не могут иметь общих соседей без нарушения локальной линейности.) Регулярные графы с точно таким числом вершин возможны, только когда r {displaystyle r} равно 1, 2, 3 или 5 и единственным образом определены для каждого из этих четырёх случаев. Четыре регулярных графа, на которых достигается эта граница как функция от числа вершин, — это 2-регулярный треугольник K 3 {displaystyle K_{3}} (3 вершины), 4-регулярный граф Пэли (9 вершин), 6-регулярный кнезеровский граф K G 6 , 2 {displaystyle KG_{6,2}} (15 вершин) и 10-регулярное дополнение графа Шлефли (27 вершин). Последний в списке 10-регулярный граф с 27 вершинами также является графом пересечений 27 прямых на кубической поверхности.

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

  • треугольник (3,2,1,0),
  • граф Пэли с девятью вершинами (9,4,1,2),
  • кнезеровский граф K G 6 , 2 {displaystyle 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).

Другие потенциально правильные комбинации с λ = 1 {displaystyle lambda =1} включают (99,14,1,2) и (115,18,1,3), но не известно, существуют ли сильно регулярные графы с такими параметрами. Вопрос о существовании сильно регулярного графа с параметрами (99,14,1,2) известен как проблема Конвея 99-графа и Джон Хортон Конвей предложил приз в 1000 долларов тому, кто её решит .

Существует бесконечно много дистанционно-регулярных графов степени 4 или 6, которые локально линейно. Кроме сильно регулярных графов одинаковой степени, они включают рёберный граф графа Петерсена, граф Хэмминга H ( 3 , 3 ) {displaystyle H(3,3)} и половинку графа Фостера.

Плотность

Одна из формулировок проблемы Ружи – Семереди задаёт вопрос о максимальном числе рёбер в локально линейном графе с n {displaystyle n} вершинами. Как доказали Имре З. Ружа и Эндре Семереди, это максимальное число равно o ( n 2 ) {displaystyle o(n^{2})} , но также равно Ω ( n 2 − ε ) {displaystyle Omega (n^{2-varepsilon })} для любого ε > 0 {displaystyle varepsilon >0} . Построение локально линейных графов из свободных от прогрессий множеств ведёт к наиболее плотным известным локально линейным графам с n 2 / exp ⁡ O ( log ⁡ n ) {displaystyle n^{2}/exp O({sqrt {log n}})} рёбрами.

Среди планарных графов максимальное число рёбер в локально линейном графе с n {displaystyle n} вершинами равно 12 5 ( n − 2 ) {displaystyle { frac {12}{5}}(n-2)} . Граф кубооктаэдра является первым в бесконечной последовательности полиэдральных графов с n = 5 k + 2 {displaystyle n=5k+2} вершинами и 12 5 ( n − 2 ) = 12 k {displaystyle { frac {12}{5}}(n-2)=12k} рёбрами для k = 2 , 3 , … {displaystyle k=2,3,dots } , построенными путём расширения квадратных граней K 2 , k {displaystyle K_{2,k}} в антипризмы. Эти примеры показывают, что эта верхняя граница точна.