Degree diameter problem
گراف تھیوری میں، ڈگری قطر کا مسئلہ قطر کے سب سے بڑے ممکنہ گراف (اس کے ورٹیکس سیٹ کے سائز کے لحاظ سے) کو تلاش کرنے کا مسئلہ ہے جس میں کسی بھی عمودی حصے کی سب سے بڑی ڈگری زیادہ سے زیادہ ہو۔ کا سائز اوپر مور باؤنڈ سے جڑا ہوا ہے ؛ کیونکہ اور صرف پیٹرسن گراف، ہوفمین-سنگلٹن گراف، اور ممکنہ طور پر قطر اور ڈگری کے گراف (ابھی تک ثابت نہیں ہوئے ہیں) مور باؤنڈ تک پہنچتے ہیں۔ عام طور پر، سب سے بڑے ڈگری قطر والے گراف مور باؤنڈ کے مقابلے میں سائز میں بہت چھوٹے ہوتے ہیں۔ فارمولہ آئیے کسی گراف کے لیے عمودی حصوں کی زیادہ سے زیادہ ممکنہ تعداد ہو جس کی ڈگری زیادہ سے زیادہ d اور قطر k ہو۔ پھر، مور باؤنڈ کہاں ہے: یہ باؤنڈ بہت کم گرافوں کے لیے حاصل کیا جاتا ہے، اس طرح مطالعہ اس طرف جاتا ہے کہ مور باؤنڈ کے کتنے قریب گراف موجود ہیں۔ غیر علامتی رویے کے لیے نوٹ کریں کہ۔ پیرامیٹر کی وضاحت کریں۔ یہ قیاس کیا جاتا ہے کہ سب کے لیے k۔ یہ معلوم ہے کہ اور وہ۔ یہ بھی دیکھیں کیج (گراف تھیوری) کسی دیئے گئے قطر اور زیادہ سے زیادہ ڈگری کے سب سے بڑے معلوم گرافوں کی ٹیبل ورٹیکس-سمیٹرک ڈگری قطر ڈیگرافس کی ٹیبل زیادہ سے زیادہ ڈگری اور قطر سے منسلک ذیلی گراف مسئلہ حوالہ جات گراف تھیوری گراف فاصلے میں کمپیوٹیشنل مسائل