Erősen szabályos grafikon

A gráfelméletben , amely a matematika területe, az erősen szabályos gráf egyfajta szabályos gráf .

Meghatározás

Legyen G = ( V , E ) szabályos gráf, amelynek v csúcsa és k fokja van . Azt mondjuk, hogy a G jelentése erősen reguláris , ha van két egész szám: X- és ji, hogy

• Minden szomszédos csúcspárnak pontosan λ közös szomszédja van.

• Bármely nem szomszédos csúcspárnak pontosan μ közös szomszédja van.

Az ilyen tulajdonságokkal rendelkező gráfot erősen szabályos típusú ( v, k , λ, μ) gráfnak nevezzük .

Ha μ nem nulla, akkor egy ilyen gráf különösen távolság-szabályos gráf .

Tulajdonságok

Az automorfizmusuk által meghatározott grafikoncsaládok
távolság-transzitív	→	szabályos távú	←	erősen szabályos
↓
szimmetrikus (ívtranszitív)	←	t -transzitív, ( t  ≥ 2)		szimmetrikus bal  (be)
↓
(ha csatlakozik) csúcs-transzitív és éltranszitív	→	szabályos és éltranszitív	→	éltranszitív
↓		↓		↓
top-transzitív	→	szabályos	→	(ha kétoldalas) biregularis
↑
Cayley grafikon	←	nulla-szimmetrikus		aszimmetrikus

• A négy paraméter ( v , k , λ, μ) mindig kielégíti a következő összefüggést:

(v-k-1)μ=k(k-λ-1){\ displaystyle (vk-1) \ mu = k (k- \ lambda -1)}

• Egy erősen szabályos ( v , k , λ, μ) típusú grafikonnak pontosan három különértéke van:
  • k{\ displaystyle k} sokasággal 1
  • 12[(λ-μ)+(λ-μ)2+4(k-μ)]{\ displaystyle {\ frac {1} {2}} \ left [(\ lambda - \ mu) + {\ sqrt {(\ lambda - \ mu) ^ {2} +4 (k- \ mu)}} \ jobb]} sokasággal 12[(v-1)-2k+(v-1)(λ-μ)(λ-μ)2+4(k-μ)]{\ displaystyle {\ frac {1} {2}} \ left [(v-1) - {\ frac {2k + (v-1) (\ lambda - \ mu)} {\ sqrt {(\ lambda - \ mu) ^ {2} +4 (k- \ mu)}}} \ jobbra]}
  • 12[(λ-μ)-(λ-μ)2+4(k-μ)]{\ displaystyle {\ frac {1} {2}} \ left [(\ lambda - \ mu) - {\ sqrt {(\ lambda - \ mu) ^ {2} +4 (k- \ mu)}} \ jobb]} sokasággal 12[(v-1)+2k+(v-1)(λ-μ)(λ-μ)2+4(k-μ)]{\ displaystyle {\ frac {1} {2}} \ left [(v-1) + {\ frac {2k + (v-1) (\ lambda - \ mu)} {\ sqrt {(\ lambda - \ mu) ^ {2} +4 (k- \ mu)}}} \ jobbra]}

• Erősen szabályos grafikonokat, amelyeknek a paraméterei megegyeznek , konferencia-grafikonoknak nevezzük, mivel összefüggésbe kerülnek a konferencia-mátrixokkal . A típusuk az .2k+(v-1)(λ-μ)=0{\ displaystyle 2k + (v-1) (\ lambda - \ mu) = 0}(v,v-12,v-5.4,v-14){\ displaystyle \ left (v, {\ frac {v-1} {2}}, {\ frac {v-5} {4}}, {\ frac {v-1} {4}} \ right)}

• A komplementer grafikon egy erősen reguláris gráf típusú ( v, k , λ, μ) szintén erősen reguláris, típusú ( v, v - k -1, V -2-2 K + μ, v -2 K + λ ).

Példák

• A Shrikhande típusú (16,6,2,2) típusú grafikon .
• Az 5 hosszúságú ciklus (5,2,0,1).
• A Petersen típusú (10,3,0,1) grafikon .
• A Chang-gráf típusa (28,12,6,4).
• A Hoffman-Singleton típusú gráf (50,7,0,1).
• A Higman-Sims típusú (100,22,0,6) grafikon .
• A q rendű Paley gráf, amelynek típusa ( q , ( q  - 1) / 2, ( q  - 5) / 4, ( q  - 1) / 4.
• A Brouwer-Haemers típusú (81,20,1,6) típusú grafikon .
• A Schläfli típusú grafikon (27,16,10,8).
• A McLaughlin helyi gráf típusa (162,56,10,24).

Megjegyzések és hivatkozások

1. (in) Eric W. Weisstein , "  határozottan Regular grafikonok  " on mathworld

<img src="https://fr.wikipedia.org/wiki/Special:CentralAutoLogin/start?type=1x1" alt="" title="" width="1" height="1" style="border: none; position: absolute;">