Kvartični graf

Kvártični gráf je v teoriji grafov graf v katerem imajo vse točke stopnjo enako 4 in je tako 4-regularni graf. Kvartični graf se imenuje tudi štírivaléntni graf. Po lemi o rokovanju je v vsakem regularnem grafu na n točkah s stopnjo r število povezav enako:

$e={\frac {nr}{2}}\!\,,$

tako da je pri kvartičnem grafu število povezav enako dvojnemu številu točk ($r=4\,$):

$e=2n\!\,.$

Zgledi

Več dobro znanih grafov je kvartičnih. Med njimi so:

• polni graf K₅, graf 5-celice, kvartični graf s 5-imi točkami, najmanjši možni kvartični graf in edini na 5-ih točkah.
• cirkulantna grafa C₇(1,2) in C₇(1,3), kvartična grafa s 7-imi točkami. Grafa sta med seboj izomorfna.
• polni dvodelni graf K_(4,4), kvartični graf z 8-imi točkami.
• trdnjavin graf 3×3, Paleyjev graf reda 9, kvartični graf z 9-imi točkami.
• krona $S_{5}^{0}$, kvartični graf z 10-imi točkami.
• Chvátalov graf, kvartični graf z 12-imi točkami, najmanjši kvartični graf brez trikotnikov, ki se ga ne da pobarvati s tremi barvami.
• poliedrski grafi
  • platonski grafi – od 5-ih platonskih grafov je en kvartičen:
    • oktaedrski graf s 6-imi točkami, poliedrski graf oktaedra. Posebni primer Turánovega grafa T(6,3) = K_2,2,2. Edini kvartični graf na 6-ih točkah.
  • arhimedski grafi – od 13-ih arhimedskih grafov so štirje kvartični:
    • kubooktaedrski graf z 12-imi točkami, poliedrski graf kubooktaedra.
    • ikozidodekaedrski graf s 30-imi točkami, poliedrski graf ikozidodekaedra.
    • rombikubooktaedrski graf z 48-imi točkami, poliedrski graf rombikubooktaedra
    • rombiikozidodekaedrski graf s 60-imi točkami, poliedrski graf rombiikozidodekaedra.
  • grafi Johnsonovih teles – od 92-ih grafov Johnsonovih teles so trije kvartični:
    • graf podaljšane kvadratne bipiramide z 10-imi točkami
    • graf trikotniške ortobikupole z 12-imi točkami
    • graf trojnopovečane šeststrane prizme s 55-imi točkami
  • grafi antiprizm brez tetraedra
• polihoronski grafi
  • graf teserakta s 16-imi točkami, polihoronski graf teserakta
  • graf 120-celice s 600-imi točkami, polihoronski graf 120-celice
• Robertsonov graf, kvartični graf z 19-imi točkami, najmanjši kvartični graf z obsegom 5.
• Hoffmanov graf, kvartični graf s 16-imi točkami, kospektralni hiperkockin graf Q₄ (teserakta).
• Folkmanov graf, kvartični graf z 20-imi točkami, najmanjši polsimetrični graf.
• Brinkmannov graf, kvartični graf z 21-imi točkami, najmanjši kvartični graf z obsegom 5 in kromatičnim številom 4.
• Holtov graf, kvartični graf s 27-imi točkami, najmanjši polprehodni graf.
• Meredithov graf, kvartični graf s 70-imi točkami, ki je 4-točkovno-povezan vendar nima Hamiltonovega cikla, in je protiprimer domneve Crispina Nash-Williamsa, da je vsak kvartični graf 4-točkovno-povezan graf Hamiltonov.

• 
  Polni graf K₅
  graf 5-celice
• 
  Oktaedrski graf
  (graf trikotniške antiprizme)
• 
  Cirkulantni graf $C_{7}(1,2)\,$
• 
  Cirkulantni graf $C_{7}(1,3)\,$
• 
  Kvartični graf na 7-ih točkah
• 
  Polni dvodelni graf K_(4,4)
• 
  Trdnjavin graf 3×3, Paleyjev graf reda 9
• 
  Chvátalov graf
• 
  Kubooktaedrski graf
• 
  Hiperkockin graf Q₄ (graf teserakta)
• 
  Hoffmanov graf
• 
  Robertsonov graf
• 
  Folkmanov graf
• 
  Brinkmannov graf
• 
  Holtov graf
• 
  Ikozidodekaedrski graf
• 
  Rombikubooktaedrski graf
• 
  Rombiikozidodekaedrski graf
• 
  Meredithov graf
• 
  Graf 120-celice

Vsak sredinski graf je kvartični ravninski graf, in vsak kvartični ravninski graf je sredinski graf parov dualnih ravninskih grafov ali multigrafov. Vozelni diagrami in povezavni diagrami so tudi kvartični ravninski multigrafi v katerih točke predstavljajo presekanja diagramov in so označeni z dodatno informacijo, ki pove katera od dveh vej vozla prečka drugo vejo v tisti točki.

