Kvartični graf

4-regularni 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.[1] 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:

tako da je pri kvartičnem grafu število povezav enako dvojnemu številu točk ():

ZglediUredi

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

Vsak sredinski graf je kvartični ravninski graf, in vsak kvartični ravninski graf je sredinski graf parov dualnih ravninskih grafov ali multigrafov.[7] 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.[8]

ZnačilnostiUredi

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.[9]

Kvartični grafi imajo liho število Hamiltonovih dekompozicij.[10]

Š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 K5 in oktaedrski graf. Cirkulantna grafa C7(1,2) in C7(1,3) sta med seboj izomorfna. Na 7-ih točkah obstaja le še en tema grafoma neizomorfen graf.

Odprti problemiUredi

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.[11]

Glej tudiUredi

SkliciUredi

ViriUredi

  • 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, 55, Amsterdam: North-Holland, str. 159–171, doi:10.1016/S0167-5060(08)70385-6, MR 1217989

Zunanje povezaveUredi