मूर ग्राफ

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) द्वारा मूर आरेख का नामकरण किया गया था, जिन्होंने इन आरेखों का वर्णन और वर्गीकरण करने का प्रश्न उठाया था।

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

डिग्री और व्यास द्वारा वर्टिकल बाउंडिंग

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

G को अधिकतम डिग्री d और व्यास k के साथ कोई भी आरेख होने दें, और किसी भी शीर्ष v से प्रारम्भ होने वाली चौड़ाई से पहले खोज द्वारा बनाए गए पेड़ पर विचार करें। इस पेड़ के स्तर 0 (v स्वयं) पर 1 शीर्ष है, और स्तर 1 पर अधिकतम d कोने हैं ( v के निकटतम)। अगले स्तर में, अधिकतम d(d − 1) शीर्ष हैं: v का प्रत्येक निकटतम 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 स्तरों में बहुत कम वर्टिकल होने का कारण होगा। इसलिए, किसी भी मूर आरेख में न्यूनतम डिग्री डी और परिधि 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 परिधि चार के साथ, हीवुड आरेख डिग्री 3 और परिधि 6 के साथ, और Tutte-Coxeter आरेख डिग्री 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.