Kubični graf

Kúbični gráf je v teoriji grafov graf v katerem imajo vse točke stopnjo enako 3 in je tako 3-regularni graf. Kubični graf se imenuje tudi trívaléntni graf.

Petersenov graf je kubični graf

Polni dvodelni graf $K_{3,3}$ (graf napeljav) je zgled bikubičnega grafa

Bíkúbični gráf je kubični dvodelni graf.

Simetrija

Leta 1932 je Ronald Martin Foster začel zbirati primere kubičnih simetričnih grafov in sestavil Fosterjev popis. Veliko znanih posameznih grafov je kubičnih in simetričnih. Med njimi so najbolj znani: graf napeljav, Petersenov, Heawoodov, Möbius-Kantorjev, Paposov, Desarguesov, Naurujski, Coxetrov, Tutte-Coxetrov, Dyckov, Fosterjev in Biggs-Smithov. William Thomas Tutte je klasificiral simetrične kubične grafe glede na najmanjše takšno celo število s, da se lahko vsaki usmerjeni povezavi z dolžino s preslikajo druga v drugo s točno eno simetrijo grafa. Pokazal je, da je s lahko največ 5 in podal primere grafov za vsako možno vrednost s od 1 do 5.

Med polsimetrične kubične grafe spadajo: Grayjev (najmanjši polsimetrični kubični graf), Jofinove in Ivanova, Ljubljanski in Tuttejeva 12-kletka.

Fruchtov graf je eden od dveh najmanjših kubičnih grafov brez simetrije - ima le en avtomorfizem, enotski avtomorfizem.

Barvanje in neodvisne množice

Po Brooksovem izreku se lahko vsak kubični graf razen polni graf $K_{4}\,$ pobarva z največ tremi barvami. Tako ima vsak kubični graf razen $K_{4}\,$ neodvisno množico vsaj $n/3\,$ točk, kjer je $n\,$ število točk v grafu: največji barvni razred v 3-barvanju ima vsaj toliko točk.

Po Vizingovem izreku se za barvanje povezav potrebuje tri ali štiri barve. 3-točkovno-barvanje je znano kot Taitovo barvanje in tvori particijo točk grafa v tri popolna parjenja. Po Kőnigovem izreku o barvanju povezav ima vsak bikubični graf Taitovo barvanje.

Kubični grafi brez mostov, ki nimajo Taitovega barvanja, so znani kot snarki. Najbolj znani snarki so: Petersenov graf, Tietzejev graf, Blanuševa snarka, cvetlični snark, snark dvojna zvezda, Szekeresov snark in Watkinsov snark. Obstaja neskončno mnogo različnih snarkov.

Glej tudi

• arhimedski graf
• kvartični graf
• kvintični graf

Viri

• Foster, Ronald Martin (1932), »Geometrical Circuits of Electrical Networks«, Transactions of the American Institute of Electrical Engineers, 51 (2): 309–317, doi:10.1109/T-AIEE.1932.5056068
• Isaacs, Rufus Philip (1975), »Infinite families of nontrivial trivalent graphs which are not Tait colorable«, American Mathematical Monthly, 82 (3): 221–239, doi:10.2307/2319844, JSTOR 2319844
• Tutte, William Thomas (1959), »On the symmetry of cubic graphs«, Canad. J. Math, 11: 621–624, doi:10.4153/CJM-1959-057-2

Zunanje povezave

• Weisstein, Eric Wolfgang. »Cubic Graph«. MathWorld.
• Weisstein, Eric Wolfgang. »Bicubic Graph«. MathWorld.