पीटरसन ग्राफ

Petersen graph
Petersen graph
	The Petersen graph is most commonly drawn as a pentagon with a pentagram inside, with five spokes.
Named after	Julius Petersen
Vertices	10
Edges	15
Radius	2
Diameter	2
Girth	5
Automorphisms	120 (S5)
Chromatic number	3
Chromatic index	4
Fractional chromatic index	3
Genus	1
Properties	Cubic; Strongly regular; Distance-transitive; Snark
	Table of graphs and parameters

लेखाचित्र सिद्धांत के गणित क्षेत्र में, पीटरसन लेखाचित्र एक अप्रत्यक्ष लेखाचित्र है जिसमें 10 कोने (लेखाचित्र सिद्धांत) और 15 किनारे (लेखाचित्र सिद्धांत) हैं। यह एक छोटा लेखाचित्र है जो लेखाचित्र सिद्धांत में कई समस्याओं के लिए एक उपयोगी उदाहरण और प्रति उदाहरण के रूप में कार्य करता है। पीटरसन लेखाचित्र का नाम जूलियस पीटरसन के नाम पर रखा गया है, जिन्होंने 1898 में इसका निर्माण सबसे छोटे घनाकार लेखाचित्र के रूप में किया था जिसमें कोई त्रयी-धार-रंगत नहीं थी।^[1]^[2]

हालांकि लेखाचित्र को सामान्यतः पीटरसन को श्रेय दिया जाता है, वस्तुतः यह पहली बार 12 साल पहले ए. बी. केम्पे (1886) के एक लेख में दिखाई दिया था। केम्पे ने देखा कि इसके कोने डेसार्गेस समाकृति की दस पंक्तियों का प्रतिनिधित्व कर सकते हैं, और इसके किनारे उन पंक्तियों के जोड़े का प्रतिनिधित्व करते हैं जो समाकृति के दस बिंदुओं में से एक पर नहीं मिलते हैं।^[3]

डोनाल्ड नुथ कहते हैं कि पीटरसन लेखाचित्र एक उल्लेखनीय समाकृति है जो सामान्य रूप से लेखाचित्र के लिए सही हो सकता है, इसके बारे में कई आशावादी भविष्यवाणियों के प्रति उदाहरण के रूप में कार्य करता है।^[4] पीटरसन लेखाचित्र उष्णकटिबंधीय ज्यामिति में भी दिखाई देता है। पीटरसन लेखाचित्र पर शंकु को स्वाभाविक रूप से पांच-अंकित तर्कसंगत उष्णकटिबंधीय वक्रों के मापांक स्थान के साथ पहचाना जाता है।

निर्माण

Error creating thumbnail:

केनेसर लेखाचित्र के रूप में पीटरसन लेखाचित्र

KG_{5,2}

पीटरसन लेखाचित्र रेखा लेखाचित्र $K_{5}$ bका पूरक लेखाचित्र है। यह क्नेजर लेखाचित्र $KG_{5,2}$ भी है; इसका अर्थ यह है कि इसमें 5-तत्व समुच्चय के प्रत्येक 2-तत्व उपसमुच्चय के लिए एक शीर्ष है, और दो कोने किनारे से जुड़े हुए हैं यदि और केवल यदि संबंधित 2-तत्व उपसमुच्चय एक दूसरे से अलग हैं। प्ररूप $KG_{2n-1,n-1}$ के क्नेजर लेखाचित्र के रूप में यह एक विषम लेखाचित्र का उदाहरण है।

ज्यामितीय रूप से, पीटरसन लेखाचित्र हेमी-द्वादशफलक के शिखर और किनारों द्वारा गठित लेखाचित्र है, यानी, एकद्वादशफ़लक विपरीत बिंदुओं, रेखाओं और रूपचित्र को एक साथ पहचाना जाता है।

अंतःस्थापन

