शीर्ष-संक्रमणीय ग्राफ: Difference between revisions
(Created page with "{{Short description|Graph where all pairs of vertices are automorphic}} {{Graph families defined by their automorphisms}} ग्राफ़ सिद्धांत के...") |
No edit summary |
||
| Line 2: | Line 2: | ||
{{Graph families defined by their automorphisms}} | {{Graph families defined by their automorphisms}} | ||
ग्राफ़ सिद्धांत के | |||
ग्राफ़ सिद्धांत के गणितीय क्षेत्र में, एक शीर्ष-संक्रमणीय ग्राफ़ एक ग्राफ़ {{mvar|G}} है जिसमें, {{mvar|G}} के किन्हीं दो शीर्षों {{math|''v''{{sub|1}}}} और {{math|''v''{{sub|2}}}} को देखते हुए, कुछ स्वचालितता होती है | |||
:<math>f : G \to G\ </math> | :<math>f : G \to G\ </math> | ||
| Line 8: | Line 9: | ||
:<math>f(v_1) = v_2.\ </math> | :<math>f(v_1) = v_2.\ </math> | ||
दूसरे शब्दों में, एक | दूसरे शब्दों में, एक ग्राफ शीर्ष-संक्रमणीय होता है यदि इसका ऑटोमोर्फिज्म समूह इसके शीर्षों पर संक्रमणीय रूप से कार्य करता है।<ref name="Godsil01">{{citation|first1=Chris|last1=Godsil|authorlink1=Chris Godsil|first2=Gordon|last2=Royle|authorlink2=Gordon Royle|title=Algebraic Graph Theory|series=[[Graduate Texts in Mathematics]]|volume=207|publisher=Springer |orig-year=2001 |isbn=978-1-4613-0163-9 |year=2013|url=https://books.google.com/books?id=GeSPBAAAQBAJ }}.</ref> एक ग्राफ शीर्ष-संक्रमणीय है यदि और केवल यदि इसका ग्राफ पूरक है, क्योंकि समूह क्रियाएं समान हैं। | ||
पृथक शीर्षों के बिना प्रत्येक सममित ग्राफ शीर्ष-संक्रमणीय है, और प्रत्येक शीर्ष-संक्रमणीय ग्राफ नियमित है। चूँकि , सभी शीर्ष-संक्रमणीय ग्राफ़ सममित नहीं हैं (उदाहरण के लिए, ट्रंकेटेड टेट्राहेड्रोन के किनारे), और सभी नियमित ग्राफ़ शीर्ष-संक्रमणीय नहीं हैं (उदाहरण के लिए, फ्रुचट ग्राफ और टिट्ज़ का ग्राफ)। | |||
== परिमित उदाहरण == | == परिमित उदाहरण == | ||
[[File:Tuncated tetrahedral graph.png|thumb|right|220px|काटे गए टेट्राहेड्रोन के किनारे एक शीर्ष-संक्रमणीय ग्राफ (एक [[केली ग्राफ]] भी) बनाते हैं जो सममित ग्राफ नहीं है।]] | [[File:Tuncated tetrahedral graph.png|thumb|right|220px|काटे गए टेट्राहेड्रोन के किनारे एक शीर्ष-संक्रमणीय ग्राफ (एक [[केली ग्राफ]] भी) बनाते हैं जो सममित ग्राफ नहीं है।]]प'''रिमित शीर्ष-संक्रमणीय ग्राफ में स'''ममित ग्राफ (जैसे [[पीटरसन ग्राफ]], [[हेवुड ग्राफ]] और [[प्लेटोनिक ठोस]] के शीर्ष और किनारे) शामिल हैं। परिमित केली ग्राफ (जैसे [[घन-जुड़े चक्र]]) भी शीर्ष-संक्रमणीय हैं, जैसे कि [[आर्किमिडीयन ठोस]] के शीर्ष और किनारे हैं (हालांकि इनमें से केवल दो सममित हैं)। पोटोक्निक, स्पिगा और वेरेट ने अधिकतम 1280 शीर्षों पर सभी जुड़े हुए घन शीर्ष-संक्रमणीय ग्राफ़ की जनगणना का निर्माण किया है।<ref>{{citation|title=Cubic vertex-transitive graphs on up to 1280 vertices|author1=Potočnik P., Spiga P. |author2=Verret G. |name-list-style=amp |journal=Journal of Symbolic Computation |volume = 50 | year = 2013|pages = 465–477|doi=10.1016/j.jsc.2012.09.002|arxiv=1201.5317|s2cid=26705221 }}.</ref> | ||
चूँकि प्रत्येक केली ग्राफ़ शीर्ष-संक्रमणीय है, अन्य शीर्ष-संक्रमणीय ग्राफ़ मौजूद हैं जो केली ग्राफ़ नहीं हैं। सबसे प्रसिद्ध उदाहरण पीटरसन ग्राफ है, लेकिन अन्य का निर्माण किनारे-संक्रमणीय ग्राफ के रेखा ग्राफ सहित किया जा सकता है | [[समता (गणित)]] शीर्ष डिग्री के साथ किनारे-संक्रमणीय गैर-द्विपक्षीय ग्राफ ग्राफ।<ref>{{citation | |||
| last1 = Lauri | first1 = Josef | | last1 = Lauri | first1 = Josef | ||
| last2 = Scapellato | first2 = Raffaele | | last2 = Scapellato | first2 = Raffaele | ||
Revision as of 12:02, 12 August 2023
| 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 है जिसमें, G के किन्हीं दो शीर्षों v1 और v2 को देखते हुए, कुछ स्वचालितता होती है
ऐसा है कि
दूसरे शब्दों में, एक ग्राफ शीर्ष-संक्रमणीय होता है यदि इसका ऑटोमोर्फिज्म समूह इसके शीर्षों पर संक्रमणीय रूप से कार्य करता है।[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.
