Býčí hlava (teorie grafů)

Býčí hlava
Vrcholy 5
žebra 5
Poloměr 2
Průměr 3
obvod 3
Automorfismy 2 ( Z / 2 Z )
Chromatické číslo 3
Chromatický index 3
Vlastnosti Rovinný
graf jednotkový graf
vzdálenosti

Býčí hlava je rovinný neorientovaný graf s 5 vrcholy a 5 hranami ve tvaru trojúhelníku se dvěma nesouvislými převislými hranami [1] .

Barevné číslo grafu je 3, chromatický index je 3, poloměr je 2, průměr je 3 a obvod je 3. Graf je blokový , dělený , bezdrápý , vertex -1-connected a 1- edge -připojeno .

Počítání bez býčích hlav

Graf je bez býčích hlav, pokud hlava není obsažena jako vygenerovaný podgraf . Grafy bez trojúhelníků neobsahují býčí hlavy, protože každá hlava obsahuje trojúhelník. Silná domněnka o dokonalých grafech byla prokázána pro grafy bez býčích hlav dávno před důkazem pro grafy obecného tvaru [2] a existuje známý algoritmus pro rozpoznání dokonalých grafů bez býčích hlav s polynomiální dobou běhu [3] .

Maria Chudnovskaya a Samuel Safra studovali bezhlavé grafy v obecnější podobě a ukázali, že každý takový graf musí mít buď velkou kliku , nebo velkou nezávislou množinu (to znamenápro grafy s býčí hlavou platí Erdős-Hajnalova domněnka ) [4 ] a vypracovali obecnou teorii struktury takových grafů [5] [6] [7] .

Chromatické a charakteristické polynomy

Chromatický polynom býčí hlavy je . Další dva grafy jsou chromaticky ekvivalentní býčí hlavě.

Charakteristickým polynomem grafu je .

Tattův polynom grafu je .

Poznámky

  1. ↑ Weisstein, Eric W. Bull Graph  na webu Wolfram MathWorld .
  2. ↑ Chvátal, Sbihi, 1987 , str. 127–139.
  3. ↑ Reed, Sbihi, 1995 , str. 171–178.
  4. ↑ Chudnovsky, Safra, 2008 , str. 1301–1310.
  5. ↑ Chudnovsky, M. (2008), Struktura býčích grafů. I. Tříhranné cesty se středy a anticentry , < http://www.columbia.edu/~mc2775/bulls1.pdf > Archivováno 3. března 2016 ve Wayback Machine . 
  6. ↑ Chudnovsky, M. (2008), Struktura býčích grafů. II. Elementární trigrafy , < http://www.columbia.edu/~mc2775/bulls2.pdf > Archivováno 4. března 2016 ve Wayback Machine . 
  7. ↑ Chudnovsky, M. (2008), Struktura býčích grafů. III. Globální struktura , < http://www.columbia.edu/~mc2775/bulls3.pdf > Archivováno 3. března 2016 ve Wayback Machine . 

Literatura