Teljes páros gráf

matematikai fogalom a gráfelméletben
Ez a közzétett változat, ellenőrizve: 2022. október 20.

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.

Teljes páros gráf
K3,2
K3,2

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

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
  • csillagkromatikus száma  .[1]

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
  1. Fertin, Guillaume; Raspaud, André & Reed, Bruce (2004), "Star coloring of graphs", Journal of Graph Theory 47 (3): 163–182, DOI 10.1002/jgt.20029