Degree diameter problem
આલેખ સિદ્ધાંતમાં, ડિગ્રી વ્યાસની સમસ્યા એ વ્યાસનો સૌથી મોટો સંભવિત આલેખ (તેના શિરોબિંદુ સમૂહના કદની દ્રષ્ટિએ) શોધવાની સમસ્યા છે, જેમાં કોઈપણ શિરોબિંદુઓની સૌથી મોટી ડિગ્રી મહત્તમ હોય છે. તેનું કદ ઉપર મૂરે બાઉન્ડ દ્વારા બંધાયેલું છે; કારણ કે અને માત્ર પીટરસન ગ્રાફ, હોફમેન-સિંગલેટન ગ્રાફ, અને સંભવતઃ વ્યાસ અને ડિગ્રીના ગ્રાફ (હજુ સુધી અસ્તિત્વમાં હોવાનું સાબિત થયું નથી) મૂરે બાઉન્ડ સુધી પહોંચે છે. સામાન્ય રીતે, સૌથી મોટા ડિગ્રી-વ્યાસના આલેખ મૂરે બાઉન્ડ કરતા કદમાં ઘણા નાના હોય છે. સૂત્ર ચાલો મહત્તમ d અને વ્યાસ k પર ડિગ્રીવાળા આલેખ માટે શિરોબિંદુઓની મહત્તમ શક્ય સંખ્યા હોઈ. પછી, મૂરે બાઉન્ડ ક્યાં છેઃ આ બાઉન્ડ ખૂબ ઓછા આલેખ માટે પ્રાપ્ત થાય છે, આમ અભ્યાસ મૂરે બાઉન્ડની કેટલા નજીક ગ્રાફ અસ્તિત્વમાં છે તે તરફ આગળ વધે છે. એસિમ્પ્ટોટિક વર્તન માટે તેની નોંધ લો. પરિમાણને વ્યાખ્યાયિત કરો. એવું અનુમાન કરવામાં આવે છે કે બધા માટે કે. તે અને તે જાણીતું છે. આ પણ જુઓ કેઝ (આલેખ સિદ્ધાંત) આપેલ વ્યાસ અને મહત્તમ ડિગ્રીના સૌથી મોટા જાણીતા આલેખનું કોષ્ટક શિરોબિંદુ-સમમિત ડિગ્રી વ્યાસ ડિગ્રાફનું કોષ્ટક મહત્તમ ડિગ્રી-અને-વ્યાસ-બાઉન્ડેડ સબગ્રાફ સમસ્યા સંદર્ભો આલેખ સિદ્ધાંતમાં કોમ્પ્યુટેશનલ સમસ્યાઓ આલેખ અંતર