Erősen reguláris gráf

A matematika, azon belül a gráfelmélet területén egy erősen reguláris gráf (strongly regular graph, srg) olyan reguláris gráf, amely néhány további követelménynek is megfelel. Ha G = (V,E) egy v csúccsal rendelkező k fokszámú reguláris gráf, akkor erősen reguláris, ha létezik olyan λ és μ egész szám, melyekre:

• Bármely két szomszédos csúcsnak λ közös szomszédja van.
• Bármely két nem szomszédos csúcsnak μ közös szomszédja van.

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

Az erősen reguláris gráfokat néha paramétereikkel jelölik: srg(v, k, λ, μ) vagy egyszerűen (v, k, λ, μ), ha a kontextusból egyértelmű, hogy erősen reguláris gráfról van szó. Az erősen reguláris gráfokat Raj Chandra Bose vezette be 1963-ban.

Egyes szerzők kizárják a definíciót triviálisan teljesítő gráfokat, tehát azokat, melyek azonos méretű teljes gráfok diszjunkt uniójaként állnak elő (μ=0), illetve ezek komplementereit, a Turán-gráfokat.

Az srg(v, k, λ, μ) komplementere szintén erősen reguláris. Paraméterei: srg(v, v−k−1, v−2−2k+μ, v−2k+λ).

Minden erősen reguláris gráf 2 átmérőjű távolságreguláris gráf (az elfajult μ=0 esetet nem tekintve).

Tulajdonságok

A paraméterek közötti kapcsolatok

Az srg(v, k, λ, μ) négy paramétere nem független egymástól, és eleget kell tenniük a következő összefüggésnek:

$(v-k-1)\mu =k(k-\lambda -1)$,

melyhez a következő, egyszerű leszámlálási okoskodással lehet eljutni:

• Osszuk szét a gráf csúcsait három szintre a következőképpen: válasszunk ki egy tetszőleges csúcsot gyökérnek, ő lesz a 0. szinten. A gyökércsúcs k szomszédját helyezzük el az 1. szintre, az összes többi csúcs a 2. szinten lesz.
• Az 1. szinten lévő csúcsok közvetlen kapcsolatban vannak a gyökérrel, ezért a gyökérrel λ közös szomszédjuk van, melyeknek szintén az 1. szinten kell lenniük. Mivel a csúcsok fokszáma k, ezért $k-\lambda -1$ él maradt meg minden 1. szintű csúcs számára ahhoz, hogy a 2. szinten lévő csúcsokhoz csatlakozzon. Ezért minden 1. szintű és a 2. szint között $k\times (k-\lambda -1)$ él húzódik.
• A 2. szinten lévő csúcsok nem közvetlenül csatlakoznak a gyökérhez, ezért μ közös szomszédjuk van a gyökérrel, melyeknek mind az 1. szinten kell lenniük. A 2. szinten $(v-k-1)$ csúcs van, és mindegyik μ az 1. szinten lévő csúccsal van összekötve. Ezért az 1. és 2. szint közötti élek száma $(v-k-1)\times \mu$.
• Az 1. és 2. szintet összekötő élekre vonatkozó két kifejezést egyenlővé tesszük.

Szomszédsági mátrix

Jelölje a v rendű egységmátrixot I, a minden elemében 1-eseket tartalmazó mátrixot pedig J. Egy erősen reguláris gráf A szomszédsági mátrixa két egyenlőségnek tesz eleget. Először is,

$AJ=JA=kJ,$

ami a csúcsok fokszámára vonatkozó követelmény triviális újrafogalmazása; mellesleg ez megmutatja, hogy k a szomszédsági mátrix sajátértéke, csak 1-esekből álló sajátvektorral. Másodszor,

${A}^{2}+(\mu -\lambda ){A}+(\mu -k){I}=\mu {J},$

ami az erős regularitási feltételt fejezi ki. Az első tag megadja a bármely csúcstól az összes többi csúcsba vezető két lépéses utak számát, a második tag az egy lépéses utakét, a harmadik tag pedig a nulla lépéses utakét. Az éllel összekötött csúcspárokra az egyenlőség arra egyszerűsödik, hogy az ilyen két lépéses utak száma éppen λ. A nem közvetlenül szomszédos csúcspároknál arra, hogy az ilyen két lépéses utak száma μ. A triviális saját magával párba állított csúcsra pedig arra, hogy a fokszám egyenlő k-val.

Megfordítva, az olyan gráfok, melyek nem teljes vagy nullgráfok, szomszédsági mátrixuk pedig a fenti két feltételt kielégíti, erősen regulárisak.

Sajátértékek