पीटरसन लेखाचित्र तलीय लेखाचित्र है। किसी भी गैर-तलीय लेखाचित्र में मामूली (लेखाचित्र सिद्धांत) या तो पूरा लेखाचित्र $K_{5}$ होता है, या पूर्ण द्विदलीय लेखाचित्र $K_{3,3}$ , लेकिन पीटरसन लेखाचित्र में दोनों लघु हैं। $K_{5}$ h> लघु को परिपूर्ण मिलान के किनारों को संकुचित कर बनाया जा सकता है, उदाहरण के लिए पहली तस्वीर में पांच छोटे किनारे हैं। $K_{3,3}$ h> लघु को एक कोणबिंदु (उदाहरण के लिए 3-सममितीय रेखाचित्र के केन्द्रीय कोणबिंदु) को हटाकर और हटाए गए कोणबिंदु के प्रत्येक प्रतिवैस के लिए एक छोर आपतित को अनुबंधित करके बनाया जा सकता है।

File:Petersen graph, two crossings.svg

1-तलीय है।

पीटरसन लेखाचित्र का सबसे सामान्य और सममित तल आरेखण, पंचभुज के भीतर पेंटाग्राम के रूप में, पांच प्रसंकरण हैं। हालांकि, प्रसंकरण को कम करने के लिए यह सबसे अच्छा रेखाचित्र नहीं है; केवल दो प्रसंकरण के साथ एक और रेखाचित्र उपस्थित है (चित्र में दिखाया गया है)। क्योंकि यह गैरतलीय है, इसमें किसी भी रेखाचित्र में कम से कम एक प्रसंकरण है, और यदि किसी रेखाचित्र से एक प्रसंकरण छोर को हटा दिया जाता है तो यह गैरतलीय रहता है और एक और प्रसंकरण होता है; इसलिए, इसकी प्रसंकरण संख्या बिल्कुल 2 है। इस रेखाचित्र में प्रत्येक किनारे को एक बार पार किया जाता है, इसलिए पीटरसन लेखाचित्र 1-तलीय लेखाचित्र है। एक स्थूलक पर पीटरसन लेखाचित्र को किनारे के प्रसंकरण के बिना खींचा जा सकता है; इसलिए इसमें श्रेणी (गणित) 1 है।

Error creating thumbnail:

पीटरसन लेखाचित्र एक इकाई दूरी का लेखाचित्र है: इसे समतल में प्रत्येक किनारे की इकाई लंबाई के साथ खींचा जा सकता है।

पीटरसन लेखाचित्र को समतल में (प्रसंकरण के साथ) इस तरह से भी खींचा जा सकता है कि सभी किनारों की लंबाई समान हो। यानी यह एक इकाई दूरी का लेखाचित्र है।

सबसे सरलतम गैर-उन्मुख सतह जिस पर प्रसंकरण के बिना पीटरसन लेखाचित्र को अंतः स्थापित किया जा सकता है, वह प्रक्षेपी तल है। यह पीटरसन लेखाचित्र के अर्ध-द्वादशफ़लक निर्माण द्वारा दी गई अंतःस्थापन है (चित्र में दिखाया गया है)। रेखाचित्र के केंद्र में पांच-बिंदु तारिका के भीतर एक तिर्यक्-आवरण रखकर और इस तिर्यक्-आवरण के माध्यम से तारिका किनारों को परिच्छेदन करके पीटरसन लेखाचित्र के मानक पेंटागोनल रेखाचित्र से प्रक्षेपीय तल अंतःस्थापन भी बनाई जा सकती है; परिणामी रेखाचित्र में छह पंचकोणीय छोर हैं। यह निर्माण एक नियमित मानचित्र (लेखाचित्र सिद्धांत) बनाता है और दिखाता है कि पीटरसन लेखाचित्र में गैर-उन्मुख श्रेणी 1 है।

File:Petersen-graph.png

पीटरसन लेखाचित्र और संबद्ध मानचित्र प्रक्षेपी तल में सन्निहित है। वृत्त पर विपरीत बिंदुओं की पहचान की जाती है, जो गैर-उन्मुख श्रेणी 1 की एक बंद सतह की उपज होती है।

समरूपता

