श्रीखंडे ग्राफ
| श्रीखंडे लेखाचित्र | |
|---|---|
| File:Shrikhande graph square.svg श्रीखंडे लेखाचित्र | |
| Named after | S. S. श्रीखंडे |
| 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 | अत्यधिक नियमित ग्राफ़|दृढ़तापूर्वक नियमित]] हैमिल्टनियन सममित यूलेरियन अभिन्न] |
| 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) पूर्ण द्विपक्षीय लेखाचित्र K4,4 का लाइन लेखाचित्र L(Kn,n) है जिसके लिए मजबूत नियमितता परिमाप उस लेखाचित्र को विशिष्ट रूप से निर्धारित नहीं करते हैं, लेकिन एक अलग लेखाचित्र के साथ साझा किए जाते हैं, अर्थात् श्रीखंडे लेखाचित्र (जो एक रूक का लेखाचित्र नहीं है)।[2][3]
श्रीखंडे लेखाचित्र नेबरहुड (लेखाचित्र थ्योरी) है; अर्थात्, प्रत्येक शीर्ष के पड़ोसी छह शीर्षों का एक चक्र लेखाचित्र बनाते हैं। जैसा कि किसी भी स्थानीय चक्रीय लेखाचित्र के साथ होता है, श्रीखंडे लेखाचित्र किसी सतह के त्रिकोणासन (टोपोलॉजी) का एन-स्केलेटन है; श्रीखंडे लेखाचित्र की स्थिति में, यह सतह एक टोरस्र्स है जिसमें प्रत्येक शीर्ष छह त्रिकोणों से घिरा हुआ है।[4] इस प्रकार, श्रीखंडे लेखाचित्र एक टोराइडी लेखाचित्र है। अंतःस्थापन 32 त्रिकोणीय शीर्षकों के साथ टोरस में एक नियमित नक्शा (लेखाचित्र सिद्धांत) बनाता है। इस नक्शे के दोहरे का स्केलेटन (जैसा कि टोरस में अंतःस्थापित है) डाइक लेखाचित्र, एक घन सममित लेखाचित्र है।
श्रीखंडे लेखाचित्र दूरी-सकर्मक लेखाचित्र नहीं है। यह सबसे छोटी दूरी-नियमित लेखाचित्र है जिसमें दूरी-सकर्मक नहीं है।[5]
श्रीखंडे लेखाचित्र का स्वसमाकृतिकता 192 का क्रम है। यह लेखाचित्र के किनारों और चाप पर सकर्मक रूप से कार्य करता है। इसलिए, श्रीखंडे लेखाचित्र एक सममित लेखाचित्र है।
श्रीखंडे लेखाचित्र का अभिलाक्षणिक बहुपद है : . इसलिए, श्रीखंडे लेखाचित्र एक अभिन्न लेखाचित्र है: इसके वर्णक्रमीय लेखाचित्र सिद्धांत में पूरी तरह से पूर्णांक होते हैं।
इसमें मोटाई 4 और कतार संख्या 3 है।[6]
गैलरी
श्रीखंडे ग्राफ एक टॉरॉयडल ग्राफ है।
- Shrikhande graph 4COL.svg
श्रीखंडे ग्राफ की रंगीन संख्या 4 है।
- Shrikhande graph 6color edge.svg
श्रीखंडे ग्राफ का वर्णक्रमीय सूचकांक 6 है।
श्रीखंडे ग्राफ सममित रूप से खींचा गया।
- Shrikhande Lombardi.svg
श्रीखंडे ग्राफ हैमिल्टनियन ग्राफ है।
टिप्पणियाँ
- ↑ 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.
