Brinkmannův graf - Brinkmann graph

Brinkmannův graf
Brinkmannův graf LS.svg
Brinkmannův graf
Pojmenoval podleGunnar Brinkmann
Vrcholy21
Hrany42
Poloměr3
Průměr3
Obvod5
Automorfismy14 (D7 )
Chromatické číslo4
Chromatický index5
Tloušťka knihy3
Číslo fronty2
VlastnostiEulerian
Hamiltonian
Tabulka grafů a parametrů

V matematický pole teorie grafů, Brinkmannův graf je 4-běžný graf s 21 vrcholy a 42 hranami objevenými Gunnarem Brinkmannem v roce 1992.[1][2] Poprvé byl publikován Brinkmannem a Meringerem v roce 1997.[3]

Má to chromatické číslo 4, chromatický index 5, poloměr 3, průměr 3 a obvod 5. Je to také 3graf spojený s vrcholem a 3-hranový graf. Je to nejmenší 4 pravidelný graf obvodu 5 s chromatickým číslem 4.[3] Má to tloušťka knihy 3 a číslo fronty 2.[4]

Podle Brooksova věta, každý k-pravidelný graf (kromě lichých cyklů a klik) má maximálně chromatické číslo k. Od roku 1959 bylo také známo, že pro každého k a l existují k-chromatické grafy s obvodem l.[5] V souvislosti s těmito dvěma výsledky a několika příklady včetně Chvátalův graf Branko Grünbaum v roce 1970 předpokládal, že pro každého k a l existují k-chromatický k-pravidelné grafy s obvodem l.[6] Chvátalův graf případ vyřeší k = l = 4 této domněnky a případ vyřeší Brinkmannův graf k =  4, l = 5. Grünbaumova domněnka byla vyvrácena pro dostatečně velkou k Johannsen, který ukázal, že chromatické číslo a graf bez trojúhelníků je O (Δ / log Δ), kde Δ je maximální stupeň vrcholu a zavádí se O velká O notace.[7] Navzdory tomuto vyvrácení však zůstává zajímavé najít příklady a je jich známo jen velmi málo.

The chromatický polynom Brinkmannova grafu je X21 - 42X20 + 861X19 - 11480X18 + 111881X17 - 848708X16 + 5207711X15 - 26500254X14 + 113675219X13 - 415278052X12 + 1299042255X11 - 3483798283X10 + 7987607279X9 - 15547364853X8 + 25384350310X7 - 34133692383X6 + 36783818141X5 - 30480167403X4 + 18168142566X3 - 6896700738X2 + 1242405972X (sekvence A159192 v OEIS ).

Algebraické vlastnosti

Brinkmannův graf není a vrchol-tranzitivní graf a jeho úplná skupina automorfismu je izomorfní s dihedrální skupina řádu 14, skupina symetrií a sedmiúhelník, včetně rotací i odrazů.

The charakteristický polynom Brinkmannova grafu je .

Galerie

Reference

  1. ^ Weisstein, Eric W. "Brinkmannův graf". MathWorld.
  2. ^ Brinkmann, G. „Generování kubických grafů rychlejší než kontrola izomorfismu.“ Předtisk 92-047 SFB 343. Bielefeld, Německo: University of Bielefeld, 1992.
  3. ^ A b Brinkmann, G. a Meringer, M. „Nejmenší 4-pravidelné 4-chromatické grafy s obvodem 5.“ Poznámky k teorii grafů New Yorku 32, 40-41, 1997.
  4. ^ Jessica Wolz, Inženýrské lineární rozložení se SAT. Diplomová práce, University of Tübingen, 2018
  5. ^ Erdős, Paul (1959), „Teorie grafů a pravděpodobnost“, Kanadský žurnál matematiky, 11 (0): 34–38, doi:10.4153 / CJM-1959-003-9.
  6. ^ Grünbaum, B. (1970), "Problém v barvení grafů", Americký matematický měsíčník, Mathematical Association of America, 77 (10): 1088–1092, doi:10.2307/2316101, JSTOR  2316101.
  7. ^ Reed, B. A. (1998), „ω, Δ a χ“, Journal of Graph Theory, 27 (4): 177–212, doi:10.1002 / (SICI) 1097-0118 (199804) 27: 4 <177 :: AID-JGT1> 3.0.CO; 2-K.