Shrikhand grafigi - Shrikhande graph
| Shrikhand grafigi | |
|---|---|
 Shrikhand grafigi | |
| Nomlangan | S. S. Shrixande |
| Vertices | 16 |
| Qirralar | 48 |
| Radius | 2 |
| Diametri | 2 |
| Atrof | 3 |
| Automorfizmlar | 192 |
| Xromatik raqam | 4 |
| Xromatik indeks | 6 |
| Kitob qalinligi | 4 |
| Navbat raqami | 3 |
| Xususiyatlari | Juda muntazam Hamiltoniyalik Nosimmetrik Evleriya Ajralmas |
| Grafiklar va parametrlar jadvali | |
In matematik maydoni grafik nazariyasi, Shrikhand grafigi a nomlangan grafik tomonidan kashf etilgan S. S. Shrixande 1959 yilda.[1][2] Bu qat'iy muntazam grafik 16 bilan tepaliklar va 48 qirralar, har bir tepalikka ega daraja 6. Tugunlarning har bir jufti ulanganmi yoki yo'qligidan qat'i nazar, boshqa ikkita qo'shnisi umumiy ikkita qo'shniga ega.
Qurilish
Shrikhande grafigini a shaklida tuzish mumkin Keyli grafigi. Tepalik to'plami . Ikkita tepalik qo'shni bo'lib, agar ular farq bo'lsa .
Xususiyatlari
Shrikhande grafasida istalgan ikkita tepalik Men va J umumiy ikkita aniq qo'shnisi bor (ikkita tepalik bundan mustasno) Men va J o'zlari), bu to'g'ri yoki yo'qligidan qat'iy nazar Men ga qo'shni J. Boshqacha qilib aytganda, shunday doimiy ravishda va uning parametrlari: {16,6,2,2}, ya'ni . Ushbu tenglik grafika a bilan bog'langanligini anglatadi nosimmetrik BIBD. Shrikhande grafigi ushbu parametrlarni boshqa bitta grafik bilan, ya'ni 4 × 4 bilan bo'lishadi rook grafigi, ya'ni chiziqli grafik L(K4,4) ning to'liq ikki tomonlama grafik K4,4. Oxirgi grafik - bu yagona chiziqli grafik L(Kn, n), buning uchun kuchli muntazamlik parametrlari ushbu grafani noyob ravishda aniqlamaydi, lekin boshqa grafika bilan, ya'ni Shrikhande grafigi bilan taqsimlanadi (bu roukning grafigi emas).[2][3]
Shrikxand grafigi mahalliy olti burchakli; ya'ni har bir tepalikning qo'shnilari a hosil qiladi tsikl oltita tepalikdan. Mahalliy tsiklik grafikada bo'lgani kabi, Shrikhande grafigi ham 1-skelet a Uitni uchburchagi ba'zi bir sirt; Shrixxand grafigi holatida bu sirt a torus har bir tepalik oltita uchburchak bilan o'ralgan.[4] Shunday qilib, Shrikhande grafigi a toroidal grafik. O'rnatish shakllari a muntazam xarita torusda, 32 uchburchak yuzli. Ushbu xaritaning dual skeletlari (torusga singari) Dik grafigi, kubik simmetrik grafik.
Shrikhande grafigi a emas masofadan o'tish davri grafigi. Bu eng kichigi masofa-muntazam grafik bu masofadan o'tish emas.[5]
The avtomorfizm guruhi Shrikhande grafigining tartibi 192. U grafaning tepalarida, qirralarida va yoylarida tranzitiv ravishda ishlaydi. Shuning uchun Shrixxand grafigi a nosimmetrik grafik.
The xarakterli polinom Shrikhande grafigi: . Shuning uchun Shrikhand grafigi an integral grafik: uning spektr butunlay butun sonlardan iborat.
Unda bor kitob qalinligi 4 va navbat raqami 3.[6]
Galereya
Shrikhande grafigi a toroidal grafik.
The xromatik raqam Shrikhande grafigining soni 4 ga teng.
The kromatik indeks Shrikhande grafigi 6 ga teng.
Shrikxand grafigi nosimmetrik tarzda chizilgan.
Shrikxand grafigi Hamiltoniyalik.
Izohlar
- ^ Vayshteyn, Erik V. "Shrikhande grafigi". MathWorld.
- ^ a b Shrikhande, S. S. (1959), "L ning o'ziga xosligi2 assotsiatsiya sxemasi ", Matematik statistika yilnomalari, 30: 781–798, doi:10.1214 / aoms / 1177706207, JSTOR 2237417.
- ^ Xarari, F. (1972), "Teorema 8.7", Grafika nazariyasi (PDF), Massachusets shtati: Addison-Uesli, p. 79.
- ^ Brouwer, A. E. Shrikhand grafigi.
- ^ Brouwer, A. E.; Koen, A. M .; Neumayer, A. (1989), Masofadan muntazam grafikalar, Nyu-York: Springer-Verlag, 104-105 va 136-betlar.
- ^ Jessica Vols, SAT bilan muhandislik chiziqli maketlari. Magistrlik dissertatsiyasi, Tubingen universiteti, 2018 yil
Adabiyotlar
- Xolton, D. A .; Sheehan, J. (1993), Petersen grafigi, Kembrij universiteti matbuoti, p. 270, ISBN 0-521-43594-3.
Tashqi havolalar
- Shrikhande grafigi, Piter Kemeron, 2010 yil avgust.