पीटरसन लेखाचित्र दृढ़ता से नियमित लेखाचित्र है (हस्ताक्षर एसआरजी (10,3,0,1) के साथ)। यह सममित लेखाचित्र भी है, जिसका अर्थ है कि यह बढ़त-सकर्मक लेखाचित्र और शीर्ष-सकर्मक लेखाचित्र है। अधिक दृढ़ता से, यह 3-चाप-संक्रमणीय है: पीटरसन लेखाचित्र में प्रत्येक निर्देशित तीन-किनारे पथ को लेखाचित्र के समरूपता द्वारा हर दूसरे ऐसे पथ में परिवर्तित किया जा सकता है।^[5] यह केवल 13 घन दूरी-नियमित लेखाचित्ऱ में से एक है।^[6]

पीटरसन लेखाचित्र का लेखाचित्र स्वसमाकृतिकता सममित समूह $S_{5}$ है; $S_{5}$ की क्रिया पीटरसन लेखाचित्र पर इसके निर्माण से केनेसर लेखाचित्र के रूप में अनुसरण करता है। पीटरसन लेखाचित्र एक अंतर्भाग (लेखाचित्र सिद्धांत) है: पीटरसन लेखाचित्र का हर लेखाचित्र समरूपता अपने आप में एक स्वसमाकृतिकता है।^[7] जैसा कि चित्रों में दिखाया गया है, पीटरसन लेखाचित्र के चित्र पंचमार्ग या त्रिमार्ग समरूपता प्रदर्शित कर सकते हैं, लेकिन तल में पीटरसन लेखाचित्ऱ को इस तरह से खींचना संभव नहीं है कि रेखाचित्र पूर्ण समरूपता समूह को लेखाचित्र प्रदर्शित कर सके।

समरूपता के अपने उच्च स्तर होने पर भी, पीटरसन लेखाचित्र केली लेखाचित्र नहीं है। यह सबसे छोटा शीर्ष-सकर्मक लेखाचित्र है जो केली लेखाचित्र नहीं है।^{[lower-alpha 1]}

हैमिल्टनियन पथ और चक्र

File:Petersen2 tiny.svg

पीटरसन लेखाचित्र हाइपो-हैमिल्टनियन है: किसी भी शीर्ष को हटाकर, जैसे रेखाचित्र में केंद्र शीर्ष, शेष लेखाचित्र हैमिल्टनियन है। क्रम-3 सममिति वाला यह रेखाचित्र इसके केम्पे (1886) द्वारा दिया गया है .

पीटरसन लेखाचित्र में हैमिल्टनियन पथ है लेकिन कोई हैमिल्टनियन चक्र नहीं है। यह सबसे छोटा ब्रिजलेस घनाकार लेखाचित्र है जिसमें कोई हैमिल्टनियन चक्र नहीं है। यह हाइपोहैमिल्टनियन लेखाचित्र है, जिसका अर्थ है कि इसका कोई हैमिल्टनियन चक्र नहीं है, किसी भी शीर्ष को हटाने से यह हैमिल्टनियन बन जाता है, और यह सबसे छोटा हाइपोहैमिल्टनियन लेखाचित्र है।

एक परिमित आनुषंगिक कोणबिंदु-सकर्मक लेखाचित्र के रूप में जिसमें हैमिल्टनियन चक्र नहीं है, पीटरसन लेखाचित्र लोवाज़ निराधार कल्पना के एक संस्करण के लिए एक प्रति उदाहरण है, लेकिन निराधार कल्पना के विहित सूत्रीकरण एक हैमिल्टनियन पथ के लिए पूछता है और पीटरसन लेखाचित्र द्वारा सत्यापित किया जाता है।

हैमिल्टनियन चक्रों के साथ केवल पांच जुड़े शीर्ष-संक्रमणीय लेखाचित्र ज्ञात हैं: पूरा लेखाचित्र K₂, पीटरसन लेखाचित्र, कॉक्सेटर लेखाचित्र और पीटरसन और कॉक्सेटर लेखाचित्र से प्राप्त दो लेखाचित्र प्रत्येक शीर्ष को त्रिकोण के साथ बदलते हैं। ^[6] यदि G अधिकतम 3r + 1 शीर्षों वाला 2-आनुषंगिक, r-नियमित लेखाचित्ऱ है, तो G हैमिल्टनियन है या G पीटरसन लेखाचित्ऱ है।^[8]

