Teljes páros gráf

Teljes páros gráf
K3,2
Névadó	Kazimierz Kuratowski
Csúcsok száma	n + m
Élek száma	mn
Átmérő	2
Kromatikus szám	2
Élkromatikus szám	max{m, n}
Automorfizmusok	2m!n! ha m=n, különben m!n!

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ó

Teljes páros gráfnak nevezünk valamely $G:=(V_1 + V_2, E)$ páros gráfot, ha bármely $v_1 \in V_1$ és $v_2 \in V_2$ csúcspárra létezik $\{ v_1, v_2 \} \in E$ él.

$K_{m,n}$ szimbólummal jelöljük azt a páros teljes gráfot, ahol $\left|V_1\right|=m$ és $\left|V_2\right|=n$. A jelölés Kazimierz Kuratowski lengyel matematikus nevét őrzi.

Tulajdonságok

• a $K_{m,n}$ gráf $m + n$ csúcsot és $m \cdot n$ élet tartalmaz
• a Kuratowski-tétel szerint síkbarajzolható gráf nem tartalmazhat a $K_{3,3}$ gráffal topologikusan izomorf részgráfot.
• a definíció következményeként $K_{m,n} = K_{n,m}$
• a $K_{m,n}$ gráf összefüggő

Speciális esetek

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

• 

  S₃ = K_1,3

• 

  S₄ = K_1,4

• 

  S₅ = K_1,5

• 

  S₆ = K_1,6

Speciális jelentéssel bír még a gráfok síkbarajzolhatóságában a K_3,3 gráf (három ház–három kút-gráf):

• 

  K_3,3

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

Lásd még

• Páros gráf
• Teljes gráf

Irodalom

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>