Інваріант Колен де Вердьєра

Інваріа́нт Колен де Вердьєра — характеристика графа $\mu (G)$ , визначена для будь-якого графа $G$ , яку 1990 року ввів Ів Колен де Вердьє в процесі дослідження кратності другого власного значення деяких операторів Шредінгера[1].

Визначення

Нехай $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\}\in E$ , і $M_{i,j}=0$ , якщо $\{i,j\}\notin E$ ;
(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$ [2][1].

Класифікація відомих груп графів

З точки зору інваріанта Колен де Вердьєра, деякі добре відомі сімейства графів мають характерні особливості:

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

Ці ж групи графів проявляють свої відмінні риси і під час аналізу зв'язку між інваріантом графа і доповненням цього графа:

Якщо доповнення графа з n вершинами є лінійним лісом, то μ ≥ n − 3;[1][5]
Якщо доповнення графа з n вершинами є зовніпланарним графом, то μ ≥ n − 4;[1][5]
Якщо доповнення графа з n вершинами є планарним графом, то μ ≥ n − 5.[1][5]

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

Мінором графа G називають граф H, отриманий з G послідовним видаленням вершин, видаленням ребер і стисненням ребер. Інваріант Колена де Вердьєра монотонний відносно операції взяття мінора в тому сенсі, що мінорування графа не може збільшити його інваріанта:

Якщо H є мінором G, то

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

.[2]

В теоремі Робертсона — Сеймура, для будь-якого k існує H, скінченна множина графів така, що для будь-якого графа з інваріантом не більшим від k графи з H не можуть бути мінорами. В роботі (Colin de Verdière, 1990) перелічено множини таких недопустимих мінорів для k ≤ 3; для k = 4 множина недопустимих мінорів складається з семи графів сімейства Петерсена за визначенням незачеплено вкладеного графа як графа з μ ≤ 4 і без графів Петерсена як мінорів[4].

Зв'язок із хроматичним числом

Колен де Вердьєр (Colin de Verdière, 1990) припустив, що будь-який граф з інваріантом де Вердьера μ можна розфарбувати з використанням не больше ніж μ + 1 кольорів. Наприклад, у лінійних лісів (компоненти яких є двочастковими графами) інваріант дорівнює 1; у зовніпланарних графів інваріант дорівнює 2 і їх можна розфарбувати трьома кольорами; у планарних графів інваріант — 3 і їх можна розфарбувати чотирма кольорами.

Для графів з інваріантом де Вердьєра не більше чотирьох припущення істинне; вони всі є незачеплено вкладаними, і той факт, що вони розфарбовуються п'ятьма кольорами, є наслідком доведення гіпотези Хадвігера для графів без мінорів типу K₆ у роботі Робертсона, Сеймура та Томаса (Robertson, Seymour та Thomas, 1993).

Інші властивості

Якщо число перетинів графа дорівнює k, то інваріант де Вердьєра для нього буде не більшим ніж k + 3. Наприклад, графи Куратовського K₅ і K_3,3 можна зобразити з одним перетином, і інваріант для них буде не більшим від чотирьох[2].

Примітки

(van der Holst, Lovász та Schrijver, 1999).
(Colin de Verdière, 1990).
В работе (Colin de Verdière, 1990) этот случай явным образом не рассмотрен, но он явным образом вытекает из результатов анализа графов, не имеющих миноров вида «треугольник» и «клешня».
(Lovász та Schrijver, 1998).
(Kotlov, Lovász та Vempala, 1997).

Посилання

Colin de Verdière, Y. (1990). Sur un nouvel invariant des graphes et un critère de planarité. Journal of Combinatorial Theory, Series B 50 (1): 11–21. doi:10.1016/0095-8956(90)90093-F.
van der Holst, Hein; Lovász, László; Schrijver, Alexander (1999). The Colin de Verdière graph parameter. Graph Theory and Combinatorial Biology (Balatonlelle, 1996). Bolyai Soc. Math. Stud. 7. Budapest: János Bolyai Math. Soc. с. 29–85..
Kotlov, Andrew; Lovász, László; Vempala, Santosh (1997). The Colin de Verdiere number and sphere representations of a graph. Combinatorica 17 (4): 483–521. doi:10.1007/BF01195002.
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:10.1090/S0002-9939-98-04244-0..
Robertson, Neil; Seymour, Paul; Thomas, Robin (1993). Hadwiger's conjecture for K₆-free graphs. Combinatorica 13: 279–361. doi:10.1007/BF01202354..

This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.

[hls99-1] (van der Holst, Lovász та Schrijver, 1999).

[cdv90-2] (Colin de Verdière, 1990).

[3] В работе (Colin de Verdière, 1990) этот случай явным образом не рассмотрен, но он явным образом вытекает из результатов анализа графов, не имеющих миноров вида «треугольник» и «клешня».

[ls98-4] (Lovász та Schrijver, 1998).

[klv97-5] (Kotlov, Lovász та Vempala, 1997).