यह देखने के लिए कि पीटरसन लेखाचित्र में कोई हैमिल्टनियन चक्र C नहीं है, कर्तन में किनारों पर विचार करें जो आंतरिक 5-चक्र को बाहरी से अलग करता है। यदि हैमिल्टनियन चक्र है, तो इन किनारों की एक सम संख्या को चुना जाना चाहिए। यदि उनमें से केवल दो को चुना जाता है, तो उनके अंत-शिखरों को दो 5-चक्रों में आसन्न होना चाहिए, जो संभव नहीं है। इसलिए उनमें से 4 को चुना गया है। मान लें कि कर्तन का शीर्ष किनारा नहीं चुना गया है (अन्य सभी स्तिथि समरूपता से समान हैं)। बाहरी चक्र में 5 किनारों में से, दो शीर्ष किनारों को चुना जाना चाहिए, दो तरफ के किनारों को नहीं चुना जाना चाहिए, और इसलिए नीचे के किनारे को चुना जाना चाहिए। आंतरिक चक्र में शीर्ष दो किनारों को चुना जाना चाहिए, लेकिन यह एक गैर-विस्तरित चक्र को पूरा करता है, जो हैमिल्टनियन चक्र का हिस्सा नहीं हो सकता। वैकल्पिक रूप से, हम दस-शीर्ष 3-नियमित लेखाचित्ऱ का भी वर्णन कर सकते हैं जिनमें हैमिल्टनियन चक्र होता है और यह दर्शाता है कि उनमें से कोई भी पीटरसन लेखाचित्ऱ नहीं है, उनमें से प्रत्येक में एक चक्र ढूंढकर जो कि किसी भी चक्र से छोटा पीटरसन लेखाचित्र है। किसी भी दस-शीर्ष वाले हैमिल्टनियन 3-नियमित लेखाचित्ऱ में दस-शीर्ष चक्र C और पाँच जीवाएँ होती हैं। यदि कोई जीवा एक दूसरे से C के साथ दो या तीन दूरी पर दो शीर्षों को जोड़ती है, तो लेखाचित्र में 3-चक्र या 4-चक्र होता है, और इसलिए पीटरसन लेखाचित्र नहीं हो सकता। यदि दो जीवाएँ C के विपरीत शीर्षों को C के साथ चार दूरी पर स्थित शीर्षों से जोड़ती हैं, तो फिर से एक 4-चक्र होता है। एकमात्र शेष स्तिथि एक मोबियस सीढ़ी है जो प्रत्येक जोड़ी के विपरीत कोने को एक जीवा से जोड़कर बनाया जाता है, जिसमें फिर से 4-चक्र होता है। चूंकि पीटरसन लेखाचित्र की परिधि पांच है, इसे इस तरह से नहीं बनाया जा सकता है और इसका कोई हैमिल्टनियन चक्र नहीं है।

रंग

File:PetersenBarveniHran.svg

पीटरसन लेखाचित्र के किनारों का 4-रंग

Error creating thumbnail:

पीटरसन लेखाचित्र के शीर्षों का 3-रंग

पीटरसन लेखाचित्र में रंगीन संख्या 3 है, जिसका अर्थ है कि इसके शिखर तीन रंगों के साथ लेखाचित्र रंग हो सकते हैं - लेकिन दो के साथ नहीं - जैसे कि कोई किनारा एक ही रंग के शिखर को जोड़ता नहीं है। सूची रंगों के लिए ब्रूक्स के प्रमेय द्वारा इसमें 3 रंगों के साथ रंग भरने वाली सूची है।

पीटरसन लेखाचित्र में रंगीन सूचकांक 4 है; किनारों को रंगने के लिए चार रंगों की आवश्यकता होती है। वर्णिक तालिका चार के साथ आनुषंगिक ब्रिजलेस घनाकार लेखाचित्र के रूप में, पीटरसन लेखाचित्र एक स्नार्क (लेखाचित्र सिद्धांत) है। यह सबसे छोटा संभव स्नार्क है, और 1898 से 1946 तक एकमात्र ज्ञात स्नार्क था। स्नार्क (लेखाचित्र सिद्धांत), डब्ल्यूटी टुट्टे द्वारा निराधार कल्पना लगाया गया और 2001 में रॉबर्टसन, सैंडर्स, सेमोर और थॉमस द्वारा घोषित किया गया।^[9] यह बताता है कि हर स्नार्क में पीटरसन लेखाचित्र लघु (लेखाचित्र सिद्धांत) के रूप में होता है।

