Wheel graph
گراف تھیوری کے ریاضیاتی شعبے میں، وہیل گراف ایک ایسا گراف ہے جو ایک واحد عالمگیر سرے کو سائیکل کے تمام عمودی حصوں سے جوڑ کر تشکیل دیا جاتا ہے۔ عمودی کے ساتھ پہیے کے گراف کو اہرام کے 1-کنکال کے طور پر بھی بیان کیا جا سکتا ہے۔ کچھ مصنفین عمودی () کے ساتھ پہیے کے گراف کو ظاہر کرنے کے لیے لکھتے ہیں ؛ دوسرے مصنفین اس کے بجائے عمودی () کے ساتھ پہیے کے گراف کو ظاہر کرنے کے لیے استعمال کرتے ہیں، جو لمبائی کے چکر کے تمام عمودی حصوں سے ایک واحد عمودی کو جوڑ کر تشکیل پاتا ہے۔ اس مضمون کا باقی حصہ سابقہ اشارے کا استعمال کرتا ہے۔ سیٹ بلڈر کی تعمیر {1,2,3,., v} کے ورٹیکس سیٹ کو دیکھتے ہوئے، وہیل گراف کے ایج سیٹ کو سیٹ بلڈر نوٹیشن میں {{1,2}, {1,3},., {1, v}, {2,3}, {3,4},., {v−1, v}, {v, 2}} کے ذریعے دکھایا جا سکتا ہے۔ خصوصیات وہیل گراف پلانر گراف ہوتے ہیں، اور ان میں ایک منفرد پلانر ایمبیڈنگ ہوتی ہے۔ مزید خاص طور پر، ہر پہیے کا گراف ایک ہیلن گراف ہے۔ وہ خود دوہری ہیں: کسی بھی پہیے کے گراف کا طیارہ دوہری ایک آئسومورفک گراف ہے۔ K4 = W4 کے علاوہ ہر زیادہ سے زیادہ طیارہ گراف، W5 یا W6 ذیلی گراف کے طور پر موجود ہوتا ہے۔ وہیل گراف میں ہمیشہ ہیملٹنین سائیکل ہوتا ہے اور Wn میں سائیکل ہوتے ہیں۔ n کی عجیب اقدار کے لیے، Wn کرومیٹک نمبر 3 کے ساتھ ایک کامل گراف ہے: سائیکل کے عمودی حصوں کو دو رنگ دیے جا سکتے ہیں، اور مرکزی عمودی حصے کو تیسرا رنگ دیا جا سکتا ہے۔ ایون n کے لیے، Wn کا کرومیٹک نمبر 4 ہوتا ہے، اور (جب n ≤ 6) کامل نہیں ہوتا ہے۔ ڈبلیو 7 واحد پہیے کا گراف ہے جو یوکلڈین سطح میں ایک یونٹ فاصلہ کا گراف ہے۔ وہیل گراف Wn کا کرومیٹک کثیر الجہتی ہے: میٹرائڈ تھیوری میں، میٹرائڈز کی دو خاص طور پر اہم خصوصی کلاسیں وہیل میٹرائڈز اور ویرل میٹرائڈز ہیں، دونوں پہیے کے گراف سے اخذ کیے گئے ہیں۔ کے وہیل میٹرائڈ پہیے ڈبلیو کے + 1 کا گرافک میٹرائڈ ہے، جبکہ کے وہیل میٹرائڈ پہیے کے بیرونی چکر کے ساتھ ساتھ اس کے تمام پھیلے ہوئے درختوں کو آزاد ہونے پر غور کرکے کے وہیل سے اخذ کیا گیا ہے۔ وہیل ڈبلیو 6 نے رمسی تھیوری پر پال ایرڈس کے قیاس آرائی کی ایک جوابی مثال فراہم کی: اس نے قیاس کیا تھا کہ مکمل گراف میں ایک ہی کرومیٹک نمبر والے تمام گرافوں میں سب سے چھوٹا رمسی نمبر ہے، لیکن فوڈری اور میک کی (1993) نے دکھایا کہ ڈبلیو 6 میں رمسی نمبر 17 ہے جبکہ اسی کرومیٹک نمبر کے ساتھ مکمل گراف، کے 4، میں رمسی نمبر 18 ہے۔ یعنی، ہر 17-ورٹیکس گراف G کے لیے، یا تو G یا اس کی تکمیل میں W6 ذیلی گراف کے طور پر ہوتا ہے، جبکہ نہ تو 17-ورٹیکس پیلے گراف اور نہ ہی اس کی تکمیل میں K4 کی کاپی ہوتی ہے۔ حوالہ جات گراف کے پیرامیٹرک خاندان پلانر گراف