Távolságreguláris gráf

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

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\le j\le 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\le j\le 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\le j<d$-re.
• $b_0>b_1\ge \cdots \ge b_{d-1}>0$ és $1=c_1\le \cdots \le c_d\le b_0$.

Algebrai tulajdonságok

• $A{A}_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:=\left[\begin{array}{c}{e}_v\mid A{e}_v\mid A_2{e}_v\mid \cdots \mid \cdots \mid A_d{e}_v\end{array}\right]$.

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

$B:=\left(\begin{array}{cccccc}{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\\ ⋮& ⋮& ⋮& & ⋮& ⋮\\ 0& 0& 0& \cdots & a_{d-1}& b_{d-1}\\ 0& 0& 0& \cdots & c_d& a_d\end{array}\right).$

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\ge 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

• Sablon:Fordítás

További információk

• Sablon:Cite book
• Distance-regular graphs – a survey from 2016