इसके अतिरिक्त, लेखाचित्र में भिन्नात्मक वर्णिक तालिका 3 है, जो यह साबित करता है कि वर्णसंबंधी तालिका और आंशिक रंगीन सूचकांक के बीच का अंतर 1 जितना बड़ा हो सकता है। लंबे समय से चली आ रही गोल्डबर्ग-सीमोर निराधार कल्पना का प्रस्ताव है कि यह सबसे बड़ा अंतर संभव है।

पीटरसन लेखाचित्र की उभयज संख्या (रंगीन सूचकांक का एक प्रकार) 5 है।

पीटरसन लेखाचित्र को किसी भी (संभवतः अनुचित) रंग में कम से कम तीन रंगों की आवश्यकता होती है जो इसकी सभी समरूपताओं को तोड़ते हैं; अर्थात् इसकी विशिष्ट संख्या तीन है। पूर्ण रेखांकन को छोड़कर, यह एकमात्र केनेसर लेखाचित्र है जिसकी विशिष्ट संख्या दो नहीं है।^[10]

अन्य गुण

पीटरसन लेखाचित्र:

3-आनुषंगिक है और इसलिए 3-छोर-आनुषंगिक और ब्रिजलेस परिधि (लेखाचित्र सिद्धांत) की शब्दावली देखें।
स्वातन्त्र्य संख्या 4 है और 3-पक्षीय है। लेखाचित्र सिद्धांत की शब्दावली देखें।
घनाकार लेखाचित्ऱ है, जिसका वर्चस्व संख्या 3 है, और एक पूर्ण मिलान और 2-कारक है।
में 6 विशिष्ट पूर्ण मिलान हैं।
परिधि का सबसे छोटा घन लेखाचित्र (लेखाचित्र सिद्धांत) 5 है। (यह अद्वितीय $(3,5)$ -उत्थापक (लेखाचित्र सिद्धांत) है। वास्तव में, चूँकि इसमें केवल 10 शीर्ष हैं, यह अद्वितीय $(3,5)$ -मूर लेखाचित्र है।)^[11]
कॉलिन डी वेर्डिएर लेखाचित्र निश्चर μ = 5 के साथ सबसे छोटा घनाकार लेखाचित्र है।^[12]
कॉप संख्या 3 का सबसे छोटा लेखाचित्र है।^[13]
त्रिज्या (लेखाचित्र सिद्धांत) 2 और व्यास (लेखाचित्र सिद्धांत) 2 है। यह व्यास 2 के साथ सबसे बड़ा घन लेखाचित्र है।^{[lower-alpha 2]}
2000 में विस्तरित तरु (गणित) हैं, जो किसी भी 10-कोणबिंदु घनाकार लेखाचित्र का सबसे अधिक है।^[14]^[15]^{[lower-alpha 3]}
रंगीन बहुपद $t(t-1)(t-2)\left(t^{7}-12t^{6}+67t^{5}-230t^{4}+529t^{3}-814t^{2}+775t-352\right)$ है।^[16]
विशेषता बहुपद $(t-1)^{5}(t+2)^{4}(t-3)$ है, इसे एक अभिन्न लेखाचित्र बनाता है - एक लेखाचित्ऱ जिसका वर्णक्रमीय लेखाचित्ऱ सिद्धांत पूरी तरह से पूर्णांकों से बना होता है।

पीटरसन रंग निराधार कल्पना

लेखाचित्र का एक यूलेरियन उपलेखाचित्र $G$ एक उपलेखाचित्र है जिसमें किनारों का एक उपसमुच्चय $G$ होता है, एक समान संख्या में $G$ के हर शीर्ष को छू रहा है। ये उपलेखाचित्र के चक्र स्थान $G$ के तत्व हैं और कभी-कभी चक्र कहलाते हैं। यदि G और H कोई भी दो ग्राफ़ हैं, तो G के किनारों से H के किनारों तक एक फ़ंक्शन को चक्र-निरंतर के रूप में परिभाषित किया जाता है यदि H के प्रत्येक चक्र की पूर्व-छवि G का चक्र है। जैगर का एक निराधार कल्पना यह दावा करता है कि प्रत्येक ब्रिजलेस लेखाचित्र में पीटरसन लेखाचित्र के लिए एक चक्र-निरंतर मानचित्रण होता है। जैगर ने दिखाया कि यह निराधार कल्पना 5-चक्र उभय आवरण निराधार कल्पना और बर्ज-फुलकर्सन निराधार कल्पना का तात्पर्य है।^[17]

