Colin de Verdière graf invariantní - Colin de Verdière graph invariant
Colin de Verdière je neměnný je parametr grafu pro všechny graf G, představil Yves Colin de Verdière v roce 1990. Bylo to motivováno studiem maximální multiplicity druhého vlastní číslo jisté Provozovatelé Schrödinger.[1]
Definice
Nechat být bezmocný jednoduchý graf. Předpokládejme to bez ztráty obecnosti . Pak je největší klika ze všech symetrická matice takové, že:
- (M1) pro všechny s : -li , a -li ;
- (M2) M má přesně jednu zápornou vlastní hodnotu, multiplicitu 1;
- (M3) neexistuje nenulová matice takhle a takhle pokud ano nebo držet.[1][2]
Charakterizace známých rodin grafů
Několik známých rodin grafů lze charakterizovat z hlediska jejich Colin de Verdière invariants:
- μ ≤ 0 kdyby a jen kdyby G má žádné hrany;[1][2]
- μ ≤ 1 kdyby a jen kdyby G je lineární les (disjunktní spojení cest);[1][3]
- μ ≤ 2 kdyby a jen kdyby G je vnější rovinný;[1][2]
- μ ≤ 3 kdyby a jen kdyby G je rovinný;[1][2]
- μ ≤ 4 kdyby a jen kdyby G je bez vložení grafu[1][4]
Tyto stejné rodiny grafů se také objevují ve spojeních mezi Colin de Verdière invariantem grafu a strukturou jeho doplňkový graf:
- Pokud doplněk an n-vrcholový graf je tedy lineární les μ ≥ n − 3;[1][5]
- Pokud doplněk an n-vrcholový graf je tedy vnější rovinný μ ≥ n − 4;[1][5]
- Pokud doplněk an n-vrcholový graf je tedy rovinný μ ≥ n − 5.[1][5]
Graf nezletilí
A Méně důležitý grafu je další graf z něj vytvořený smrštěním hran a odstraněním hran a vrcholů. Colin de Verdière invariant je minor-monotónní, což znamená, že převzetí minor z grafu může jeho invariant pouze zmenšit nebo ponechat beze změny:
- Li H je nezletilá z G pak .[2]
Podle Věta Robertson – Seymour, pro každého k existuje konečná množina H grafů tak, aby grafy byly maximálně invariantní k jsou stejné jako grafy, které nemají žádného člena H jako nezletilý. Colin de Verdière (1990) uvádí tyto sady zakázané nezletilé pro k ≤ 3; pro k = 4 sada zakázaných nezletilých se skládá ze sedmi grafů v Petersenova rodina, vzhledem ke dvěma charakteristikám bez vložení grafů jako grafy s μ ≤ 4 a jako grafy bez menší rodiny Petersenů.[4] Pro k = 5 sada zakázaných nezletilých obsahuje 78 grafů rodiny Heawoodů a předpokládá se, že jich již není.[6]
Chromatické číslo
Colin de Verdière (1990) domníval se, že jakýkoli graf s Colin de Verdièrovým invariantem μ může být barevný s maximálně μ + 1 barvami. Například lineární lesy mají invariant 1 a mohou být 2-barevné; the vnější rovinné grafy mít invariantní dva a mohou být 3-barevné; the rovinné grafy mít invariant 3 a (podle čtyřbarevná věta ) může být čtyřbarevný.
U grafů s Colinem de Verdièrem invariantním nejvýše čtyřmi zůstává domněnka pravdivá; tohle jsou propojitelné grafy bez možnosti propojení a skutečnost, že mají chromatické číslo nejvýše pět, je důsledkem důkazu od Neil Robertson, Paul Seymour, a Robin Thomas (1993 ) z Hadwigerův dohad pro K.6- bezvýznamné grafy.
Další vlastnosti
Pokud má graf číslo křížení , má Colin de Verdière maximálně invariantní . Například dva Kuratowski grafy a lze oba nakreslit jedním křížením a mít Colin de Verdière invariantní maximálně čtyři.[2]
Vliv
Colin de Verdière invariant je definován ze speciální třídy matic odpovídající grafu namísto jediné matice související s grafem. Ve stejných liniích jsou definovány a studovány další parametry grafu, například minimální hodnocení grafu, minimální semidefinitní hodnost grafu a minimální šikmá pozice grafu.
Poznámky
- ^ A b C d E F G h i j van der Holst, Lovász & Schrijver (1999).
- ^ A b C d E F Colin de Verdière (1990).
- ^ Colin de Verdière (1990) tento případ výslovně neuvádí, ale vyplývá to z jeho charakterizace těchto grafů jako grafů s č trojúhelníkový graf nebo dráp Méně důležitý.
- ^ A b Lovász & Schrijver (1998).
- ^ A b C Kotlov, Lovász & Vempala (1997).
- ^ Hein van der Holst (2006). „Grafy a překážky ve čtyřech rozměrech“ (PDF). Journal of Combinatorial Theory, Řada B. 96 (3): 388–404. doi:10.1016 / j.jctb.2005.09.004.
Reference
- Colin de Verdière, Yves (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. Přeložil Neil Calkin jako Colin de Verdière, Yves (1993), "Na novém invariantu grafu a kritériu pro rovinnost", v Robertson, Neil; Seymour, Paule (eds.), Teorie struktury grafu: Proc. Společná letní výzkumná konference AMS – IMS – SIAM o nezletilých grafech, Současná matematika, 147, American Mathematical Society, str. 137–147.
- van der Holst, Hein; Lovász, László; Schrijver, Alexander (1999), „The Colin de Verdière graph parameter“, Teorie grafů a kombinatorická biologie (Balatonlelle, 1996), Bolyai Soc. Matematika. Stud., 7, Budapešť: János Bolyai Math. Soc., S. 29–85.
- Kotlov, Andrew; Lovász, László; Vempala, Santosh (1997), „Colin de Verdiere číslo a koule reprezentace grafu“, Combinatorica, 17 (4): 483–521, doi:10.1007 / BF01195002
- Lovász, László; Schrijver, Alexander (1998), „Borsukova věta o antipodálních vazbách a spektrální charakterizace bezlinkově zabudovatelných grafů“, Proceedings of the American Mathematical Society, 126 (5): 1275–1285, doi:10.1090 / S0002-9939-98-04244-0.
- Robertson, Neil; Seymour, Paule; Thomas, Robin (1993), „Hadwigerova domněnka o K.6-bezplatné grafy " (PDF), Combinatorica, 13: 279–361, doi:10.1007 / BF01202354.