Girth

A gráfelméletben akkor mondjuk, hogy egy gráf girth-e (ejtsd: [ɡɜːθしーた], magyarosan görsz) k, ha a gráfban található legrövidebb kör k hosszú. Ha a gráf nem tartalmaz kört (erdő), akkor a girth-e végtelen.

A „girth” szakszónak nincs bejáratott magyar fordítása, néha a derékbőség vagy bőség kifejezést használják rá.

Tetszőleges k ≥ 2, g ≥ 3 esetén létezik k-reguláris g-girthparaméterű gráf, ezek közül a legkevesebb csúccsal rendelkező gráfokat nevezzük cage-gráfoknak.

Példák

• Egy n hosszú kör girth-e n.
• Egy négyzetrács-gráf girth-e 4.
• Ha egy gráf klikkszáma legalább 3, akkor a gráf girth-e is 3.
• A $K_{n}$ teljes gráf girth-e 3, ha $n\geq 3$.
• A $K_{m,n}$ teljes páros gráf girth-e 4, ha $m\geq 2$ és $n\geq 2$.

• 
  A Petersen-gráf girth-e 5.
• 
  A Heawood-gráf girth-e 6
• 
  A McGee-gráf girth-e 7.
• 
  A Tutte–Coxeter-gráf girth-e 8.

A girthparaméter és a kromatikus szám kapcsolata

Ha egy gráf girth-e nagyobb, mint 3, akkor a gráf háromszögmentes, vagyis a klikkszáma legfeljebb kettő. A klikkszám az egyik legismertebb és legegyszerűbb alsó becslése a kromatikus számnak. A klikkszám és kromatikus szám kapcsolatáról szóló egyik klasszikus eredmény (a Mycielski-konstrukció) szerint konstruálható olyan gráf, aminek a klikkszáma csak kettő, de a kromatikus száma tetszőlegesen nagy. Vagyis a klikkszám bár alsó becslése a kromatikus számnak, önmagában (más gráfparaméterek használata nélkül) nem alkalmas a kromatikus szám felső becslésére. Az általánosabb állítást, miszerint tetszőleges a és b egész számokra létezik a girth-ű és b kromatikus számú gráf, Erdős Pál bizonyította először a valószínűségi módszer segítségével. Így a kromatikus számhoz hasonlóan a girth sem használható önmagában (más gráfparaméterek használata nélkül) a kromatikus szám felső becslésére.

Források

• Weisstein, Eric W.: Girth (angol nyelven). Wolfram MathWorld