McKay – Miller – Shiráň grafigi - McKay–Miller–Širáň graph

Yilda grafik nazariyasi, McKay-Miller-Shira grafikalari ning cheksiz sinfidir vertikal-o'tuvchi grafikalar bilan diametri ikkitasi va ularning diametriga nisbatan ko'p sonli vertikallar bilan daraja. Ularning nomi berilgan Brendan MakKey, Mirka Miller, va ularni birinchi bo'lib qurgan Yozef Shiráir kuchlanishli grafikalar 1998 yilda.^[1]

Fon

Ushbu grafikalarni qurish uchun kontekst: daraja diametri muammosi yilda grafik nazariyasi, bu har bir daraja va diametr kombinatsiyasi uchun mumkin bo'lgan eng katta grafikani qidiradi. Ikki diametrli grafikalar uchun har bir tepaga o'zboshimchalik bilan boshlanadigan tepadan ikki qadamda erishish mumkin va agar daraja ${ displaystyle d}$ keyin ko'pi bilan ${ displaystyle d}$ tepaliklarga bir qadamda va boshqasida erishish mumkin ${ displaystyle d (d-1)}$ ikki qadamda Mur bog'langan tepaliklarning umumiy soni ko'pi bilan bo'lishi mumkin ${ displaystyle d ^ {2} +1}$. Biroq, ushbu chegaraga erishish uchun faqat to'rtta grafik ma'lum: bitta chekka (bir daraja), 5 vertex tsikl grafigi (ikkinchi daraja), Petersen grafigi (uchinchi daraja) va Hoffman - Singleton grafigi (yettinchi daraja). Ulardan faqat bittasi Mur grafikalari 57 daraja bilan mavjud bo'lishi mumkin. Boshqa barcha darajalar uchun diametrning ikki grafigidagi tepaliklarning maksimal soni kichikroq bo'lishi kerak. McKay-Miller-Shiráň grafikalari qurilgunga qadar yagona taniqli qurilish bir qator tepaliklarga teng bo'ldi

${ displaystyle left lfloor { frac {d + 2} {2}} right rfloor cdot left lceil { frac {d + 2} {2}} right rceil,}$

yordamida Keyli grafigi qurilish.^[2]

Buning o'rniga McKay-Miller-Shira grafikalarida bir qator tepaliklar teng

${ displaystyle { frac {8} {9}} chap (d + { frac {1} {2}} o'ng) ^ {2},}$

ning cheksiz ko'p qiymatlari uchun ${ displaystyle d}$. Darajalar ${ displaystyle d}$ buning uchun ularning qurilish ishlari aynan shu narsadir ${ displaystyle (2d + 1) / 3}$ a asosiy kuch va shunday 1 modulga mos keladigan 4. Ushbu mumkin darajalar raqamlardir

7, 13, 19, 25, 37, 43, 55, 61, 73, 79, 91, ...

Ushbu ketma-ketlikdagi birinchi raqam - 7 - Gofman - Singleton grafigi darajasi, yettinchi darajali Makkay - Miller - Shiras grafigi - Gofman - Sinqlton grafigi.^[2] Xuddi shu qurilish darajalarga ham qo'llanilishi mumkin ${ displaystyle d}$ buning uchun ${ displaystyle (2d + 1) / 3}$ Bu asosiy kuch, lekin 0 yoki -1 mod 4. Bu holda, u baribir uning o'lchamlari, diametri va darajasi uchun bir xil formulalar bilan grafik hosil qiladi, ammo bu grafikalar umuman vertex-tranzitiv emas.^[1][3]

Keyinchalik McKay-Miller-Shira grafikalari, tepaliklari soni yanada kattaroq bo'lgan boshqa grafikalar, ${ displaystyle O (d ^ {3/2})}$ Mur bog'langanidan kamroq, qurilgan.^[4] Biroq, bular McKay-Miller-Shira grafikalariga qaraganda ancha cheklangan darajalar to'plamini qamrab oladi.^[5]

Qurilishlar

MakKay, Miller va Shirasning dastlabki konstruktsiyasida ishlatilgan kuchlanish grafigi ularni a sifatida qurish usuli qoplama grafigi grafikning ${ displaystyle K_ {q, q} ^ {*}}$, qayerda ${ displaystyle q = (2d + 1) / 3}$ bu asosiy kuch va qaerda ${ displaystyle K_ {q, q} ^ {*}}$ dan hosil bo'ladi to'liq ikki tomonlama grafik ${ displaystyle K_ {q, q}}$ biriktirish orqali ${ displaystyle (q-1) / 4}$ har bir tepalikka o'z-o'zidan halqalar. Syagiova (2001) yana voltaj grafigi usulidan foydalanadi, lekin oddiyroq grafikaga qo'llaniladi, a dipol grafigi bilan ${ displaystyle q}$ har bir tepaga bir xil miqdordagi o'z-o'zidan halqalarni biriktirib, xuddi shu tarzda o'zgartirilgan parallel qirralar.^[2]

Shuningdek, McKay-Miller-Shira grafikalarini o'zgartirish orqali o'zgartirish mumkin Levi grafigi ning afin tekisligi ustidan maydon tartib ${ displaystyle q}$.^[3][5]

Qo'shimcha xususiyatlar

The spektr MakKay-Miller-Shiras grafigi ko'pi bilan beshta o'ziga xos qiymatga ega. Ushbu grafiklarning ba'zilarida ushbu qiymatlarning barchasi butun sonlardir, shuning uchun grafik an integral grafik.^[6]

Adabiyotlar