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

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

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

Gráfelméleti tulajdonságok

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

Algebrai tulajdonságok

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

Metszési mátrixok

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

$AX=XB$,

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

$B$ karakterisztikus polinomja megegyezik az $A$ minimálpolinomjával.

$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}}.$

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

A távolságreguláris gráfok osztályozása

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

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

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.

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