मूर ग्राफ

Unsolved problem in mathematics:

Does a Moore graph with girth 5 and degree 57 exist?

(more unsolved problems in mathematics)

ग्राफ़ सिद्धांत में, एक मूर ग्राफ़ एक नियमित ग्राफ़ होता है जिसका परिधि (ग्राफ़ सिद्धांत) (सबसे छोटा चक्र (ग्राफ़ सिद्धांत) लंबाई) इसके व्यास (ग्राफ़ सिद्धांत) के दोगुने से अधिक होता है (सबसे दूर के दो वर्टेक्स (ग्राफ़ सिद्धांत) के बीच की दूरी) . यदि ऐसे ग्राफ की [[ डिग्री (ग्राफ सिद्धांत) ]] है 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. वे वास्तव में उन चक्रों की संख्या के संबंध में चरम हैं जिनकी लंबाई ग्राफ की परिधि है।

मूर ग्राफ का नामकरण किसके द्वारा किया गया था Hoffman & Singleton (1960) एडवर्ड एफ मूर के बाद, जिन्होंने इन ग्राफों का वर्णन और वर्गीकरण करने का प्रश्न उठाया।

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

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

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

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

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

Hoffman & Singleton (1960) मूल रूप से एक मूर ग्राफ़ को एक ग्राफ़ के रूप में परिभाषित किया गया था, जिसके लिए वर्टिकल की संख्या पर यह सीमा पूरी तरह से मिलती है। इसलिए, किसी भी मूर ग्राफ़ में अधिकतम डिग्री वाले सभी ग्राफ़ों में अधिकतम वर्टिकल संभव हैं d और व्यास k.

बाद में, Singleton (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 होनी चाहिए। मूर ग्राफ हैं:

• पूरा रेखांकन K_n पर n > 2 नोड्स (व्यास 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 के साथ, और टट्टे-कॉक्सेटर ग्राफ डिग्री 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.