Távolságreguláris gráf
Gráfcsaládok automorfizmusukkal meghatározva | ||||
távolságtranzitív | távolságreguláris | erősen reguláris | ||
szimmetrikus | t-tranzitív, t ≥ 2 | ferdeszimmetrikus | ||
(ha összefüggő) csúcs- és éltranzitív | éltranzitív és reguláris | éltranzitív | ||
csúcstranzitív | reguláris | (ha páros) bireguláris | ||
Cayley-gráf | zérószimmetrikus | aszimmetrikus |
A matematika, azon belül a gráfelmélet területén egy távolságreguláris gráf (distance-regular graph) olyan reguláris gráf, melyben bármely két v és w csúcsot kiválasztva, a v-től j távolságra és a w-től k távolságra lévő csúcsok száma kizárólag j, k, illetve i = d(v, w), azaz a két csúcs távolságának a függvénye.
Minden távolságtranzitív gráf távolságreguláris. És valóban, a távolságreguláris gráfokat a távolságtranzitív gráfok kombinatorikai általánosításaiként vezették be; számszerűen ugyanazok a regularitási paramétereik, de a távolságreguláris gráfok nem feltétlenül rendelkeznek nagy automorfizmus-csoporttal.
Metszési tömbök
Egy átmérőjű gráf pontosan akkor távolságreguláris, ha minden -beli, egymástól távolságra lévő csúcspár esetén létezik olyan, egész számokból álló tömb, amire igaz, hogy bármely értékre megadja azon szomszédainak számát, melyek -től távolságra vannak, pedig megadja azon szomszédainak számát, melyek -től távolságra vannak. A távolságreguláris gráfot jellemző, egész számokból álló tömböt a gráf metszési tömbjének (intersection array) nevezik.
Kospektrális távolságreguláris gráfok
Két összefüggő távolságreguláris gráf pontosan akkor kospektrális, ha metszési tömbjeik megegyeznek.
Egy távolságreguláris gráf pontosan akkor nem összefüggő, ha kospektrális távolságreguláris gráfok diszjunkt uniójából áll.
Tulajdonságok
Legyen egy távolságreguláris gráf, melynek metszési tömbje . Minden -re jelölje azt a -reguláris gráfot, melynek szomszédsági mátrixa, előáll a -ben távolságra lévő csúcspárok összekapcsolásával, és jelölje azon szomszédainak számát, melyek -től távolságra vannak, minden olyan -beli csúcspárra, melyek egymástól távolságra vannak.
Gráfelméleti tulajdonságok
- minden -re.
- és .
Algebrai tulajdonságok
- minden .
- szomszédsági algebrája egy olyan asszociációs séma Bose–Mesner-algebrája, ahol a csúcspárjai távolságuk alapján vannak összerendelve; továbbá, ha összefüggő, különböző sajátértékkel rendelkezik.
Metszési mátrixok
Létezik olyan, a metszési mátrixának (intersection matrix) nevezett tridiagonális mátrix, hogy bármely -beli csúcsra:
,
ahol .
karakterisztikus polinomja megegyezik az minimálpolinomjával.
Példák
Néhány távolságreguláris gráf, illetve gráfcsalád:
- Teljes gráfok.
- Körgráfok.
- Páratlan gráfok.
- Moore-gráfok.
- A Wells-gráf és a Sylvester-gráf.
- átmérőjű erősen reguláris gráfok.
A távolságreguláris gráfok osztályozása
Bármely for all értékre csak véges számú összefüggő, fokszámú távolságreguláris gráf létezik.[1]
3-reguláris távolságreguláris gráfok
A 3-reguláris távolságreguláris gráfok osztályozása már teljes.
A 13 különböző gráf a következő: a K4 (avagy tetraéder), a K3,3, a Petersen-gráf, a kocka, a Heawood-gráf, a Papposz-gráf, a Coxeter-gráf, a Tutte–Coxeter-gráf, a dodekaéder, a Desargues-gráf, a Tutte 12-cage, a Biggs–Smith-gráf és a Foster-gráf.
Fordítás
- Ez a szócikk részben vagy egészben a Distance-regular graph című angol Wikipédia-szócikk ezen változatának fordításán alapul. Az eredeti cikk szerkesztőit annak laptörténete sorolja fel. Ez a jelzés csupán a megfogalmazás eredetét és a szerzői jogokat jelzi, nem szolgál a cikkben szereplő információk forrásmegjelöléseként.
Jegyzetek
További információk
- Godsil, C. D.. Algebraic combinatorics, Chapman and Hall Mathematics Series. New York: Chapman and Hall, xvi+362. o. (1993). ISBN 0-412-04131-6
- Distance-regular graphs – a survey from 2016
Matematikaportál • összefoglaló, színes tartalomajánló lap