Erősen regulá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 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.

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.^[1]

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),^[2][3] 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).

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:

${\displaystyle (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 ${\displaystyle 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 ${\displaystyle 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 ${\displaystyle (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 ${\displaystyle (v-k-1)\times \mu }$.
• Az 1. és 2. szintet összekötő élekre vonatkozó két kifejezést egyenlővé tesszük.

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,

${\displaystyle 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,

${\displaystyle {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.^[4]

• 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ó)
  • ${\displaystyle {\frac {1}{2}}\left[(\lambda -\mu )+{\sqrt {(\lambda -\mu )^{2}+4(k-\mu )}}\right]}$, aminek multiplicitása ${\displaystyle {\frac {1}{2}}\left[(v-1)-{\frac {2k+(v-1)(\lambda -\mu )}{\sqrt {(\lambda -\mu )^{2}+4(k-\mu )}}}\right]}$
  • ${\displaystyle {\frac {1}{2}}\left[(\lambda -\mu )-{\sqrt {(\lambda -\mu )^{2}+4(k-\mu )}}\right]}$, aminek multiplicitása ${\displaystyle {\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 ${\displaystyle 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:

${\displaystyle {\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 ${\displaystyle 2k+(v-1)(\lambda -\mu )\neq 0}$, sajátértékei egész számok, és multiplicitásaik nem egyenlőek.

• 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).^[5]
• 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.

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.

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

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

• 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

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