Граф Джонсона

Граф Джонсона
Граф Джонсона J (5,2)
Назван в честь	Селмер М. Джонсон
Вершины	${\displaystyle {\binom {n}{k}}}$
Края	${\displaystyle {\frac {1}{2}}k(nk){\binom {n}{k}}}$
Диаметр	${\displaystyle \min(k,nk)}$
Характеристики	${\displaystyle k(nk)}$-регулярный Вершинно-транзитивный Дистанционно-транзитивный Гамильтоново-связный
Обозначение	${\displaystyle J(n,k)}$
Таблица графиков и параметров

В математике графы Джонсона — это особый класс неориентированных графов, определяемых из систем множеств. Вершины графа Джонсона — это -элементные подмножества -элементного множества; две вершины являются смежными, когда пересечение двух вершин (подмножеств) содержит -элементы. ^[1] Графы Джонсона и тесно связанная с ними схема Джонсона названы в честь Селмера М. Джонсона .${\displaystyle J(n,k)}$${\displaystyle к}$${\displaystyle n}$${\displaystyle (k-1)}$

• Оба и являются полным графом K _n .${\displaystyle J(n,1)}$${\displaystyle J(n,n-1)}$
• ${\displaystyle J(4,2)}$является октаэдрическим графом .
• ${\displaystyle J(5,2)}$является дополнением графа Петерсена , ^[1] следовательно, линейным графом K ₅ . В более общем случае, для всех граф Джонсона является линейным графом K _n и дополнением графа Кнезера${\displaystyle n}$${\displaystyle J(n,2)}$ ${\displaystyle К(n,2).}$

• ${\displaystyle J(n,k)}$изоморфен​​${\displaystyle J(n,nk).}$
• Для всех любая пара вершин на расстоянии имеет общие элементы.${\displaystyle 0\leq j\leq \operatorname {диаметр} (J(n,k))}$${\displaystyle j}$${\displaystyle кдж}$
• ${\displaystyle J(n,k)}$является гамильтоново-связанным , что означает, что каждая пара вершин образует конечные точки гамильтонова пути в графе. В частности, это означает, что он имеет гамильтонов цикл . ^[2]
• Известно также, что граф Джонсона является -вершинно-связным. ^[3]${\displaystyle J(n,k)}$${\displaystyle k(nk)}$
• ${\displaystyle J(n,k)}$образует граф вершин и ребер ( n  − 1)-мерного многогранника , называемого гиперсимплексом . ^[4]
• Число клик задается выражением через его наименьшее и наибольшее собственные значения :${\displaystyle J(n,k)}$${\displaystyle \omega (J(n,k))=1-\lambda _{\max }/\lambda _{\min }.}$
• Хроматическое число не более [ ^5]${\displaystyle J(n,k)}$${\ displaystyle n, \ chi (J (n, k)) \ leq n.}$
• Каждый граф Джонсона локально решетчатый , что означает, что индуцированный подграф соседей любой вершины является графом ладьи . Точнее, в графе Джонсона каждое соседство является графом ладьи. ^[6]${\displaystyle J(n,k)}$${\displaystyle k\times (nk)}$

Существует дистанционно-транзитивная подгруппа , изоморфная . Фактически, , за исключением того, что когда , . ^[7]${\displaystyle \operatorname {Aut} (J (n,k))}$ ${\displaystyle \operatorname {Симв} (н)}$${\displaystyle \operatorname {Aut} (J(n,k))\cong \operatorname {Sym} (n)}$${\displaystyle n=2k\geq 4}$${\displaystyle \operatorname {Aut} (J(n,k))\cong \operatorname {Sym} (n)\times C_{2}}$

Как следствие транзитивности расстояния, также является дистанционно регулярным . Обозначим его диаметр , массив пересечений задается как ${\displaystyle J(n,k)}$${\displaystyle д}$${\displaystyle J(n,k)}$

${\displaystyle \left\{b_{0},\ldots ,b_{d-1},c_{1},\ldots c_{d}\right\}}$

где:

${\displaystyle {\begin{align}b_{j}&=(kj)(nkj)&&0\leq j<d\\c_{j}&=j^{2}&&0<j\leq d\end{align}}}$

Оказывается, если только не является , его массив пересечений не является общим с каким-либо другим отдельным дистанционно регулярным графом; массив пересечений является общим с тремя другими дистанционно регулярными графами, которые не являются графами Джонсона. ^[1]${\displaystyle J(n,k)}$${\displaystyle J(8,2)}$${\displaystyle J(8,2)}$

• Характеристический многочлен определяется выражением${\displaystyle J(n,k)}$

${\displaystyle \phi (x):=\prod _{j=0}^{\operatorname {diam} (J (n,k))} \left(x-A_{n,k}(j)\right )^{{\binom {n}{j}}-{\binom {n}{j-1}}}.}$

где ^[7]${\ displaystyle A_ {n, k} (j) = (kj) (nkj) -j.}$

• Собственные векторы имеют явное описание. ^[8]${\displaystyle J(n,k)}$

Граф Джонсона тесно связан со схемой Джонсона , схемой ассоциации , в которой каждая пара множеств из k -элементов связана с числом, равным половине размера симметричной разности двух множеств. ^[9] Граф Джонсона имеет ребро для каждой пары множеств на расстоянии один в схеме ассоциации, а расстояния в схеме ассоциации являются в точности кратчайшими расстояниями пути в графе Джонсона. ^[10]${\displaystyle J(n,k)}$

Схема Джонсона также связана с другим семейством дистанционно-транзитивных графов, нечетными графами , вершинами которых являются -элементные подмножества -элементного множества, а ребра соответствуют непересекающимся парам подмножеств. ^[9]${\displaystyle к}$${\displaystyle (2k+1)}$

Свойства расширения вершин графов Джонсона, а также структура соответствующих экстремальных множеств вершин заданного размера, не полностью изучены. Однако недавно была получена асимптотически точная нижняя граница расширения больших множеств вершин. ^[11]

В общем случае определение хроматического числа графа Джонсона является открытой проблемой . ^[12]

• Граф Грассмана

• Вайсштейн, Эрик В. , «Граф Джонсона», MathWorld
• Брауэр, Андрис Э. , графы Джонсона