शीर्ष-संक्रमणीय ग्राफ
| Graph families defined by their automorphisms | ||||
|---|---|---|---|---|
| distance-transitive | → | distance-regular | ← | strongly regular |
| ↓ | ||||
| symmetric (arc-transitive) | ← | [[symmetric graph|t-transitive, t ≥ 2]] | skew-symmetric | |
| ↓ | ||||
| (if connected) vertex- and edge-transitive |
→ | edge-transitive and regular | → | edge-transitive |
| ↓ | ↓ | ↓ | ||
| vertex-transitive | → | regular | → | (if bipartite) biregular |
| ↑ | ||||
| Cayley graph | ← | zero-symmetric | asymmetric | |
ग्राफ़ सिद्धांत के गणित क्षेत्र में, एक शीर्ष-संक्रमणीय ग्राफ़ एक ग्राफ़ (असतत गणित) है G जिसमें, कोई भी दो वर्टेक्स (ग्राफ़ सिद्धांत) दिए गए हैं v1 और v2 का G, कुछ ग्राफ ऑटोमोर्फिज्म है
ऐसा है कि
दूसरे शब्दों में, एक ग्राफ़ शीर्ष-संक्रमणीय होता है यदि इसके शीर्षों पर क्रियाओं के ऑटोमोर्फिज़्म समूह समूह क्रिया (गणित) Group_action#क्रियाओं के उल्लेखनीय गुण हों।[1] एक ग्राफ शीर्ष-संक्रमणीय है यदि और केवल यदि इसका ग्राफ पूरक है, क्योंकि समूह क्रियाएं समान हैं।
पृथक शीर्ष के बिना प्रत्येक सममित ग्राफ शीर्ष-संक्रमणीय है, और प्रत्येक शीर्ष-संक्रमणीय ग्राफ नियमित ग्राफ है। हालाँकि, सभी शीर्ष-संक्रमणीय ग्राफ़ सममित नहीं हैं (उदाहरण के लिए, काटे गए टेट्राहेड्रोन के किनारे), और सभी नियमित ग्राफ़ शीर्ष-संक्रमणीय नहीं हैं (उदाहरण के लिए, फल ग्राफ और टिट्ज़ का ग्राफ)।
परिमित उदाहरण
परिमित शीर्ष-संक्रमणीय ग्राफ में सममित ग्राफ (जैसे पीटरसन ग्राफ, हेवुड ग्राफ और प्लेटोनिक ठोस के शीर्ष और किनारे) शामिल हैं। परिमित केली ग्राफ (जैसे घन-जुड़े चक्र) भी शीर्ष-संक्रमणीय हैं, जैसे कि आर्किमिडीयन ठोस के शीर्ष और किनारे हैं (हालांकि इनमें से केवल दो सममित हैं)। पोटोक्निक, स्पिगा और वेरेट ने अधिकतम 1280 शीर्षों पर सभी जुड़े हुए घन शीर्ष-संक्रमणीय ग्राफ़ की जनगणना का निर्माण किया है।[2]
हालाँकि प्रत्येक केली ग्राफ़ शीर्ष-संक्रमणीय है, अन्य शीर्ष-संक्रमणीय ग्राफ़ मौजूद हैं जो केली ग्राफ़ नहीं हैं। सबसे प्रसिद्ध उदाहरण पीटरसन ग्राफ है, लेकिन अन्य का निर्माण किनारे-संक्रमणीय ग्राफ के रेखा ग्राफ सहित किया जा सकता है | समता (गणित) शीर्ष डिग्री के साथ किनारे-संक्रमणीय गैर-द्विपक्षीय ग्राफ ग्राफ।[3]
गुण
कनेक्टिविटी (ग्राफ़ सिद्धांत)|एक शीर्ष-संक्रमणीय ग्राफ़ की किनारे-कनेक्टिविटी नियमित ग्राफ़ डी के बराबर है, जबकि कनेक्टिविटी (ग्राफ़ सिद्धांत)|वर्टेक्स-कनेक्टिविटी कम से कम 2(d + 1)/3 होगी।[1]यदि डिग्री 4 या उससे कम है, या ग्राफ भी किनारे-संक्रमणीय ग्राफ है|किनारे-संक्रमणीय है, या ग्राफ न्यूनतम केली ग्राफ है, तो शीर्ष-कनेक्टिविटी भी डी के बराबर होगी।[4]
अनंत उदाहरण
अनंत शीर्ष-संक्रमणीय ग्राफ़ में शामिल हैं:
- अनंत पथ (ग्राफ़ सिद्धांत) (दोनों दिशाओं में अनंत)
- अनंत नियमित ग्राफ ट्री (ग्राफ सिद्धांत), जैसे। मुक्त समूह का केली ग्राफ़
- समान टाइलिंग के ग्राफ़ (प्लानर चौकोर की एकसमान समतलीय टाइलिंग की सूची देखें), जिसमें नियमित बहुभुजों द्वारा सभी टाइलिंग शामिल हैं
- अनंत केली रेखांकन
- राडो ग्राफ
दो गणनीय शीर्ष-संक्रमणीय ग्राफ़ को रीमैनियन और मीट्रिक ज्यामिति की शब्दावली कहा जाता है#Q|अर्ध-आइसोमेट्रिक यदि उनके दूरी कार्यों का अनुपात नीचे और ऊपर से घिरा हुआ है। एक प्रसिद्ध अनुमान में कहा गया है कि प्रत्येक अनंत शीर्ष-संक्रमणीय ग्राफ केली ग्राफ के लिए अर्ध-आइसोमेट्रिक है। 2001 में :de:रेनहार्ड डिएस्टेल और इमरे नेता द्वारा एक प्रति-उदाहरण प्रस्तावित किया गया था।[5] 2005 में, एस्किन, फिशर और व्हाईट ने प्रतिउदाहरण की पुष्टि की।[6]
यह भी देखें
- एज-ट्रांसिटिव ग्राफ
- लोवेज़ अनुमान
- अर्ध-सममितीय ग्राफ
- शून्य-सममितीय ग्राफ
संदर्भ
- ↑ 1.0 1.1 Godsil, Chris; Royle, Gordon (2013) [2001], Algebraic Graph Theory, Graduate Texts in Mathematics, vol. 207, Springer, ISBN 978-1-4613-0163-9.
- ↑ Potočnik P., Spiga P. & Verret G. (2013), "Cubic vertex-transitive graphs on up to 1280 vertices", Journal of Symbolic Computation, 50: 465–477, arXiv:1201.5317, doi:10.1016/j.jsc.2012.09.002, S2CID 26705221.
- ↑ Lauri, Josef; Scapellato, Raffaele (2003), Topics in graph automorphisms and reconstruction, London Mathematical Society Student Texts, vol. 54, Cambridge University Press, p. 44, ISBN 0-521-82151-7, MR 1971819. Lauri and Scapelleto credit this construction to Mark Watkins.
- ↑ Babai, L. (1996), Technical Report TR-94-10, University of Chicago, archived from the original on 2010-06-11
- ↑ Diestel, Reinhard; Leader, Imre (2001), "A conjecture concerning a limit of non-Cayley graphs" (PDF), Journal of Algebraic Combinatorics, 14 (1): 17–25, doi:10.1023/A:1011257718029, S2CID 10927964.
- ↑ Eskin, Alex; Fisher, David; Whyte, Kevin (2005). "अर्ध-आइसोमेट्री और हल करने योग्य समूहों की कठोरता". arXiv:math.GR/0511647..
बाहरी संबंध
- Weisstein, Eric W. "Vertex-transitive graph". MathWorld.
- A census of small connected cubic vertex-transitive graphs . Primož Potočnik, Pablo Spiga, Gabriel Verret, 2012.
