वर्टेक्स-ट्रांज़िटिविटी और एज स्वैपिंग प्रॉपर्टी

Aug 18 2020

एक सरल, अप्रत्यक्ष ग्राफ $G=(V,E)$कहा जाता है यदि किसी के लिए शीर्ष-सकर्मक है$a,b\in V$ एक ग्राफ isomorphism है $\varphi:V\to V$ ऐसा है कि $\varphi(a) = b$

हम कहते हैं कि एक ग्राफ $G=(V,E)$है धार-गमागमन संपत्ति किसी भी किनारे के लिए करता है, तो$e = \{x,y\} \in E$ एक ग्राफ isomorphism है $\varphi:V\to V$ ऐसा है कि $\varphi(x) = y$ तथा $\varphi(y) = x$

क्या इन गुणों में से कोई भी जुड़े हुए रेखांकन के लिए अन्य का अर्थ है?

जवाब

2 DánielG. Aug 20 2020 at 00:36

जैसा कि एंकिन टिप्पणियों में कहते हैं, जुड़े हुए ग्राफ़ के लिए किनारे-स्वैपिंग संपत्ति का अर्थ है एक मार्ग के साथ किनारे स्वैप की रचना के माध्यम से वर्टेक्स-ट्रांज़िटिविटी।

अन्य निहितार्थ सत्य नहीं है। यदि समीपस्थ कोने की किसी भी जोड़ी के लिए ग्राफ सममित है$(u_1,v_1)$ तथा $(u_2,v_2)$ वहाँ एक automorphism भेज रहा है $u_1$ सेवा मेरे $u_2$ तथा $v_1$ सेवा मेरे $v_2$। ध्यान दें कि यह एज-ट्रांज़िटिविटी से अधिक मजबूत है, क्योंकि हम एज मैप के एंडपॉइंट्स को दूसरे किनारे के एंडपॉइंट्स के लिए निर्दिष्ट कर सकते हैं (इसलिए, इस तरह के ग्राफ को आर्क-ट्रांसेटिव भी कहा जाता है )।

अब विकिपीडिया का दावा है कि ऐसे रेखांकन हैं जो वर्टेक्स-ट्रांसेटिव और एज-ट्रांसेटिव हैं लेकिन सममित नहीं हैं। इस तरह के ग्राफ में एज-स्वैपिंग प्रॉपर्टी नहीं हो सकती है, अन्यथा हम जरूरत पड़ने पर एज-ट्रांसिटिविटी का उपयोग करके और उसके बाद किनारे स्वैप करने के लिए आसन्न कोने की किसी भी जोड़ी को समीपस्थ कोने में भेज सकते हैं।

वर्टेक्स-ट्रांज़िटिविटी, एज-ट्रांज़िटिविटी और एज-स्वैपिंग प्रॉपर्टी के बीच संबंध के बारे में: त्रिकोणीय प्रिज़्म ग्राफ में एज-स्वैपिंग प्रॉपर्टी है और इस तरह यह वर्टेक्स-ट्रांज़िटिव है, लेकिन यह एज-ट्रांज़िटिव नहीं है। मैं एक ग्राफ के बारे में नहीं सोच सकता जो कि शीर्ष-सकर्मक है, लेकिन किनारे-सकर्मक नहीं है और न ही मेरे सिर के ऊपर से किनारे-स्वैपिंग संपत्ति है, हालांकि मुझे आश्चर्य होगा कि अगर ऐसा कोई ग्राफ़ नहीं था।