↑ As stated, this assumes that Cayley graphs need not be connected. Some sources require Cayley graphs to be connected, making the two-vertex empty graph the smallest vertex-transitive non-Cayley graph; under the definition given by these sources, the Petersen graph is the smallest connected vertex-transitive graph that is not Cayley.
↑ This follows from the fact that it is a Moore graph, since any Moore graph is the largest possible regular graph with its degree and diameter.^[11]
↑ The cubic graphs with 6 and 8 vertices maximizing the number of spanning trees are Möbius ladders.

संदर्भ

↑ Brouwer, Andries E., The Petersen graph
↑ Petersen, Julius (1898), "Sur le théorème de Tait", L'Intermédiaire des Mathématiciens, 5: 225–227
↑ Kempe, A. B. (1886), "A memoir on the theory of mathematical form", Philosophical Transactions of the Royal Society of London, 177: 1–70, doi:10.1098/rstl.1886.0002, S2CID 108716533
↑ Knuth, Donald E., The Art of Computer Programming; volume 4, pre-fascicle 0A. A draft of section 7: Introduction to combinatorial searching
↑ Babai, László (1995), "Automorphism groups, isomorphism, reconstruction", in Graham, Ronald L.; Grötschel, Martin; Lovász, László (eds.), Handbook of Combinatorics, vol. I, North-Holland, pp. 1447–1540, Corollary 1.8, archived from the original on 2010-06-11.
↑ ^6.0 ^6.1 Royle, G. "Cubic Symmetric Graphs (The Foster Census)." Archived 2008-07-20 at the Wayback Machine
↑ Cameron, Peter J. (2004), "Automorphisms of graphs", in Beineke, Lowell W.; Wilson, Robin J. (eds.), Topics in Algebraic Graph Theory, Encyclopedia of Mathematics and its Applications, vol. 102, Cambridge University Press, Cambridge, pp. 135–153, doi:10.1017/CBO9780511529993, ISBN 0-521-80197-4, MR 2125091; see in particular p. 153
↑ Holton, D. A.; Sheehan, J. (1993), The Petersen Graph, Cambridge University Press, p. 32, ISBN 0-521-43594-3
↑ Pegg, Ed, Jr. (2002), "Book Review: The Colossal Book of Mathematics" (PDF), Notices of the American Mathematical Society, 49 (9): 1084–1086, Bibcode:2002ITED...49.1084A, doi:10.1109/TED.2002.1003756{{citation}}: CS1 maint: multiple names: authors list (link)
↑ Albertson, Michael O.; Boutin, Debra L. (2007), "Using determining sets to distinguish Kneser graphs", Electronic Journal of Combinatorics, 14 (1): R20, doi:10.37236/938, MR 2285824.
↑ ^11.0 ^11.1 Hoffman, Alan J.; Singleton, Robert R. (1960), "Moore graphs with diameter 2 and 3" (PDF), IBM Journal of Research and Development, 5 (4): 497–504, doi:10.1147/rd.45.0497, MR 0140437.
↑ László Lovász, Alexander Schrijver (1998), "A Borsuk theorem for antipodal links and a spectral characterization of linklessly embeddable graphs" (PDF), Proceedings of the American Mathematical Society, 126 (5): 1275–1285, doi:10.1090/S0002-9939-98-04244-0
↑ Baird, William; Beveridge, Andrew; Bonato, Anthony; Codenotti, Paolo; Maurer, Aaron; McCauley, John; Valeva, Silviya (2014), "On the minimum order of $k$ [[Category: Templates Vigyan Ready]]-cop-win graphs", Contributions to Discrete Mathematics, 9 (1): 70–84, arXiv:1308.2841, doi:10.11575/cdm.v9i1.62207, MR 3265753 {{citation}}: URL–wikilink conflict (help)
↑ Jakobson, Dmitry; Rivin, Igor (1999), On some extremal problems in graph theory, arXiv:math.CO/9907050
↑ Valdes, L. (1991), "Extremal properties of spanning trees in cubic graphs", Congressus Numerantium, 85: 143–160.
↑ Biggs, Norman (1993), Algebraic Graph Theory (2nd ed.), Cambridge: Cambridge University Press, ISBN 0-521-45897-8
↑ DeVos, Matt; Nešetřil, Jaroslav; Raspaud, André (2007), "On edge-maps whose inverse preserves flows or tensions", Graph theory in Paris, Trends Math., Basel: Birkhäuser, pp. 109–138, doi:10.1007/978-3-7643-7400-6_10, MR 2279171.
↑ Coxeter, H. S. M. (1950), "Self-dual configurations and regular graphs", Bulletin of the American Mathematical Society, 56 (5): 413–455, doi:10.1090/S0002-9904-1950-09407-5.
↑ Watkins, Mark E. (1969), "A Theorem on Tait Colorings with an Application to the Generalized Petersen Graphs", Journal of Combinatorial Theory, 6 (2): 152–164, doi:10.1016/S0021-9800(69)80116-X
↑ Bailey, Rosemary A. (1997), Surveys in Combinatorics, Cambridge University Press, p. 187, ISBN 978-0-521-59840-8

