Másodfokú gráf
A másodfokú gráf egy olyan gráf , amelyben minden csúcs 4 -es fokozatú . Más szóval, a másodfokú gráf egy 4 szabályos gráf [1] .
Példák
Néhány jól ismert gráf másodfokú. Ezek olyan grafikonok, mint:
- K 5 teljes gráf , 5 csúcsú másodfokú gráf, a lehető legkisebb másodfokú gráf;
- A Chwatala gráf , egy másik 12 csúcsú másodfokú gráf, a legkisebb olyan másodfokú gráf, amelynek nincsenek háromszögei, és nem lehet háromszínűvé tenni [2] ;
- Folkman gráf, 20 csúcsos másodfokú gráf, legkisebb félszimmetrikus gráf [3] ;
- Meredith -gráf, egy 70 csúcsos másodfokú gráf, amely 4-összefüggésben van , de nem rendelkezik Hamilton-ciklussal, megcáfolva Crispin Nash-Williams sejtését [4] .
Bármely medián gráf másodfokú síkgráf , és bármely másodfokú sík gráf kettős sík gráf vagy multigráf pár medián gráfja [5] . A csomódiagramok és a linkdiagramok is másodfokú síkbeli multigráfok , amelyekben a csúcsok a diagram metszéspontjait jelentik, és további információkkal vannak ellátva, amelyek jelzik, hogy a csomópont melyik két ága metszi a másik ágat az adott pontban [6] .
Tulajdonságok
Mivel a másodfokú gráf bármely csúcsának foka páros, minden összekapcsolt másodfokú gráfnak van Euler-ciklusa . A hagyományos kétrészes gráfokhoz hasonlóan minden kétrészes négyzetes gráf tökéletes illeszkedést tartalmaz . Ebben az esetben sokkal egyszerűbb és gyorsabb illesztési algoritmus lehetséges, mint a szabálytalan gráfok esetében - ha az Euler-ciklus bármely másik élét választjuk, akkor egy 2-tényezőt kaphatunk , amely ebben az esetben ciklusok gyűjteménye, mindegyik amelyeknek páros hosszúságúak, és a gráf minden csúcsa pontosan egy ciklusban jelenik meg. Ha ezekben a ciklusokban bármely más élt választunk, akkor tökéletes illeszkedést kapunk lineáris időben . Ugyanez a módszer használható egy gráf élének négy színnel való színezésére lineáris időben [7] .
A másodfokú gráfoknak páros számú Hamilton kiterjesztése van [8] .
Nyitott kérdések
Nyitott probléma az a sejtés, hogy minden másodfokú Hamilton-gráfnak van-e páros számú Hamilton-ciklusa , vagy egynél több Hamilton-ciklusa van. Ismeretes, hogy másodfokú multigráfokra a válasz NEM [9] .
Lásd még
Jegyzetek
- ↑ Toida, 1974 , p. 124–133.
- ↑ Chvatal, 1970 , p. 93–94.
- ↑ Folkman, 1967 , p. 215–232.
- ↑ Meredith, 1973 , p. 55–60.
- ↑ Bondy, Häggkvist, 1981 , p. 42–45.
- ↑ walesi, 1993 , p. 159–171.
- ↑ Gabow, 1976 , p. 345–355.
- ↑ Thomason, 1978 , p. 259–268.
- ↑ Fleischner 1994 , p. 449–459.
Irodalom
- Toida S. Kvartikus gráfok felépítése // Journal of Combinatorial Theory . - 1974. - T. 16 . – S. 124–133 . - doi : 10.1016/0095-8956(74)90054-9 .
- Chvátal V. A legkisebb háromszög nélküli 4-kromatikus 4-reguláris gráf // Journal of Combinatorial Theory . - 1970. - T. 9 , sz. 1 . – S. 93–94 . - doi : 10.1016/S0021-9800(70)80057-6 .
- John Folkman. Szabályos vonalszimmetrikus gráfok // Journal of Combinatorial Theory . - 1967. - T. 3 . – S. 215–232 . - doi : 10.1016/s0021-9800(67)80069-3 .
- Meredith GHJ Szabályos, n - valens, n -kapcsolt, nem Hamilton-féle, n - élen nem színezhető gráfok // Journal of Combinatorial Theory . - 1973. - T. 14 . — S. 55–60 . - doi : 10.1016/s0095-8956(73)80006-1 .
- Bondy JA, Häggkvist R. Él-diszjunkt Hamilton-ciklusok 4-reguláris síkgráfokban // Aequationes Mathematicae . - 1981. - T. 22 , sz. 1 . – S. 42–45 . - doi : 10.1007/BF02190157 .
- Dominic JA Welsh. A csomók összetettsége // Quo vadis, gráfelmélet?. - Amszterdam: Észak-Holland, 1993. - T. 55. - S. 159-171. — (A diszkrét matematika évkönyvei). - doi : 10.1016/S0167-5060(08)70385-6 .
- Harold N. Gabow. Euler-partíciók használata színes bipartit multigráfok élére // International Journal of Computer and Information Sciences. - 1976. - V. 5 , sz. 4 . – S. 345–355 . - doi : 10.1007/bf00998632 .
- Thomason AG Hamiltoni ciklusok és egyedi élű, színes gráfok // Annals of Discrete Mathematics. - 1978. - T. 3 . – S. 259–268 . - doi : 10.1016/s0167-5060(08)70511-9 .
- Herbert Fleischner. Maximálisan domináns ciklusok egyedisége 3-reguláris gráfokban és Hamilton-ciklusok egyedisége 4-reguláris gráfokban // Journal of Graph Theory. - 1994. - T. 18 , sz. 5 . – S. 449–459 . - doi : 10.1002/jgt.3190180503 .
Linkek