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 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 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 csillagkromatikus száma .
Speciális esetek 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 Páros gráf Teljes gráf
Jegyzetek
Irodalom .
Kategória:Gráfelmélet Kategória:Parametrikus gráfcsaládok