Degree diameter problem
গ্রাফ তত্ত্বে, ডিগ্রি ব্যাসের সমস্যা হল ব্যাসের বৃহত্তম সম্ভাব্য গ্রাফ (এর শীর্ষ সেটের আকারের পরিপ্রেক্ষিতে) খুঁজে বের করার সমস্যা যাতে যে কোনও শীর্ষের বৃহত্তম ডিগ্রি সর্বাধিক হয়। এর আকার উপরে মুর বাঁধা দ্বারা আবদ্ধ; কারণ এবং শুধুমাত্র পিটারসেন গ্রাফ, হফম্যান-সিঙ্গেলটন গ্রাফ, এবং সম্ভবত ব্যাস এবং ডিগ্রির গ্রাফ (এখনও বিদ্যমান প্রমাণিত হয়নি) মুর বাঁধা অর্জন করে। সাধারণভাবে, বৃহত্তম ডিগ্রি-ব্যাস গ্রাফগুলি মুর বাউন্ডের তুলনায় আকারে অনেক ছোট। সূত্র ধরা যাক সর্বাধিক ডি ডিগ্রি এবং ব্যাস কে সহ একটি গ্রাফের জন্য শীর্ষগুলির সর্বাধিক সম্ভাব্য সংখ্যা। তারপর, মুর আবদ্ধ কোথায়ঃ এই সীমাটি খুব কম গ্রাফের জন্য অর্জন করা হয়, এইভাবে অধ্যয়নটি মুর আবদ্ধের কতটা কাছাকাছি গ্রাফ রয়েছে তার দিকে চলে যায়। অ্যাসিম্পটোটিক আচরণের জন্য এটি লক্ষ্য করুন। পরামিতি নির্ধারণ করুন। এটি অনুমান করা হয় যে সকলের জন্য কে। এটি এবং সেটি জানা যায়। আরও দেখুন একটি প্রদত্ত ব্যাস এবং সর্বাধিক ডিগ্রি ব্যাসের বৃহত্তম পরিচিত গ্রাফের কেজ (গ্রাফ তত্ত্ব) টেবিল শীর্ষ-প্রতিসম ডিগ্রি ব্যাসের ডিগ্রাফের টেবিল সর্বাধিক ডিগ্রি-এবং-ব্যাস-সীমাবদ্ধ উপগ্রাফ সমস্যা রেফারেন্স গ্রাফ তত্ত্বে গণনামূলক সমস্যা গ্রাফ দূরত্ব