Teljes páros gráf

A Wikipédiából, a szabad enciklopédiából
Teljes páros gráf
K3,2
K3,2

Névadó Kazimierz Kuratowski
Csúcsok száma n + m
Élek száma mn
Sugár
Átmérő
Derékbőség
Kromatikus szám 2
Élkromatikus szám max{m, n}
Automorfizmusok
Jelölés

A teljes páros gráf olyan páros gráf, ahol mindkét partíció minden csúcsára fennáll, hogy vezet belőle él a másik partíció minden csúcsába.

Definíció[szerkesztés]

Teljes páros gráfnak nevezünk valamely páros gráfot, ha bármely és csúcspárra létezik él.

szimbólummal jelöljük azt a teljes páros gráfot, ahol és . A jelölés Kazimierz Kuratowski lengyel matematikus nevét őrzi.

Tulajdonságok[szerkesztés]

  • a gráf csúcsot és élt tartalmaz
  • a Kuratowski-tétel szerint síkbarajzolható gráf nem tartalmazhat a gráffal topologikusan izomorf részgráfot.
  • a definíció következményeként
  • a gráf összefüggő
  • élgráfjai bástyagráfok

Speciális esetek[szerkesztés]

Egy Km,n teljes páros gráf akkor és csak akkor körmentes, ha m=1 vagy n=1. Ilyen esetben lehet beszélni csillaggráfról (illetve csillagtopológiáról):

Speciális jelentősége van még a gráfok síkbarajzolhatóságában a K3,3 gráf (három ház–három kút-gráf):

Ha m=n, akkor a gráf csúcstranzitív.

Lásd még[szerkesztés]

Irodalom[szerkesztés]

Diestel, Reinhard (2005), Graph Theory (3rd ed.), Springer, p. 17, ISBN 3-540-26182-6, <http://diestel-graph-theory.com/index.html>.

Bondy, John Adrian & Murty, U. S. R. (1976), Graph Theory with Applications, North-Holland, p. 5, ISBN 0-444-19451-7, <http://www.ecp6.jussieu.fr/pageperso/bondy/books/gtwa/gtwa.html>