Interested Article - Инвариант Колен де Вердьера

Инвариант Колен де Вердьера — характеристика графа $\mu (G)$ , определённая для любого графа G , введённая в 1990 году в процессе исследования кратности второго собственного значения некоторых операторов Шрёдингера .

Определение

Пусть $G=(V,E)$ — простой (не содержащий петель и кратных рёбер) ациклический граф. Без потери общности поименуем множество вершин следующим образом: $V=\{1,\dots ,n\}$ . Тогда $\mu (G)$ — наибольший коранг любой такой матрицы $M=(M_{i,j})\in \mathbb {R} ^{(n)}$ , что:

(M1) для любых $i,j$ , где $i\neq j$ : $M_{i,j}<0$ , если i и j смежны, и $M_{i,j}=0$ , в противном случае
(M2) M имеет ровно одно собственное значение кратности 1;
(M3) не существует такой ненулевой матрицы $X=(X_{i,j})\in \mathbb {R} ^{(n)}$ , что $MX=0$ , и что $X_{i,j}=0$ всякий раз, когда $i=j$ или $M_{i,j}\neq 0$ .

Классификация известных групп графов

С точки зрения инварианта Колен де Вердьера, некоторые хорошо известные семейства графов обладают характерными особенностями:

$\mu (K_{1})=0$ , $\mu (K_{n})=n-1$ , $\mu ({\overline {K_{n}}})=1$ при $n>1$ ;
μ ≤ 1 тогда и только тогда, когда G является линейным лесом (лесом, в котором каждый компонент является путём, то есть инцидентность любой вершины не больше 2);
μ ≤ 2 тогда и только тогда, когда G является внешнепланарным графом (все вершины лежат на одной грани);
μ ≤ 3 тогда и только тогда, когда G является планарным графом ;
μ ≤ 4 тогда и только тогда, когда G является бессвязно встраиваемым , то есть не существует двух циклов в G , для которых при отображении на евклидово пространство (коэффициент зацепления) равен нулю.

Эти же группы графов проявляют свои отличительные черты и при анализе связи между инвариантом графа и дополнением этого графа:

Если дополнение графа с n вершинами является линейным лесом, то μ ≥ n − 3 ;
Если дополнение графа с n вершинами является внешнепланарным графом, то μ ≥ n − 4 ;
Если дополнение графа с n вершинами является планарным графом, то μ ≥ n − 5 .

Миноры графов

Минором графа G называют граф H , полученный из G последовательным удалением вершин, удалением рёбер и сжатием рёбер. Инвариант Колена де Вердьера монотонен относительно операции взятия минора в том смысле, что минорирование графа не может увеличить его инвариант:

Если H является минором G , то

\mu (H)\leq \mu (G)

.

По теореме Робертсона — Сеймура , для любого k существует H , конечное множество графов такое, что для любого графа с инвариантом не более k графы из H не могут быть минорами. В работе ( ) перечисляются множества таких недопустимых миноров для k ≤ 3; для k = 4 множество недопустимых миноров состоит из семи графов по определению бессвязно встраиваемого графа как графа с μ ≤ 4 и без графов Петерсена в качестве миноров.

Связь с хроматическим числом

( ) предположил, что любой граф с инвариантом де Вердьера μ может быть раскрашен с использованием не более чем μ + 1 цветов. Например, у линейных лесов (компоненты которых являются двудольными графами) инвариант равняется 1; у внешнепланарных графов инвариант равняется 2, и они могут быть раскрашены тремя цветами; у планарных графов инвариант — 3, и они могут быть раскрашены четырьмя цветами .

Для графов с инвариантом де Вердьера не более четырёх предположение истинно; они все являются бессвязно встраиваемыми, и тот факт, что они раскрашиваются пятью цветами, является следствием доказательства гипотезы Хадвигера для графов без миноров типа K ₆ в работе ( ).

Другие свойства

Если число пересечений графа равно k , то инвариант де Вердьера для него будет не более k + 3. Например, графы Куратовского K ₅ и K _3,3 могут быть изображены с одним пересечением, и инвариант для них будет не более четырёх.

Примечания

↑ ( ).
↑ ( ).
В работе ( ) этот случай явным образом не рассмотрен, но он явным образом вытекает из результатов анализа графов, не имеющих миноров вида «треугольник» и « клешня ».
↑ ( ).
↑ ( ).

Ссылки

(1990), "Sur un nouvel invariant des graphes et un critère de planarité", Journal of Combinatorial Theory, Series B , 50 (1): 11—21, doi : . Translated by Neil Calkin as (1993), "On a new graph invariant and a criterion for planarity", in ; (eds.), Graph Structure Theory: Proc. AMS–IMS–SIAM Joint Summer Research Conference on Graph Minors , Contemporary Mathematics, vol. 147, American Mathematical Society, pp. 137—147 .
van der Holst, Hein; Lovász, László ; Schrijver, Alexander (1999), "The Colin de Verdière graph parameter", , Bolyai Soc. Math. Stud., vol. 7, Budapest: János Bolyai Math. Soc., pp. 29—85 .
Kotlov, Andrew; Lovász, László ; Vempala, Santosh (1997), , Combinatorica , 17 (4): 483—521, doi :
Lovász, László ; Schrijver, Alexander (1998), "A Borsuk theorem for antipodal links and a spectral characterization of linklessly embeddable graphs", Proceedings of the American Mathematical Society , 126 (5): 1275—1285, doi : .
; ; (1993), (PDF) , , 13 : 279—361, doi : .