मूर ग्राफ

Unsolved problem in गणित:

क्या मूर ग्राफ 5 और डिग्री 57 के साथ सम्मिलित है?

(more unsolved problems in गणित)

आरेख़ सिद्धांत में मूर आरेख़ एक ऐसा नियमित आरेख है जिसकी परिधि (सबसे छोटे वृत्त की लंबाई) उसके व्यास (सबसे दूर के दो शीर्षों के बीच की दूरी) से दो गुना अधिक होती है। यदि इस प्रकार के आरेख की डिग्री d और इसका व्यास k है तो इसकी परिधि 2k + 1 के बराबर होती है यह सच है कि डिग्री d और व्यास k के आरेख के लिए यदि और केवल यदि इसके शीर्षों की संख्या बराबर होती है:

$1+d\sum _{i=0}^{k-1}(d-1)^{i},$

इस डिग्री और व्यास के साथ किसी भी आरेख में शीर्ष की सबसे बड़ी संभव संख्या पर एक ऊपरी सीमा होती है इसलिए ये रेखांकन उनके मापदंडों के लिए डिग्री व्यास की समस्या को हल करते हैं।

मूर आरेख G की एक और समतुल्य परिभाषा यह है कि इसकी परिधि g = 2k + 1 और n/g(m – n + 1), g लंबाई का वृत्त है जहाँ n और m क्रमश: शीर्षों और किनारों की संख्या G है। वे वास्तव में उन वृत्तों की संख्या के संबंध में शीर्ष पर हैं जिनकी लंबाई आरेख की परिधि है।

एडवर्ड एफ.मूर के नाम पर हॉफमैन & सिंगलटन (1960) द्वारा मूर आरेख का नामकरण किया गया था। जिन्होंने इन आरेखों का वर्णन और वर्गीकरण करने का प्रश्न उठाया था।

डिग्री और व्यास के दिए गए संयोजन के लिए अधिकतम संभावित संख्या होने के साथ-साथ, मूर आरेख़ में दी गई डिग्री और परिधि के साथ एक नियमित आरेख़ के लिए न्यूनतम संभव संख्या में शीर्ष होते हैं। अर्थात्, कोई भी मूर आरेख एक केज (आरेख सिद्धांत) है। मूर आरेख़ में शीर्षों की संख्या के लिए एक सूत्र को सामान्यीकृत किया जा सकता है क्योकि मूर आरेख़ की परिभाषा मे सम परिधि के साथ-साथ विषम परिधि और रेखांकन केज आरेख भी हो सकते हैं।

डिग्री और व्यास द्वारा शीर्ष सीमांकन

मूर ग्राफ के रूप में पीटरसन आरेख किसी चौड़ाई वाले प्रथम खोज वृत्त के iवें स्तर में d(d − 1)ⁱ शीर्ष होते हैं।

माना कि G अधिकतम डिग्री d और व्यास k के साथ कोई भी आरेख और किसी भी शीर्ष v से प्रारम्भ होने वाली चौड़ाई से पहले एक खोज द्वारा बनाया गया है जिस पर विचार करें कि इस शृंखला के स्तर 0 (v स्वयं) पर 1 शीर्ष है और स्तर 1 (v के निकटतम) पर अधिकांश d शीर्ष हैं। v स्वयं पर 1 शीर्ष है और स्तर 1 पर अधिकतम d शीर्ष हैं v के निकटतम अगले स्तर में, अधिकतम d(d − 1) शीर्ष हैं: v का प्रत्येक निकटतम भाग से जुड़ने के लिए यह अपनी एक निकटता का उपयोग करता है और इसलिए स्तर 2 पर अधिकतम d − 1 निकटतम शीर्ष हो सकते हैं। सामान्यतः एक समान तर्क दर्शाता है कि किसी भी स्तर 1 ≤ i ≤ k पर, अधिकतम d(d − 1)ⁱ⁻¹ शीर्ष हो सकते हैं। इस प्रकार, शीर्षों की कुल संख्या अधिक से अधिक हो सकती है:

$1+d\sum _{i=0}^{k-1}(d-1)^{i}.$

