Wheel graph
ग्राफ सिद्धांत के गणितीय विषय में, एक चक्र ग्राफ एक एकल सार्वभौमिक शीर्ष को एक चक्र के सभी शीर्षों से जोड़कर बनाया गया एक ग्राफ है। शीर्षों के साथ एक पहिया ग्राफ को एक पिरामिड के 1-कंकाल के रूप में भी परिभाषित किया जा सकता है। कुछ लेखक शीर्ष () के साथ एक पहिया ग्राफ को निरूपित करने के लिए लिखते हैं; अन्य लेखक इसके बजाय शीर्ष () के साथ एक पहिया ग्राफ को निरूपित करने के लिए उपयोग करते हैं, जो लंबाई के चक्र के सभी शीर्षों के लिए एक एकल शीर्ष को जोड़कर बनाया जाता है। इस लेख का शेष भाग पूर्व संकेतन का उपयोग करता है। सेट-बिल्डर का निर्माण {1,2,3,., v} के एक शीर्ष सेट को देखते हुए, व्हील ग्राफ के किनारे के सेट को सेट-बिल्डर संकेतन में {{{1,2,3}, {1,3},., {1, v}, {2,3}, {3,4},., {v−1, v}, {v, 2}} द्वारा दर्शाया जा सकता है। गुण-चक्र ग्राफ समतल ग्राफ होते हैं और इनमें एक अद्वितीय समतल एम्बेडिंग होती है। विशेष रूप से, प्रत्येक चक्र ग्राफ एक हेलिन ग्राफ है। वे स्व-द्वैत हैंः किसी भी चक्र ग्राफ का समतलीय द्वैत एक समरूपी ग्राफ है। के4 = डब्ल्यू4 के अलावा प्रत्येक अधिकतम समतलीय ग्राफ में डब्ल्यू5 या डब्ल्यू6 उपग्राफ के रूप में होता है। पहिया ग्राफ में हमेशा एक हैमिल्टनियन चक्र होता है और Wn में चक्र होते हैं। n के विषम मानों के लिए, Wn रंगीन संख्या 3 के साथ एक पूर्ण ग्राफ हैः चक्र के शीर्षों को दो रंग दिए जा सकते हैं, और केंद्र शीर्ष को तीसरा रंग दिया जा सकता है। सम n के लिए, Wn की क्रोमाटिक संख्या 4 है, और (जब n ≤ 6) सही नहीं है। डब्ल्यू7 एकमात्र पहिया ग्राफ है जो यूक्लिडियन तल में एक इकाई दूरी ग्राफ है। व्हील ग्राफ डब्ल्यू. एन. का क्रोमेटिक बहुपद हैः मैट्रायड सिद्धांत में, मैट्रायड के दो विशेष रूप से महत्वपूर्ण विशेष वर्ग व्हील मैट्रायड और व्हर्ल मैट्रायड हैं, दोनों व्हील ग्राफ से प्राप्त होते हैं। के-व्हील मैट्रायड व्हील डब्ल्यूके + 1 का ग्राफिक मैट्रायड है, जबकि के-व्हर्ल मैट्रायड व्हील के बाहरी चक्र के साथ-साथ इसके सभी फैले हुए पेड़ों को स्वतंत्र मानते हुए के-व्हील से लिया गया है। चक्र डब्ल्यू6 ने रैमसे सिद्धांत पर पॉल एर्दोस के एक अनुमान के लिए एक प्रति-उदाहरण प्रदान कियाः उन्होंने अनुमान लगाया था कि एक ही वर्णात्मक संख्या वाले सभी ग्राफों में पूर्ण ग्राफ में सबसे छोटी रैमसे संख्या है, लेकिन फॉड्री और मैके (1993) ने दिखाया कि डब्ल्यू6 में रैमसे संख्या 17 है जबकि एक ही वर्णात्मक संख्या, के4 वाले पूर्ण ग्राफ में रैमसे संख्या 18 है। अर्थात्, प्रत्येक 17-वर्टेक्स ग्राफ जी के लिए, या तो जी या इसके पूरक में एक उपग्राफ के रूप में डब्ल्यू 6 होता है, जबकि न तो 17-वर्टेक्स पाले ग्राफ और न ही इसके पूरक में के 4 की एक प्रति होती है। ग्राफ़ के पैरामीट्रिक परिवार प्लैनर ग्राफ़ के संदर्भ