श्रीखंडे ग्राफ
| Shrikhande graph | |
|---|---|
 The Shrikhande graph | |
| Named after | S. S. Shrikhande |
| Vertices | 16 |
| Edges | 48 |
| Radius | 2 |
| Diameter | 2 |
| Girth | 3 |
| Automorphisms | 192 |
| Chromatic number | 4 |
| Chromatic index | 6 |
| Book thickness | 4 |
| Queue number | 3 |
| Properties | Strongly regular Hamiltonian Symmetric Eulerian Integral |
| Table of graphs and parameters | |
ग्राफ सिद्धांत के गणित क्षेत्र में, श्रीखंडे ग्राफ 1959 में S.S. श्रीखंडे द्वारा खोजे गए नामित ग्राफों की एक गैलरी है।[1][2] यह 16 कोणबिंदु (ग्राफ़ सिद्धांत) और 48 किनारों (ग्राफ़ सिद्धांत) के साथ एक दृढ़ता से नियमित ग्राफ है, जिसमें प्रत्येक कोणबिंदु में डिग्री (ग्राफ़ सिद्धांत) 6 है। बिंदु की प्रत्येक जोड़ी में दो अन्य पड़ोसी आम हैं, चाहे बिंदु जोड़ी से जुड़ा हो या नहीं।
निर्माण
श्रीखंडे ग्राफ को केली ग्राफ के रूप में बनाया जा सकता है। कोणबिंदु सेट है। दो शीर्ष संलग्न हैं यदि और केवल यदि अंतर हो।
गुण
श्रीखंडे ग्राफ में, किन्हीं भी दो शीर्षों I और J के दो अलग-अलग पड़ोसी उभयनिष्ठ हैं (दो शीर्षों I और J को छोड़कर), जो सत्य है कि I, J के निकट है या नहीं। दूसरे शब्दों में, यह दृढ़ता से नियमित ग्राफ है और इसके पैरामीटर {16,6,2,2} है, यानी, . इस समानता का अर्थ है कि ग्राफ एक समरूपता BIBD से जुड़ा है। श्रीखंडे ग्राफ इन मापदंडों को ठीक एक अन्य ग्राफ के साथ साझा करता है, 4×4 हाथी लाइन ग्राफ, यानी रेखा ग्राफ L(K)4,4) पूर्ण द्विपक्षीय ग्राफ के4,4. बाद वाला ग्राफ एकमात्र लाइन ग्राफ है L(Kn,n) जिसके लिए मजबूत नियमितता पैरामीटर उस ग्राफ़ को विशिष्ट रूप से निर्धारित नहीं करते हैं लेकिन एक अलग ग्राफ़ के साथ साझा किए जाते हैं, अर्थात् श्रीखंडे ग्राफ़ (जो एक हाथी का ग्राफ़ नहीं है)।[2][3] श्रीखंडे ग्राफ नेबरहुड (ग्राफ थ्योरी) है; अर्थात्, प्रत्येक शीर्ष के पड़ोसी छह शीर्षों का एक चक्र ग्राफ बनाते हैं। जैसा कि किसी भी स्थानीय चक्रीय ग्राफ के साथ होता है, श्रीखंडे ग्राफ किसी सतह के त्रिकोणासन (टोपोलॉजी) का एन-कंकाल|1-कंकाल है; श्रीखंडे ग्राफ के मामले में, यह सतह एक टोरस्र्स है जिसमें प्रत्येक शीर्ष छह त्रिकोणों से घिरा हुआ है।[4] इस प्रकार, श्रीखंडे ग्राफ एक टॉरॉयडल ग्राफ है। एम्बेडिंग 32 त्रिकोणीय चेहरों के साथ टोरस में एक नियमित नक्शा (ग्राफ सिद्धांत) बनाता है। इस नक्शे के दोहरे का कंकाल (जैसा कि टोरस में एम्बेडेड है) डाइक ग्राफ, एक घन सममित ग्राफ है।
श्रीखंडे ग्राफ दूरी-सकर्मक ग्राफ नहीं है। यह सबसे छोटी दूरी-नियमित ग्राफ है जो दूरी-सकर्मक नहीं है।[5] श्रीखंडे ग्राफ का ग्राफ ऑटोमोर्फिज्म 192 क्रम का है। यह ग्राफ के किनारों पर, किनारों पर और चाप पर सकर्मक रूप से कार्य करता है। इसलिए, श्रीखंडे ग्राफ एक सममित ग्राफ है।
श्रीखंडे ग्राफ का अभिलाक्षणिक बहुपद है : . इसलिए, श्रीखंडे ग्राफ एक अभिन्न ग्राफ है: इसके वर्णक्रमीय ग्राफ सिद्धांत में पूरी तरह से पूर्णांक होते हैं।
इसमें पुस्तक की मोटाई 4 और कतार संख्या 3 है।[6]
गैलरी
श्रीखंडे ग्राफ एक टॉरॉयडल ग्राफ है।
श्रीखंडे ग्राफ की रंगीन संख्या 4 है।
श्रीखंडे ग्राफ का वर्णक्रमीय सूचकांक 6 है।
श्रीखंडे ग्राफ सममित रूप से खींचा गया।
श्रीखंडे ग्राफ हैमिल्टनियन ग्राफ है।
टिप्पणियाँ
- ↑ Weisstein, Eric W. "Shrikhande Graph". MathWorld.
- ↑ 2.0 2.1 Shrikhande, S. S. (1959), "The uniqueness of the L2 association scheme", Annals of Mathematical Statistics, 30: 781–798, doi:10.1214/aoms/1177706207, JSTOR 2237417.
- ↑ Harary, F. (1972), "Theorem 8.7", Graph Theory (PDF), Massachusetts: Addison-Wesley, p. 79, archived from the original (PDF) on November 9, 2013.
- ↑ Brouwer, A. E. Shrikhande graph.
- ↑ Brouwer, A. E.; Cohen, A. M.; Neumaier, A. (1989), Distance-Regular Graphs, New York: Springer-Verlag, pp. 104–105 and 136.
- ↑ Jessica Wolz, Engineering Linear Layouts with SAT. Master Thesis, University of Tübingen, 2018
संदर्भ
- Holton, D. A.; Sheehan, J. (1993), The Petersen Graph, Cambridge University Press, p. 270, ISBN 0-521-43594-3.
बाहरी संबंध
- The Shrikhande Graph, Peter Cameron, August 2010.