हॉफमैन & सिंगलटन (1960) ने मूल रूप से मूर आरेख को एक आरेख के रूप में परिभाषित किया था जिसके लिए शीर्ष की संख्या पर यह सीमा पूरी तरह से समान है। इसलिए किसी भी मूर आरेख़ में अधिकतम डिग्री d और व्यास k वाले सभी आरेख़ों में अधिकतम संभव शीर्ष होते हैं। बाद में सिंगलटन (1968) ने दिखाया कि मूर आरेख़ को समान रूप से व्यास k और परिधि 2k + 1 के रूप में परिभाषित किया जा सकता है ये दो आवश्यकताएं आरेख को डिग्री d के लिए डिग्री d पर नियमित होने के लिए बाध्य करती हैं और शीर्ष के गणनात्मक सूत्र को संतुष्ट करती हैं।

केज आरेख के रूप में मूर रेखांकन

इसकी अधिकतम डिग्री और इसके व्यास के संदर्भ में एक आरेख में शीर्षों की संख्या की ऊपरी सीमा के अतिरिक्त समान विधियों के माध्यम से इसकी न्यूनतम डिग्री और इसकी परिधि के संदर्भ में शीर्षों की संख्या पर एक निचली सीमा की गणना कर सकते हैं। माना कि G की न्यूनतम डिग्री d और परिधि 2k + 1 है। अपेक्षाकृत रूप से एक प्रारंभिक शीर्ष v चुनें और पहले की तरह चौड़ाई प्रथम खोज शीर्ष को v पर इस शीर्ष के स्तर 0 (v स्वयं) पर एक शीर्ष होना चाहिए और कम से कम d शीर्ष स्तर 1 पर स्तर 2 (k > 1 के लिए), कम से कम d(d − 1) शीर्ष होने चाहिए, क्योंकि स्तर 1 पर प्रत्येक शीर्ष में कम से कम d − 1 शेष आसन्नताएं होती हैं और कोई दो शीर्ष नहीं होते हैं। स्तर 1 एक दूसरे के निकट हो सकता है या स्तर 2 पर एक साझा शीर्ष पर हो सकता है क्योंकि यह अनुमानित परिधि से छोटा वृत्त बना देता है व्यापक रूप से समान तर्क दर्शाता है कि किसी भी स्तर 1 ≤ i ≤ k पर कम से कम d(d − 1)ⁱ शीर्ष होने चाहिए। इस प्रकार, शीर्षों की कुल संख्या कम से कम होनी चाहिए:

$1+d\sum _{i=1}^{k-1}(d-1)^{i}.$

मूर आरेख़ में, शीर्षों की संख्या पर निर्धारित यह सीमा पूरी तरह से प्राप्त होती है। प्रत्येक मूर आरेख़ की परिधि ठीक 2k + 1 होती है इसमें उच्च परिधि रखने के लिए पर्याप्त शीर्ष नहीं हैं और एक छोटा वृत्त किसी चौड़ाई वाले पहले खोज वृत्त के पहले k स्तरों में बहुत कम शीर्ष होने का कारण था इसलिए, किसी भी मूर आरेख में न्यूनतम डिग्री d और परिधि 2k + 1 के साथ सभी आरेखों में न्यूनतम संख्या संभव है क्योकि यह एक केज आरेख है।

यहां तक ​​​​कि 2k परिधि के लिए, एक शीर्ष के मध्य बिंदु से प्रारम्भ होने वाली एक चौड़ाई पहली खोज का वृत्त बना सकती हैं। न्यूनतम डिग्री d के साथ इस परिधि के आरेख में न्यूनतम संख्या में शीर्ष पर परिणामी सीमा है:

$2\sum _{i=0}^{k-1}(d-1)^{i}=1+(d-1)^{k-1}+d\sum _{i=0}^{k-2}(d-1)^{i}.$

सूत्र के दाहिने हाथ की ओर इसके अतिरिक्त एक शीर्ष से प्रारम्भ होने वाली चौड़ाई वाले पहले खोज वृत्त में शीर्षों की संख्या की गणना करता है। इस संभावना के लिए लेखांकन कि वृत्त के अंतिम स्तर में एक शीर्ष पिछले स्तर में d शीर्षों के निकटम हो सकता है। इस प्रकार, मूर आरेख़ को कभी-कभी उन आरेख़ मे सम्मिलित करने के रूप में परिभाषित किया जाता है जो वास्तव में इस सीमा को पूर्ण करते हैं। जिससे ऐसा कोई भी आरेख केज आरेख होता है।

उदाहरण

हॉफमैन-सिंगलटन प्रमेय में कहा गया है कि परिधि 5 के साथ किसी भी मूर आरेख की डिग्री 2, 3, 7 या 57 होना एक मूर आरेख हैं:

