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
Sugár	$\left\{{\begin{array}{ll}1&m=1\vee n=1\\2&{\text{különben}}\end{array}}\right.$
Átmérő	$\left\{{\begin{array}{ll}1&m=n=1\\2&{\text{különben}}\end{array}}\right.$
Derékbőség	$\left\{{\begin{array}{ll}\infty &m=1\vee n=1\\4&{\text{különben}}\end{array}}\right.$
Kromatikus szám	2
Élkromatikus szám	max{m, n}
Automorfizmusok	$\left\{{\begin{array}{ll}2m!n!&n=m\\m!n!&{\text{különben}}\end{array}}\right.$
Jelölés	$K_{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. A teljes k-részes gráf speciális esete, ahol k=2.

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 teljes páros 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$ élt 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ő
• élgráfjai bástyagráfok
• csillagkromatikus száma $\chi _{s}(G)=min(m,n)+1$.

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 csillaggráfról (illetve csillagtopológiáról):

• 
  S₃ = K_1,3
• 
  S₄ = K_1,4
• 
  S₅ = K_1,5
• 
  S₆ = K_1,6

Speciális jelentősége van 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> Archiválva 2010. április 13-i dátummal a Wayback Machine-ben