अग्रिम पठन

Exoo, Geoffrey; Harary, Frank; Kabell, Jerald (1981), "कुछ सामान्यीकृत पीटरसन रेखांकन की क्रॉसिंग संख्या", गणित स्कैंडिनेविका, 48: 184–188, doi:10.7146/math.scand.a-11910.
Lovász, László (1993), Combinatorial Problems and Exercises (2nd ed.), North-Holland, ISBN 0-444-81504-X.
Schwenk, A. J. (1989), "Enumeration of Hamiltonian cycles in certain generalized Petersen graphs", Journal of Combinatorial Theory, Series B, 47 (1): 53–59, doi:10.1016/0095-8956(89)90064-6

बाहरी संबंध

[8] As stated, this assumes that Cayley graphs need not be connected. Some sources require Cayley graphs to be connected, making the two-vertex empty graph the smallest vertex-transitive non-Cayley graph; under the definition given by these sources, the Petersen graph is the smallest connected vertex-transitive graph that is not Cayley.

[15] This follows from the fact that it is a Moore graph, since any Moore graph is the largest possible regular graph with its degree and diameter.^[11]

[18] The cubic graphs with 6 and 8 vertices maximizing the number of spanning trees are Möbius ladders.

[1] Brouwer, Andries E., The Petersen graph

[2] Petersen, Julius (1898), "Sur le théorème de Tait", L'Intermédiaire des Mathématiciens, 5: 225–227

[3] Kempe, A. B. (1886), "A memoir on the theory of mathematical form", Philosophical Transactions of the Royal Society of London, 177: 1–70, doi:10.1098/rstl.1886.0002, S2CID 108716533

[4] Knuth, Donald E., The Art of Computer Programming; volume 4, pre-fascicle 0A. A draft of section 7: Introduction to combinatorial searching

[5] Babai, László (1995), "Automorphism groups, isomorphism, reconstruction", in Graham, Ronald L.; Grötschel, Martin; Lovász, László (eds.), Handbook of Combinatorics, vol. I, North-Holland, pp. 1447–1540, Corollary 1.8, archived from the original on 2010-06-11.

[foster-6] 6.0 ^6.1 Royle, G. "Cubic Symmetric Graphs (The Foster Census)." Archived 2008-07-20 at the Wayback Machine

[7] Cameron, Peter J. (2004), "Automorphisms of graphs", in Beineke, Lowell W.; Wilson, Robin J. (eds.), Topics in Algebraic Graph Theory, Encyclopedia of Mathematics and its Applications, vol. 102, Cambridge University Press, Cambridge, pp. 135–153, doi:10.1017/CBO9780511529993, ISBN 0-521-80197-4, MR 2125091; see in particular p. 153

[9] Holton, D. A.; Sheehan, J. (1993), The Petersen Graph, Cambridge University Press, p. 32, ISBN 0-521-43594-3

