4-reguláris gráf

A matematika, azon belül a gráfelmélet területén egy 4-reguláris gráf (angol nyelvterületen még: quartic graph) olyan reguláris gráf, melyben minden csúcs fokszáma 4.^[1]

Példák

Számos jól ismert gráf 4-reguláris. Közéjük tartoznak:

A K₅ teljes gráf, ami a legkisebb lehetséges 4-reguláris gráf.
A 12 csúcsú Chvátal-gráf, a legkisebb 4-reguláris gráf, mely nem tartalmaz háromszöget és nem színezhető ki három színnel.^[2]
A 20 csúcsú Folkman-gráf, ami a legkisebb félszimmetrikus gráf.^[3]
A 70 csúcsú Meredith-gráf, ami egyben 4-szeresen összefüggő is, de nincs Hamilton-köre, cáfolva ezzel Crispin Nash-Williams egy sejtését.^[4]

Minden mediális gráf 4-reguláris síkbarajzolható gráf, és minden 4-reguláris síkbarajzolható gráf egy duális síkgráfok vagy multigráfok mediális gráfja.^[5] A csomódiagramok és láncdiagramok szintén 4-reguláris, síkba rajzolható multigráfok, melyek csúcsai a diagram metszéspontjainak felelnek meg és további információt tartalmaznak azzal kapcsolatban, hogy a csomó két ága közül melyik metszi a másik ágat az adott ponton.^[6]

Tulajdonságok

Mivel egy 4-reguláris gráf minden csúcsának fokszáma páros, ezért minden összefüggő 4-reguláris gráfnak van Euler-köre. Minden páros gráfhoz tartozik teljes párosítás; a 4-reguláris páros gráfok esetében ennek megkeresése sokkal egyszerűbb és gyorsabb algoritmussal történhet: egy Euler-séta minden második élét kiválasztva megkapjuk a gráf 2-faktorát, ami ebben az esetben páros hosszúságú körök olyan gyűjteménye, melyre igaz, hogy a gráf minden csúcsa pontosan egy körben szerepel. Ezen körökön belül újra minden második élt kiválasztva lineáris időben megkapható a teljes párosítás. Ugyanez a módszer használható a gráf négy színnel történő élszínezésének lineáris idejű előállítására.^[7]

A 4-reguláris gráfok páros számú Hamilton-körökre felbontással rendelkeznek.^[8]

Megoldatlan problémák

Nyitott kérdés, hogy vajon az összes 4-reguláris Hamilton-körű gráfnak páros számú Hamilton-kör van-e, vagy egyáltalán egynél több Hamilton-köre van-e. A válasz 4-reguláris multigráfok esetében nemleges.^[9]

Kapcsolódó szócikkek

A Wikimédia Commons tartalmaz 4-reguláris gráf témájú médiaállományokat.

3-reguláris gráf

Fordítás

Ez a szócikk részben vagy egészben a Quartic graph című angol Wikipédia-szócikk ezen változatának fordításán alapul. Az eredeti cikk szerkesztőit annak laptörténete sorolja fel. Ez a jelzés csupán a megfogalmazás eredetét és a szerzői jogokat jelzi, nem szolgál a cikkben szereplő információk forrásmegjelöléseként.

Jegyzetek

↑ Toida, S. (1974), "Construction of quartic graphs", Journal of Combinatorial Theory, Series B 16: 124–133, DOI 10.1016/0095-8956(74)90054-9.
↑ Chvátal, V. (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.
↑ Folkman, Jon (1967), "Regular line-symmetric graphs", Journal of Combinatorial Theory 3: 215–232, DOI 10.1016/s0021-9800(67)80069-3.
↑ Meredith, G. 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.
↑ Bondy, J. A. & Häggkvist, R. (1981), "Edge-disjoint Hamilton cycles in 4-regular planar graphs", Aequationes Mathematicae 22 (1): 42–45, DOI 10.1007/BF02190157.
↑ Welsh, Dominic J. A. (1993), "The complexity of knots", Quo vadis, graph theory?, vol. 55, Annals of Discrete Mathematics, Amsterdam: North-Holland, pp. 159–171, DOI 10.1016/S0167-5060(08)70385-6.
↑ 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.
↑ Thomason, A. G. (1978), "Hamiltonian cycles and uniquely edge colourable graphs", Annals of Discrete Mathematics 3: 259–268, DOI 10.1016/s0167-5060(08)70511-9.
↑ 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.

További információk

Weisstein, Eric W.: Quartic Graph (angol nyelven). Wolfram MathWorld

[1] Toida, S. (1974), "Construction of quartic graphs", Journal of Combinatorial Theory, Series B 16: 124–133, DOI 10.1016/0095-8956(74)90054-9.

[2] Chvátal, V. (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.

[3] Folkman, Jon (1967), "Regular line-symmetric graphs", Journal of Combinatorial Theory 3: 215–232, DOI 10.1016/s0021-9800(67)80069-3.

[4] Meredith, G. 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.

[5] Bondy, J. A. & Häggkvist, R. (1981), "Edge-disjoint Hamilton cycles in 4-regular planar graphs", Aequationes Mathematicae 22 (1): 42–45, DOI 10.1007/BF02190157.

[6] Welsh, Dominic J. A. (1993), "The complexity of knots", Quo vadis, graph theory?, vol. 55, Annals of Discrete Mathematics, Amsterdam: North-Holland, pp. 159–171, DOI 10.1016/S0167-5060(08)70385-6.

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

[8] Thomason, A. G. (1978), "Hamiltonian cycles and uniquely edge colourable graphs", Annals of Discrete Mathematics 3: 259–268, DOI 10.1016/s0167-5060(08)70511-9.

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

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]