Távolságreguláris gráf

Gráfcsaládok automorfizmusukkal meghatározva
távolságtranzitív	${\displaystyle {\boldsymbol {\rightarrow }}}$	távolságreguláris	${\displaystyle {\boldsymbol {\leftarrow }}}$	erősen reguláris
${\displaystyle {\boldsymbol {\downarrow }}}$
szimmetrikus	${\displaystyle {\boldsymbol {\leftarrow }}}$	t-tranzitív, t ≥ 2		ferdeszimmetrikus
${\displaystyle {\boldsymbol {\downarrow }}}$
(ha összefüggő) csúcs- és éltranzitív	${\displaystyle {\boldsymbol {\rightarrow }}}$	éltranzitív és reguláris	${\displaystyle {\boldsymbol {\rightarrow }}}$	éltranzitív
${\displaystyle {\boldsymbol {\downarrow }}}$		${\displaystyle {\boldsymbol {\downarrow }}}$		${\displaystyle {\boldsymbol {\downarrow }}}$
csúcstranzitív	${\displaystyle {\boldsymbol {\rightarrow }}}$	reguláris	${\displaystyle {\boldsymbol {\rightarrow }}}$	(ha páros) bireguláris
${\displaystyle {\boldsymbol {\uparrow }}}$
Cayley-gráf	${\displaystyle {\boldsymbol {\leftarrow }}}$	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.

Egy ${\displaystyle d}$ átmérőjű ${\displaystyle G}$ gráf pontosan akkor távolságreguláris, ha minden ${\displaystyle G}$-beli, egymástól ${\displaystyle j}$ távolságra lévő ${\displaystyle u,v}$ csúcspár esetén létezik olyan, egész számokból álló ${\displaystyle \{b_{0},b_{1},\cdots ,b_{d-1};c_{1},\cdots ,c_{d}\}}$ tömb, amire igaz, hogy bármely ${\displaystyle 1\leq j\leq d}$ értékre ${\displaystyle b_{j}}$ megadja ${\displaystyle u}$ azon szomszédainak számát, melyek ${\displaystyle v}$-től ${\displaystyle j+1}$ távolságra vannak, ${\displaystyle c_{j}}$ pedig megadja ${\displaystyle u}$ azon szomszédainak számát, melyek ${\displaystyle v}$-től ${\displaystyle j-1}$ 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.

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.

Legyen ${\displaystyle G}$ egy távolságreguláris gráf, melynek metszési tömbje ${\displaystyle \{b_{0},b_{1},\cdots ,b_{d-1};c_{1},\cdots ,c_{d}\}}$. Minden ${\displaystyle 0\leq j\leq d}$-re jelölje ${\displaystyle G_{j}}$ azt a ${\displaystyle k_{j}}$-reguláris gráfot, melynek szomszédsági mátrixa, ${\displaystyle A_{j}}$ előáll a ${\displaystyle G}$-ben ${\displaystyle j}$ távolságra lévő csúcspárok összekapcsolásával, és jelölje ${\displaystyle a_{j}}$ ${\displaystyle u}$ azon szomszédainak számát, melyek ${\displaystyle v}$-től ${\displaystyle j}$ távolságra vannak, minden olyan ${\displaystyle G}$-beli ${\displaystyle u,v}$ csúcspárra, melyek egymástól ${\displaystyle j}$ távolságra vannak.

• ${\displaystyle {\frac {k_{j+1}}{k_{j}}}={\frac {b_{j}}{c_{j+1}}}}$ minden ${\displaystyle 0\leq j<d}$-re.
• ${\displaystyle b_{0}>b_{1}\geq \cdots \geq b_{d-1}>0}$ és ${\displaystyle 1=c_{1}\leq \cdots \leq c_{d}\leq b_{0}}$.

• ${\displaystyle AA_{j}=c_{j+1}A_{j+1}+a_{j}A_{j}+b_{j-1}A_{j-1}}$ minden ${\displaystyle 0<j<d}$.
• ${\displaystyle G}$ szomszédsági algebrája egy olyan asszociációs séma Bose–Mesner-algebrája, ahol a ${\displaystyle G}$ csúcspárjai távolságuk alapján vannak összerendelve; továbbá, ha ${\displaystyle G}$ összefüggő, ${\displaystyle d+1}$ különböző sajátértékkel rendelkezik.

Létezik olyan, a ${\displaystyle G}$ metszési mátrixának (intersection matrix) nevezett ${\displaystyle B}$ tridiagonális mátrix, hogy bármely ${\displaystyle G}$-beli ${\displaystyle v}$ csúcsra:

${\displaystyle AX=XB}$,

ahol ${\displaystyle X:={\begin{bmatrix}e_{v}\mid Ae_{v}\mid A_{2}e_{v}\mid \cdots \mid \cdots \mid A_{d}e_{v}\end{bmatrix}}}$.

${\displaystyle B}$ karakterisztikus polinomja megegyezik az ${\displaystyle A}$ minimálpolinomjával.

${\displaystyle B:={\begin{pmatrix}a_{0}&b_{0}&0&\cdots &0&0\\c_{1}&a_{1}&b_{1}&\cdots &0&0\\0&c_{2}&a_{2}&\cdots &0&0\\\vdots &\vdots &\vdots &&\vdots &\vdots \\0&0&0&\cdots &a_{d-1}&b_{d-1}\\0&0&0&\cdots &c_{d}&a_{d}\end{pmatrix}}.}$

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.
• ${\displaystyle 2}$ átmérőjű erősen reguláris gráfok.

Bármely ${\displaystyle k}$ for all ${\displaystyle k\geq 3}$ értékre csak véges számú összefüggő, ${\displaystyle k}$ fokszámú távolságreguláris gráf létezik.^[1]

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 K₄ (avagy tetraéder), a K_3,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.

• 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.

• 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