Kvartový graf - Quartic graph
V matematický pole teorie grafů, a kvartový graf je graf kde všichni vrcholy mít stupeň 4. Jinými slovy, kvartový graf je 4běžný graf.[1]
Příklady
Několik známých grafů je kvartálních. Obsahují:
- The kompletní graf K.5, kvartový graf s 5 vrcholy, nejmenší možný kvartový graf.
- The Chvátalův graf, další kvartový graf s 12 vrcholy, nejmenší kvartový graf, který oba nemá trojúhelníky a nemůže být barevný se třemi barvami.[2]
- The Folkmanův graf, kvartový graf s 20 vrcholy, nejmenší polosymetrický graf.[3]
- The Meredithův graf, kvartový graf se 70 vrcholy, který je 4-připojeno ale nemá Hamiltonianův cyklus, vyvrací domněnku Crispin Nash-Williams.[4]
Každý mediální graf je kvartál rovinný graf a každý graf kvartické roviny je mediálním grafem dvojice grafů nebo multigrafů v duální rovině.[5] Uzlové diagramy a spojovací diagramy jsou také kvartická rovina multigrafy, ve kterém vrcholy představují křížení diagramu a jsou označeny dalšími informacemi o tom, která ze dvou větví uzlu protíná druhou větev v daném bodě.[6]
Vlastnosti
Protože stupeň každého vrcholu v kvartovém grafu je sudý, každý připojeno kvartový graf má Prohlídka Euler.A stejně jako u běžných bipartitních grafů obecněji, každý bipartitní kvartový graf má a perfektní shoda. V tomto případě mnohem jednodušší a rychlejší algoritmus pro nalezení takové shody je možné než pro nepravidelné grafy: výběrem všech ostatních okrajů prohlídky Euler, jeden může najít 2-faktor, což v tomto případě musí být soubor cyklů, každý se sudou délkou, přičemž každý vrchol grafu se objeví přesně v jednom cyklu. Když v těchto cyklech znovu vyberete všechny ostatní hrany, získáte perfektní shodu lineární čas. Stejnou metodu lze také použít vybarvujte okraje grafu se čtyřmi barvami v lineárním čase.[7]
Kvarové grafy mají sudý počet Hamiltonovské rozklady.[8]
Otevřené problémy
Jde o otevřenou domněnku, zda mají všechny kvartické hamiltonovské grafy sudý počet Hamiltonovské obvody, nebo mají více než jeden Hamiltonovský okruh. O odpovědi je známo, že je nepravdivá pro kvartiku multigrafy.[9]
Viz také
Reference
- ^ Toida, S. (1974), "Konstrukce křemenných grafů", Journal of Combinatorial Theory, Řada B, 16: 124–133, doi:10.1016/0095-8956(74)90054-9, PAN 0347693.
- ^ Chvátal, V. (1970), „Nejmenší 4-chromatický 4-pravidelný graf bez trojúhelníků“, Journal of Combinatorial Theory, 9 (1): 93–94, doi:10.1016 / S0021-9800 (70) 80057-6.
- ^ Folkman, Jon (1967), „Pravidelné lineárně symetrické grafy“, Journal of Combinatorial Theory, 3: 215–232, doi:10.1016 / s0021-9800 (67) 80069-3, PAN 0224498.
- ^ Meredith, G. H. J. (1973), „Regular n-valentní n-nepojené neHamiltonovské ne-n-obrázkové barvy ", Journal of Combinatorial Theory, Řada B, 14: 55–60, doi:10.1016 / s0095-8956 (73) 80006-1, PAN 0311503.
- ^ Bondy, J. A .; Häggkvist, R. (1981), „Edge-disjoint Hamiltonovy cykly ve 4-pravidelných rovinných grafech“, Aequationes Mathematicae, 22 (1): 42–45, doi:10.1007 / BF02190157, PAN 0623315.
- ^ Velština, Dominic J. A. (1993), „Složitost uzlů“, Quo vadis, teorie grafů?, Annals of Discrete Mathematics, 55, Amsterdam: Severní Holandsko, s. 159–171, doi:10.1016 / S0167-5060 (08) 70385-6, PAN 1217989.
- ^ Gabow, Harold N. (1976), „Použití oddílů Euler k okrajovým barevným bipartitním multigrafům“, International Journal of Computer and Information Sciences, 5 (4): 345–355, doi:10.1007 / bf00998632, PAN 0422081.
- ^ Thomason, A. G. (1978), „Hamiltonovské cykly a jedinečně zbarvitelné grafy hran“, Annals of Discrete Mathematics, 3: 259–268, doi:10.1016 / s0167-5060 (08) 70511-9, PAN 0499124.
- ^ Fleischner, Herbert (1994), „Jedinečnost maximálních dominujících cyklů ve 3 pravidelných grafech a Hamiltonovských cyklů ve 4 pravidelných grafech“, Journal of Graph Theory, 18 (5): 449–459, doi:10,1002 / jgt.3190180503, PAN 1283310.