View source for शीर्ष-संक्रमणीय ग्राफ

{{Short description|Graph where all pairs of vertices are automorphic}}
{{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(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|काटे गए टेट्राहेड्रोन के किनारे एक शीर्ष-संक्रमणीय ग्राफ (एक [[केली ग्राफ]] भी) बनाते हैं जो सममित ग्राफ नहीं है।]]परिमित शीर्ष-संक्रमणीय ग्राफ में सममित ग्राफ (जैसे [[पीटरसन ग्राफ]], [[हेवुड ग्राफ]] और [[प्लेटोनिक ठोस]] के शीर्ष और किनारे) सम्मिलित हैं। परिमित केली ग्राफ (जैसे [[घन-जुड़े चक्र]]) भी शीर्ष-संक्रमणीय हैं, जैसे कि [[आर्किमिडीयन ठोस]] के शीर्ष और किनारे हैं (चूँकि इनमें से केवल दो सममित हैं)। पोटोक्निक, स्पिगा और वेरेट ने अधिकतम 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
 | last2 = Scapellato | first2 = Raffaele
 | isbn = 0-521-82151-7
 | mr = 1971819
 | page = 44
 | publisher = Cambridge University Press
 | series = London Mathematical Society Student Texts
 | title = Topics in graph automorphisms and reconstruction
 | url = https://books.google.com/books?id=hsymFm0E0uIC&pg=PA44
 | volume = 54
 | year = 2003}}. Lauri and Scapelleto credit this construction to Mark Watkins.</ref>
== गुण ==
कनेक्टिविटी (ग्राफ़ सिद्धांत) या एक शीर्ष-संक्रमणीय ग्राफ़ की एज -कनेक्टिविटी नियमित ग्राफ़ ''d'' के समान है, जबकि कनेक्टिविटी (ग्राफ़ सिद्धांत) या वर्टेक्स-कनेक्टिविटी कम से कम 2(d + 1)/3 होगी।<ref name=Godsil01/> यदि डिग्री 4 या उससे कम है, या ग्राफ भी किनारे-संक्रमणीय ग्राफ है| जिसके किनारे-संक्रमणीय है, या ग्राफ न्यूनतम केली ग्राफ है, तो शीर्ष-कनेक्टिविटी भी ''d'' के समान होगी।<ref>{{Citation|title=Technical Report TR-94-10|author=Babai, L.|year=1996|publisher=University of Chicago |url=http://www.cs.uchicago.edu/files/tr_authentic/TR-94-10.ps |archive-url=https://web.archive.org/web/20100611212234/http://www.cs.uchicago.edu/files/tr_authentic/TR-94-10.ps |archive-date=2010-06-11 }}</ref>


== अनंत उदाहरण ==
अनंत शीर्ष-संक्रमणीय ग्राफ़ में सम्मिलित हैं:
* अनंत पथ (ग्राफ़ सिद्धांत) (दोनों दिशाओं में अनंत)
* अनंत नियमित ग्राफ ट्री (ग्राफ सिद्धांत), जैसे। [[मुक्त समूह]] का केली ग्राफ़
* समान टाइलिंग के ग्राफ़ (प्लानर [[चौकोर|टेस्सेलेशन]] की एकसमान समतलीय टाइलिंग की सूची देखें), जिसमें नियमित बहुभुजों द्वारा सभी टाइलिंग सम्मिलित हैं
* अनंत केली ग्राफ 
*[[राडो ग्राफ]]
दो गणनीय शीर्ष-संक्रमणीय ग्राफ़ को अर्ध-आइसोमेट्रिक कहा जाता है यदि उनके दूरी कार्यों का अनुपात नीचे और ऊपर से घिरा हुआ है। एक प्रसिद्ध अनुमान में कहा गया है कि प्रत्येक अनंत शीर्ष-संक्रमणीय ग्राफ केली ग्राफ के लिए अर्ध-आइसोमेट्रिक है। 2001 में डिएस्टेल और लीडर द्वारा एक प्रति-उदाहरण प्रस्तावित किया गया था।<ref>{{citation|first1=Reinhard|last1=Diestel|first2=Imre|last2=Leader|authorlink2=Imre Leader|url=http://www.math.uni-hamburg.de/home/diestel/papers/Cayley.pdf|title=A conjecture concerning a limit of non-Cayley graphs|journal=Journal of Algebraic Combinatorics|volume=14|issue=1|year=2001|pages=17–25|doi=10.1023/A:1011257718029|s2cid=10927964|doi-access=free}}.</ref> 2005 में, एस्किन, फिशर और व्हाईट ने प्रतिउदाहरण की पुष्टि की थी।<ref>{{cite arXiv|first1=Alex|last1=Eskin|first2=David|last2=Fisher|first3=Kevin|last3=Whyte|eprint=math.GR/0511647 |title=अर्ध-आइसोमेट्री और हल करने योग्य समूहों की कठोरता|year=2005}}.</ref>
== यह भी देखें ==
* एज-ट्रांसिटिव ग्राफ
* लोवेज़ अनुमान
* [[अर्ध-सममितीय ग्राफ]]
* [[शून्य-सममितीय ग्राफ]]

== संदर्भ ==
<references/>


== बाहरी संबंध ==
* {{MathWorld | urlname=Vertex-TransitiveGraph | title=Vertex-transitive graph }}
*[http://www.matapp.unimib.it/~spiga/census.html A census of small connected cubic vertex-transitive graphs ]. Primož Potočnik, Pablo Spiga, Gabriel Verret, 2012.
[[Category: ग्राफ़ परिवार]] [[Category: बीजगणितीय ग्राफ सिद्धांत]] [[Category: नियमित रेखांकन]] 



[[Category: Machine Translated Page]]
[[Category:Created On 09/08/2023]]
[[Category:Vigyan Ready]]