• A gráf szomszédsági mátrixának pontosan három sajátértéke van:
  • k, aminek multiplicitása 1 (ahogy fent látható)
  • ${\frac {1}{2}}\left[(\lambda -\mu )+{\sqrt {(\lambda -\mu )^{2}+4(k-\mu )}}\right]$, aminek multiplicitása ${\frac {1}{2}}\left[(v-1)-{\frac {2k+(v-1)(\lambda -\mu )}{\sqrt {(\lambda -\mu )^{2}+4(k-\mu )}}}\right]$
  • ${\frac {1}{2}}\left[(\lambda -\mu )-{\sqrt {(\lambda -\mu )^{2}+4(k-\mu )}}\right]$, aminek multiplicitása ${\frac {1}{2}}\left[(v-1)+{\frac {2k+(v-1)(\lambda -\mu )}{\sqrt {(\lambda -\mu )^{2}+4(k-\mu )}}}\right]$
• Mivel a multiplicitásoknak egész számoknak kell lenniük, a fenti alakok további megszorításokat adnak v, k, μ és λ értékeire, ez az úgynevezett „Krein-feltétel”.
• Az olyan erősen reguláris gráfokat, melyekre $2k+(v-1)(\lambda -\mu )=0$ konferenciagráfoknak nevezzük, a konferenciamátrixokkal való kapcsolatuk miatt. Paramétereik a következőre egyszerűsíthetők:

${\text{srg}}\left(v,{\tfrac {1}{2}}(v-1),{\tfrac {1}{4}}(v-5),{\tfrac {1}{4}}(v-1)\right).$

• Az olyan erősen reguláris gráfok, melyekre $2k+(v-1)(\lambda -\mu )\neq 0$, sajátértékei egész számok, és multiplicitásaik nem egyenlőek.

Példák

A 13 rendű Paley-gráf, ami az srg(13,6,2,3) paraméterű erősen reguláris gráf.

• Az 5 hosszúságú körgráf paraméterei srg(5, 2, 0, 1).
• A Petersen-gráf paraméterei srg(10, 3, 0, 1).
• A Clebsch-gráf paraméterei srg(16, 5, 0, 2).
• A Shrikhande-gráf paraméterei srg(16, 6, 2, 2), és nem távolságtranzitív gráf.
• A GQ(2, 4) általánosított négyszög élgráfjának paraméterei srg(27, 10, 1, 5). Minden (s, t) rendű általánosított négyszögből ugyanígy előáll egy erősen reguláris gráf.
• A Schläfli-gráf paraméterei srg(27, 16, 10, 8).
• A Chang-gráfok paraméterei srg(28, 12, 6, 4).
• A Hoffman–Singleton-gráf paraméterei srg(50, 7, 0, 1).
• A Gewirtz-gráf paraméterei (56, 10, 0, 2).
• Az M₂₂ gráf paraméterei srg(77, 16, 0, 4).
• A Brouwer–Haemers-gráf paraméterei srg(81, 20, 1, 6).
• A Higman–Sims-gráf paraméterei srg(100, 22, 0, 6).
• A lokális McLaughlin-gráf paraméterei srg(162, 56, 10, 24).
• A Cameron-gráf paraméterei srg(231, 30, 9, 3).
• A q rendű Paley-gráf paraméterei srg(q, (q − 1)/2, (q − 5)/4, (q − 1)/4).
• Az n × n-es négyzetes bástyagráf paraméterei srg(n², 2n − 2, n − 2, 2).
• Az önkomplementer szimmetrikus gráfok erősen regulárisak.

Egy erősen reguláris gráfot primitívnek tekintünk, ha a gráf és komplementere is összefüggő. A fent felsorolt gráfok mind primitívek, egyébként fennállna, hogy μ=0 vagy μ=k.

Moore-gráfok

A λ = 0 paraméterű erősen reguláris gráfok háromszögmentesek. A 3-nál kevesebb csúcsú teljes gráfokon és az összes teljes páros gráfon kívül csak a fenti listában szereplő hét gráf ismert közülük. A λ = 0 és μ = 1 paraméterű erősen reguláris gráfok 5 girthű Moore-gráfok. A fenti listában szereplő három ilyen gráf, (5, 2, 0, 1), (10, 3, 0, 1) és (50, 7, 0, 1) ismert ezek közül. Az egyetlen további lehetséges, Moore-gráfot előállító paraméterhalmaz a (3250, 57, 0, 1); nem ismert, hogy létezik-e ez a gráf, és ha igen, egyedi-e.

Kapcsolódó szócikkek

• Seidel-féle szomszédsági mátrix

Fordítás

• Ez a szócikk részben vagy egészben a Strongly 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.

Irodalom

• A.E. Brouwer, A.M. Cohen, and A. Neumaier (1989), Distance Regular Graphs. Berlin, New York: Springer-Verlag. ISBN 3-540-50619-5, ISBN 0-387-50619-5
• Chris Godsil and Gordon Royle (2004), Algebraic Graph Theory. New York: Springer-Verlag. ISBN 0-387-95241-1

További információk

• Eric W. Weisstein, Mathworld article with numerous examples.
• Gordon Royle, List of larger graphs and families.
• Andries E. Brouwer, Parameters of Strongly Regular Graphs.
• Brendan McKay, Some collections of graphs.
• Ted Spence, Strongly regular graphs on at most 64 vertices.
• Gál Attila Péter: Reguláris és erősen reguláris gráfok (szakdolgozat)