Značilnosti

Ker je stopnja vsake točke v kvartičnem grafu soda, ima vsak povezani kvartični graf Eulerjevo pot. In kakor za regularne dvodelne grafe v splošnem ima vsak dvodelni kvartični graf popolno parjenje. V tem primeru je možen veliko preprostejši in hitrejši algoritem za iskanje takšnega parjenja kot pri neregularnih grafih – z zbiranjem katerekoli druge povezave Eulerjeve poti se lahko najde 2-faktor, ki mora v tem primeru biti zbirka krožnic, vsaka z liho dolžino, kjer se vsaka točka grafa pojavi točno v eni krožnici. S ponovno izbiro katerekoli druge povezave v teh krožnicah se lahko dobi popolno parjenje v linearnem času. Enaka metoda se lahko uporabi za barvanje povezav grafa s štirimi barvami v linearnem času.

Kvartični grafi imajo liho število Hamiltonovih dekompozicij.

Število možnih neizomorfnih povezanih kvartičnih grafov na n ≥ 0 točkah je: (OEIS A006820):

1, 0, 0, 0, 0, 1, 1, 2, 6, 16, 59, 265, 1544, 10778, 88168, 805491, 8037418, 86221634, 985870522, 11946487647, 152808063181, 2056692014474, 28566273166527, ...

Pri tem velja, da regularnost ničelnega grafa brez točk (n = 0) ni definirana in je tako lahko poljubna, zato je graf tudi 4-regularen. Na 5-ih in 6-ih točkah sta edina neizomorfna grafa polni graf K₅ in oktaedrski graf. Cirkulantna grafa C₇(1,2) in C₇(1,3) sta med seboj izomorfna. Na 7-ih točkah obstaja le še en tema grafoma neizomorfen graf.

Odprti problemi

Ali imajo vsi kvartični grafi liho število Hamiltonovih ciklov ali imajo več kot enega je odprta domneva. Izjava ne velja za kvartične multigrafe.

Glej tudi

• kubični graf
• kvintični graf

Viri

• Bondy, John Adrian; Häggkvist, Roland (1981), »Edge-disjoint Hamilton cycles in 4-regular planar graphs«, Aequationes Mathematicae, 22 (1): 42–45, doi:10.1007/BF02190157, MR 0623315
• Brinkmann, Gunnar; Meringer, Markus (1997), »The Smallest 4-Regular 4-Chromatic Graphs with Girth 5«, Graph Theory Notes of New York, 32: 40–41
• Chvátal, Václav (1970), »The smallest triangle-free 4-chromatic 4-regular graph«, Journal of Combinatorial Theory, 9 (1): 93–94, doi:10.1016/S0021-9800(70)80057-6
• Fleischner, Herbert (1994), »Uniqueness of maximal dominating cycles in 3-regular graphs and of Hamiltonian cycles in 4-regular graphs«, Journal of Graph Theory, 18 (5): 449–459, doi:10.1002/jgt.3190180503, MR 1283310
• Folkman, Jon (1967), »Regular line-symmetric graphs«, Journal of Combinatorial Theory, 3: 215–232, doi:10.1016/s0021-9800(67)80069-3, MR 0224498
• Gabow, Harold N. (1976), »Using Euler partitions to edge color bipartite multigraphs«, International Journal of Computer and Information Sciences, 5 (4): 345–355, doi:10.1007/bf00998632, MR 0422081
• Meredith, Guy H. J. (1973), »Regular n-valent n-connected nonHamiltonian non-n-edge-colorable graphs«, Journal of Combinatorial Theory, Series B, 14: 55–60, doi:10.1016/s0095-8956(73)80006-1, MR 0311503
• Robertson, Neil (1964), »The Smallest Graph of Girth 5 and Valency 4«, Bull. Amer. Math. Soc., 70: 824–825
• Thomason, Andrew Gordon (1978), »Hamiltonian cycles and uniquely edge colourable graphs«, Annals of Discrete Mathematics, 3: 259–268, doi:10.1016/s0167-5060(08)70511-9, MR 0499124
• Toida, Šuniči (1974), »Construction of quartic graphs«, Journal of Combinatorial Theory, Series B, 16: 124–133, doi:10.1016/0095-8956(74)90054-9, MR 0347693
• Welsh, Dominic J. A. (1993), »The complexity of knots«, Quo vadis, graph theory?, Annals of Discrete Mathematics, zv. 55, Amsterdam: North-Holland, str. 159–171, doi:10.1016/S0167-5060(08)70385-6, MR 1217989

Zunanje povezave

• Weisstein, Eric Wolfgang. »Quartic Graph«. MathWorld.