[10] Pegg, Ed, Jr. (2002), "Book Review: The Colossal Book of Mathematics" (PDF), Notices of the American Mathematical Society, 49 (9): 1084–1086, Bibcode:2002ITED...49.1084A, doi:10.1109/TED.2002.1003756{{citation}}: CS1 maint: multiple names: authors list (link)

[11] Albertson, Michael O.; Boutin, Debra L. (2007), "Using determining sets to distinguish Kneser graphs", Electronic Journal of Combinatorics, 14 (1): R20, doi:10.37236/938, MR 2285824.

[hs60-12] 11.0 ^11.1 Hoffman, Alan J.; Singleton, Robert R. (1960), "Moore graphs with diameter 2 and 3" (PDF), IBM Journal of Research and Development, 5 (4): 497–504, doi:10.1147/rd.45.0497, MR 0140437.

[13] László Lovász, Alexander Schrijver (1998), "A Borsuk theorem for antipodal links and a spectral characterization of linklessly embeddable graphs" (PDF), Proceedings of the American Mathematical Society, 126 (5): 1275–1285, doi:10.1090/S0002-9939-98-04244-0

[14] Baird, William; Beveridge, Andrew; Bonato, Anthony; Codenotti, Paolo; Maurer, Aaron; McCauley, John; Valeva, Silviya (2014), "On the minimum order of $k$ [[Category: Templates Vigyan Ready]]-cop-win graphs", Contributions to Discrete Mathematics, 9 (1): 70–84, arXiv:1308.2841, doi:10.11575/cdm.v9i1.62207, MR 3265753 {{citation}}: URL–wikilink conflict (help)

[16] Jakobson, Dmitry; Rivin, Igor (1999), On some extremal problems in graph theory, arXiv:math.CO/9907050

[17] Valdes, L. (1991), "Extremal properties of spanning trees in cubic graphs", Congressus Numerantium, 85: 143–160.

[biggs-19] Biggs, Norman (1993), Algebraic Graph Theory (2nd ed.), Cambridge: Cambridge University Press, ISBN 0-521-45897-8

[20] DeVos, Matt; Nešetřil, Jaroslav; Raspaud, André (2007), "On edge-maps whose inverse preserves flows or tensions", Graph theory in Paris, Trends Math., Basel: Birkhäuser, pp. 109–138, doi:10.1007/978-3-7643-7400-6_10, MR 2279171.

[21] Coxeter, H. S. M. (1950), "Self-dual configurations and regular graphs", Bulletin of the American Mathematical Society, 56 (5): 413–455, doi:10.1090/S0002-9904-1950-09407-5.

[22] Watkins, Mark E. (1969), "A Theorem on Tait Colorings with an Application to the Generalized Petersen Graphs", Journal of Combinatorial Theory, 6 (2): 152–164, doi:10.1016/S0021-9800(69)80116-X

[Bailey1997-23] Bailey, Rosemary A. (1997), Surveys in Combinatorics, Cambridge University Press, p. 187, ISBN 978-0-521-59840-8

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[lower-alpha 1]

[8]

[9]

[10]

[11]

[12]

[13]

[lower-alpha 2]

[14]

[15]

[lower-alpha 3]

[16]

[17]

[18]

[19]

[20]

Anonymous

Search

पीटरसन ग्राफ

Namespaces

More

Page actions

Contents

निर्माण

अंतःस्थापन

समरूपता

हैमिल्टनियन पथ और चक्र

रंग

अन्य गुण

पीटरसन रंग निराधार कल्पना

संबंधित रेखांकन

टिप्पणियाँ

संदर्भ

अग्रिम पठन

बाहरी संबंध

Navigation

Navigation

Wiki tools

Wiki tools

Anonymous

Search

पीटरसन ग्राफ

निर्माण

अंतःस्थापन

समरूपता

हैमिल्टनियन पथ और चक्र

रंग

अन्य गुण

पीटरसन रंग निराधार कल्पना

संबंधित रेखांकन

टिप्पणियाँ

संदर्भ

अग्रिम पठन

बाहरी संबंध

Navigation

Wiki tools

Page tools

Other projects

Categories