Girthparaméter

A Wikipédiából, a szabad enciklopédiából

A gráfelméletben egy gráf girthparamétere k, ha a gráfban található legrövidebb kör k hosszú. Ha a gráf nem tartalmaz kört (erdő), akkor a girthparamétere végtelen. A „girth” szakszónak nincs bejáratott magyar fordítása, néha a kissé komolytalan, bár szellemes „derékbőség” kifejezést is 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[szerkesztés | forrásszöveg szerkesztése]

  • Egy n hosszú kör girthparamétere n.
  • Egy négyzetrács-gráf girthparamétere 4.
  • Minden G gráf girthparamétere 3, ha klikkszáma legalább 3.
  • Speciálisan K_n girthparamétere 3, ha n \geq 3.
  • A Petersen-gráf girthparamétere 5.

A girthparaméter és a kromatikus szám kapcsolata[szerkesztés | forrásszöveg szerkesztése]

Ha egy gráf girthparamétere nagyobb, mint 3, akkor a gráf háromszögmentes. A Mycielski-konstrukció segítségével tetszőlegesen nagy kromatikus számú gráfokat konstruálhatunk úgy, hogy a girthparaméterük nagyobb marad, mint 3, mivel ha eredetileg egy háromszögmentes gráfból indulunk ki, akkor a Mycielski-konstrukció utáni gráfunk is háromszögmentes lesz, de a kromatikus száma eggyel megnő.

Az általánosabb állítást, miszerint tetszőleges a és b-re létezik a girthparaméterű é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.

Források[szerkesztés | forrásszöveg szerkesztése]

Angol Wikipédia Girth

Wolfram Mathworld Girth