Távolságreguláris gráf

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.

Gráfcsaládok automorfizmusukkal meghatározva
távolságtranzitívtávolságreguláriserősen reguláris
szimmetrikust-tranzitív, t ≥ 2ferdeszimmetrikus
(ha összefüggő)
csúcs- és éltranzitív
éltranzitív és reguláriséltranzitív
csúcstranzitívreguláris(ha páros)
bireguláris
Cayley-gráfzérószimmetrikusaszimmetrikus

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ökSzerkesztés

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áfokSzerkesztés

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ágokSzerkesztés

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ágokSzerkesztés

  •   minden  -re.
  •   és  .

Algebrai tulajdonságokSzerkesztés

  •   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átrixokSzerkesztés

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ákSzerkesztés

Néhány távolságreguláris gráf, illetve gráfcsalád:

A távolságreguláris gráfok osztályozásaSzerkesztés

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áfokSzerkesztés

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ásSzerkeszté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 jelzi, nem szolgál a cikkben szereplő információk forrásmegjelöléseként.

JegyzetekSzerkesztés

  1. Bang, S. (2015. január 10.). „There are only finitely many distance-regular graphs of fixed valency greater than two”. Advances in Mathematics 269 (Supplement C), 1–55. o. DOI:10.1016/j.aim.2014.09.025.  

További információkSzerkesztés