Инвариант графа Колена де Вердьера

Инвариант Колена де Вердьера является параметром графа. $\mu (G)$ для любого графа G, введенный Ивом Коленом де Вердьером в 1990 году. Это было мотивировано изучением максимальной кратности второго собственного значения некоторых операторов Шредингера . ^{[ 1 ]}

Определение

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

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

Характеристика известных семейств графов

Несколько известных семейств графов можно охарактеризовать в терминах их инвариантов Колена де Вердьера:

µ ≤ 0 тогда и только тогда, когда G имеет только одну вершину; ^{[ 1 ]}^{[ 2 ]}
µ ≤ 1 тогда и только тогда, когда G — линейный лес (несвязное объединение путей); ^{[ 1 ]}^{[ 3 ]}
µ ≤ 2 тогда и только тогда, G внешнепланарна когда ; ^{[ 1 ]}^{[ 2 ]}
µ ≤ 3 тогда и только тогда, G плоская когда ; ^{[ 1 ]}^{[ 2 ]}
µ ≤ 4 тогда и только тогда, когда G бесзвенно вложима в R ³. ^{[ 1 ]}^{[ 4 ]}

Эти же самые семейства графов проявляются также в связях между инвариантом Колена де Вердьера графа и структурой его дополнения :

Если дополнение n -вершинного графа представляет собой линейный лес, то µ ≥ n − 3 ; ^{[ 1 ]}^{[ 5 ]}
Если дополнение n -вершинного графа внешнепланарно, то µ ≥ n − 4 ; ^{[ 1 ]}^{[ 5 ]}
Если дополнение n -вершинного графа плоское, то µ ≥ n − 5 . ^{[ 1 ]}^{[ 5 ]}

Миноры графа

Минор . графа — это другой граф, образованный из него путем стягивания ребер и удаления ребер и вершин Инвариант Колена де Вердьера является минорно-монотонным, что означает, что взятие минора графа может только уменьшить или оставить неизменным его инвариант:

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

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

. ^{[ 2 ]}

По теореме Робертсона-Сеймура для каждого k существует конечное множество H графов такое, что графы с инвариантом не выше k совпадают с графами, которые не имеют ни одного члена H в качестве минора. Колен де Вердьер (1990) перечисляет эти наборы запрещенных несовершеннолетних для k ≤ 3; для k = 4 набор запрещенных миноров состоит из семи графов семейства Петерсена из-за двух характеристик бесзвенно встраиваемых графов как графов с µ ≤ 4 и как графов без минора семейства Петерсена. ^{[ 4 ]} При k = 5 множество запрещенных миноров включает 78 графов семейства Хивуда , и предполагается, что этот список полон. ^{[ 6 ]}

Хроматическое число

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

Для графов с инвариантом Колена де Вердьера не более четырех гипотеза остается верной; это бессвязно встраиваемые графы , и тот факт, что они имеют хроматическое число не более пяти, является следствием доказательства Нилом Робертсоном , Полом Сеймуром и Робином Томасом ( 1993 ) гипотезы Хадвигера для K6 _{графов, свободных от} -минорных.

Другие объекты недвижимости

Если график имеет номер пересечения $k$ , он имеет не более чем инвариант Колена де Вердьера $k+3$ . Например, два Куратовского графа $K_{5}$ и $K_{3,3}$ оба могут быть нарисованы с одним пересечением и иметь не более четырех инвариантов Колена де Вердьера. ^{[ 2 ]}

Влияние

Инвариант Колена де Вердьера определяется через класс матриц, соответствующих графу, а не через одну матрицу. Аналогичным образом можно определить и изучить другие параметры графа, такие как минимальный ранг , минимальный полуопределенный ранг и минимальный ранг перекоса .

Примечания

^ Jump up to: ^а ^б ^с ^д ^и ^ж ^г ^час ^я ^дж ван дер Хольст, Ловас и Шрийвер (1999) .
^ Jump up to: ^а ^б ^с ^д ^и ^ж Колен де Вердьер (1990) .
^ Колен де Вердьер (1990) не формулирует этот случай явно, но это следует из его характеристики этих графов как графов без треугольников или второстепенных когтей .
^ Jump up to: ^а ^б Ловас и Шрийвер (1998) .
^ Jump up to: ^а ^б ^с Котлов, Ловас и Вемпала (1997) .
^ Хайн ван дер Холст (2006). «Графы и препятствия в четырех измерениях» (PDF) . Журнал комбинаторной теории , серия B. 96 (3): 388–404. дои : 10.1016/j.jctb.2005.09.004 .

Ссылки

Колен де Вердьер, Ив (1990), «О новом инварианте графа и критерии планарности», Журнал комбинаторной теории, серия B , 50 (1): 11–21, doi : 10.1016/0095-8956(90) 90093- Ф. Переведено Нилом Дж. Калкиным как Колен де Вердьер, Ив (1993), «О новом инварианте графа и критерии планарности», Робертсон, Нил ; Сеймур, Пол (ред.), Теория структуры графов: Proc. Совместная летняя исследовательская конференция AMS – IMS – SIAM по минорным графам , Современная математика, том. 147, Американское математическое общество, стр. 137–147 .
ван дер Хольст, Хейн; Ловас, Ласло ; Шрийвер, Александр (1999), «Параметр графа Колена де Вердьера», Теория графов и комбинаторная биология (Balatonlelle, 1996) , Bolyai Soc. Математика. Студ., вып. 7, Будапешт: Янош Бойай Матем. Соц., с. 29–85, заархивировано из оригинала 03 марта 2016 г. , получено 6 августа 2010 г.
Котлов, Андрей; Ловас, Ласло ; Вемпала, Сантош (1997), «Число Колина де Вердьера и сферические представления графа» , Combinatorica , 17 (4): 483–521, doi : 10.1007/BF01195002 , заархивировано из оригинала 03 марта 2016 г. , извлечено 06.08.2010
Ловас, Ласло ; Шрийвер, Александр (1998), «Теорема Борсука для антиподальных связей и спектральная характеристика бессвязно встраиваемых графов», Proceedings of the American Mathematical Society , 126 (5): 1275–1285, doi : 10.1090/S0002-9939-98- 04244-0 .
Робертсон, Нил ; Сеймур, Пол ; Томас, Робин (1993), «Гипотеза Хадвигера для _{K 6} графов, свободных от » (PDF) , Combinatorica , 13 : 279–361, doi : 10.1007/BF01202354 , заархивировано из оригинала (PDF) 10 апреля 2009 г. , получено 06 августа 2010 г.

[hls99-1] Jump up to: ^а ^б ^с ^д ^и ^ж ^г ^час ^я ^дж ван дер Хольст, Ловас и Шрийвер (1999) .

[cdv90-2] Jump up to: ^а ^б ^с ^д ^и ^ж Колен де Вердьер (1990) .

[3] Колен де Вердьер (1990) не формулирует этот случай явно, но это следует из его характеристики этих графов как графов без треугольников или второстепенных когтей .

[ls98-4] Jump up to: ^а ^б Ловас и Шрийвер (1998) .

[klv97-5] Jump up to: ^а ^б ^с Котлов, Ловас и Вемпала (1997) .

[6] Хайн ван дер Холст (2006). «Графы и препятствия в четырех измерениях» (PDF) . Журнал комбинаторной теории , серия B. 96 (3): 388–404. дои : 10.1016/j.jctb.2005.09.004 .

[ 1 ]

[ 2 ]

[ 3 ]

[ 4 ]

[ 5 ]

[ 6 ]