Girth paraméter

A gráfelméletben egy gráf girth-paramé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 girth-paramé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-girth-paramé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-paramétere n.
• Egy négyzetrács-gráf girth-paramétere 4.
• Minden G gráf girth-paramétere 3, ha klikkszáma legalább 3.
• Speciálisan $K_n$ girth-paramétere 3, ha $n \geq 3$.
• A Petersen-gráf girth-paramétere 5.

A girth-paraméter és a kromatikus szám kapcsolata

Ha egy gráf girth-paramé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 girth-paramé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 girth-paramé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

Angol Wikipédia Girth

Wolfram Mathworld Girth