• n > 2 नोड्स पर पूर्ण रेखांकन K_n (व्यास 1, परिधि 3, डिग्री n − 1, क्रम n)
• विषम वृत्त आरेख C_2n+1 (व्यास n, परिधि 2n + 1, डिग्री 2, क्रम 2n + 1)
• पीटरसन आरेख (व्यास 2, परिधि 5, डिग्री 3, क्रम 10)
• हॉफमैन-सिंगलटन आरेख (व्यास 2, परिधि 5, डिग्री 7, क्रम 50)
• व्यास 2, परिधि 5, डिग्री 57 और क्रम 3250 का एक काल्पनिक आरेख है जिसका अस्तित्व अज्ञात है।

हालांकि सभी ज्ञात मूर आरेख़ शीर्ष-सकर्मक आरेख हैं यदि यह काल्पनिक आरेख सम्मिलित है तो शीर्ष-सकर्मक रेखांकन नहीं हो सकता है क्योंकि इसके स्वसमाकृतिकता समूह में अधिकतम अनुक्रम 375 पर हो सकता है जो इसके शीर्षों की संख्या से कम है।

यदि मूर आरेख़ की सामान्यीकृत परिभाषा जो परिधि आरेख़ की स्वीकृति देती है इसका उपयोग किया जाता है तो सम परिधि मूर आरेख़ सामान्यीकृत बहुभुज (संभावित पतित) के घटना आरेख़ के अनुरूप होता हैं। कुछ उदाहरण मे C_2n सम वृत्त हैं, पूर्ण द्विभाज्य रेखांकन K_n,n परिधि 4 के साथ हीवुड आरेख डिग्री 3 और परिधि 6 के साथ टुट्टे-कॉक्सेटर आरेख डिग्री 3 और परिधि 8 के साथ अधिक सामान्यतः यह ज्ञात है कि ऊपर सूचीबद्ध आरेख़ के अतिरिक्त सभी मूर आरेख़ की परिधि 5, 6, 8, या 12 होती है। एक सामान्यीकृत n-गॉन के लिए n के संभावित मानों के विषय में प्रयुक्त हिगमैन प्रमेय से सम परिधि की स्थिति का अनुसरण करता है।

यह भी देखें

• किसी दिए गए व्यास और अधिकतम डिग्री के सबसे बड़े ज्ञात रेखांकन की तालिका

संदर्भ

• Azarija, Jernej; Klavžar, Sandi (2015), "Moore Graphs and Cycles Are Extremal Graphs for Convex Cycles", Journal of Graph Theory, 80: 34–42, arXiv:1210.6342, doi:10.1002/jgt.21837, S2CID 333785
• Bannai, E.; Ito, T. (1973), "On finite Moore graphs", Journal of the Faculty of Science, the University of Tokyo. Sect. 1 A, Mathematics, 20: 191–208, MR 0323615, archived from the original on 2012-04-24
• Bollobás, Béla (1998), Modern Graph Theory, Graduate Texts in Mathematics, vol. 184, Springer-Verlag.
• Dalfó, C. (2019), "A survey on the missing Moore graph" (PDF), Linear Algebra and Its Applications, 569: 1–14, doi:10.1016/j.laa.2018.12.035, hdl:2117/127212, MR 3901732, S2CID 126689579
• Damerell, R. M. (1973), "On Moore graphs", Mathematical Proceedings of the Cambridge Philosophical Society, 74 (2): 227–236, Bibcode:1973PCPS...74..227D, doi:10.1017/S0305004100048015, MR 0318004
• Erdős, Paul; Rényi, Alfréd; Sós, Vera T. (1966), "On a problem of graph theory" (PDF), Studia Sci. Math. Hungar., 1: 215–235, archived from the original (PDF) on 2016-03-09, retrieved 2010-02-23.
• Hoffman, Alan J.; Singleton, Robert R. (1960), "Moore graphs with diameter 2 and 3", IBM Journal of Research and Development, 5 (4): 497–504, doi:10.1147/rd.45.0497, MR 0140437
• Mačaj, Martin; Širáň, Jozef (2010), "Search for properties of the missing Moore graph", Linear Algebra and Its Applications, 432 (9): 2381–2398, doi:10.1016/j.laa.2009.07.018.
• Singleton, Robert R. (1968), "There is no irregular Moore graph", American Mathematical Monthly, 75 (1): 42–43, doi:10.2307/2315106, JSTOR 2315106, MR 0225679

बाहरी संबंध

• Brouwer and Haemers: Spectra of graphs
• Eric W. Weisstein, Moore Graph (Hoffman-Singleton Theorem) at MathWorld.