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.https://projecteuclid.org/euclid.pjm/1103035734, R. C. Bose, Strongly regular graphs, partial geometries and partially balanced designs, Pacific J. Math 13 (1963) 389–419. (p. 122)

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),Godsil, Chris; Royle, Gordon. Algebraic Graph Theory. Springer-Verlag New York, 2001, p. 218. 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: , 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 é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 é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 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 . 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,

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,

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ó) , aminek multiplicitása , aminek multiplicitása 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 konferenciagráfoknak nevezzük, a konferenciamátrixokkal való kapcsolatuk miatt. Paramétereik a következőre egyszerűsíthetők:

Az olyan erősen reguláris gráfok, melyekre , sajátértékei egész számok, és multiplicitásaik nem egyenlőek.

Példák

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 M22 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(n2, 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

Jegyzetek

Irodalom A.E. Brouwer, A.M. Cohen, and A. Neumaier (1989), Distance Regular Graphs. Berlin, New York: Springer-Verlag. , Chris Godsil and Gordon Royle (2004), Algebraic Graph Theory. New York: Springer-Verlag.

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)

Kategória:Gráfcsaládok Kategória:Algebrai gráfelmélet Kategória:Reguláris gráfok