Degree diameter problem
ग्राफ सिद्धांत में, डिग्री व्यास समस्या व्यास के सबसे बड़े संभव ग्राफ (इसके शीर्ष समूह के आकार के संदर्भ में) को खोजने की समस्या है जैसे कि किसी भी शीर्ष की सबसे बड़ी डिग्री अधिक से अधिक हो। का आकार ऊपर मूर बाउंड से घिरा हुआ है और केवल पीटरसन ग्राफ, हॉफमैन-सिंगलेटन ग्राफ, और संभवतः व्यास और डिग्री के ग्राफ (अभी तक मौजूद नहीं हैं) मूर बाउंड तक पहुंचते हैं। सामान्य तौर पर, सबसे बड़े डिग्री-व्यास वाले ग्राफ मूर बाउंड की तुलना में आकार में बहुत छोटे होते हैं। सूत्र मान लीजिए कि अधिकतम डी और व्यास के डिग्री वाले ग्राफ के लिए शीर्षों की अधिकतम संभव संख्या हो। फिर, मूर बाउंड कहां हैः यह बाउंड बहुत कम ग्राफों के लिए प्राप्त किया जाता है, इस प्रकार अध्ययन इस बात पर जाता है कि मूर बाउंड के कितने करीब ग्राफ मौजूद हैं। एसिम्प्टोटिक व्यवहार के लिए ध्यान दें कि। पैरामीटर को परिभाषित करें। यह अनुमान लगाया जाता है कि सभी के लिए के. यह ज्ञात है कि और वह। किसी दिए गए व्यास और अधिकतम डिग्री के सबसे बड़े ज्ञात ग्राफ की केज (ग्राफ सिद्धांत) तालिका देखें शीर्ष-सममित डिग्री व्यास डिग्राफ की तालिका अधिकतम डिग्री और व्यास-सीमित उपग्राफ समस्या संदर्भ ग्राफ सिद्धांत में कम्प्यूटेशनल समस्याएं ग्राफ दूरी