![cover image](https://wikiwandv2-19431.kxcdn.com/_next/image?url=https://upload.wikimedia.org/wikipedia/commons/thumb/4/49/Star_network_7.svg/langhu-640px-Star_network_7.svg.png&w=640&q=50)
Csillaggráf
olyan fa, melynek egyetlen közbülső csúcsa van, a többi levél / From Wikipedia, the free encyclopedia
A matematika, azon belül a gráfelmélet területén egy Sk csillaggráf vagy röviden csillag (star) megegyezik a K1,k teljes páros gráffal: olyan fa, melynek egyetlen közbülső csúcsa és k levele van (kivétel a k ≤ 1 eset, amikor nincs közbülső csúcs, de van k + 1 levél). Más szerzők definíciója szerint az Sk csillag a k rendű fa, melynek maximális átmérője 2; ebben az esetben a k > 2 csillag k − 1 levéllel rendelkezik.
Csillag | |
![]() | |
Az S7 csillag. (Egyes szerzők sorszámozása szerint az S8.) | |
Csúcsok száma | k+1 |
Élek száma | k |
Átmérő | min (2, k) |
Derékbőség | ∞ |
Kromatikus szám | min (2, k + 1) |
Élkromatikus szám | k |
Egyéb | Éltranzitív Fa Egységtávolság- Gyufa- Páros |
Jelölés | Sk |
A három élű csillagot nevezik karomnak is.
Az Sk csillag elegánsan élcímkézhető, ha k páros, és nem az, ha k páratlan. Éltranzitív gyufagráf, átmérője 2 (ha k > 1), Girthparamétere ∞ (nem tartalmaz kört), élkromatikus száma k, kromatikus száma 2 (ha k > 0). A csillagnak egy nagy automorfizmus-csoportja van, a k betű felett értelmezett szimmetrikus csoport.
A csillagok úgy is leírhatók, mint azok az összefüggő gráfok, melyben legfeljebb egy csúcs foka nagyobb 1-nél.