समतलीय जीवा चक्रों से उत्पन्न घूर्णनात्मक रूप से सममित समतलीय ग्राफों का स्थानीय भिन्नात्मक मीट्रिक आयाम

मूल जानकारी

• पेपर ID: 2105.07808
• शीर्षक: समतलीय जीवा चक्रों से उत्पन्न घूर्णनात्मक रूप से सममित समतलीय ग्राफों का स्थानीय भिन्नात्मक मीट्रिक आयाम
• लेखक: शाहबाज़ अली, राउल एम. फाल्कॉन, मुहम्मद खालिद महमूद
• वर्गीकरण: math.CO (संयोजन गणित)
• प्रकाशन समय: 17 मई 2021 (arXiv प्रीप्रिंट)
• पेपर लिंक: https://arxiv.org/abs/2105.07808

सारांश

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

अनुसंधान पृष्ठभूमि और प्रेरणा

समस्या की पृष्ठभूमि

1. मीट्रिक आयाम समस्या की उत्पत्ति: 1970 के दशक में स्लेटर और हरारी और मेल्टर द्वारा स्वतंत्र रूप से प्रस्तुत, जिसका उद्देश्य ग्राफ में दूरी सदिश द्वारा विशिष्ट रूप से प्रतिनिधित्व किए जा सकने वाले शीर्षों की न्यूनतम संख्या निर्धारित करना है
2. समस्या की जटिलता: मीट्रिक आयाम समस्या NP-कठिन है, लेकिन विभिन्न प्रकार के ग्राफों के लिए स्पष्ट समाधान प्राप्त किए गए हैं
3. व्यावहारिक अनुप्रयोग मूल्य: रोबोटिक नेविगेशन, पैटर्न मान्यता, छवि प्रसंस्करण, रासायनिक यौगिक प्रतिनिधित्व, संयोजन अनुकूलन और नेटवर्क जैसे क्षेत्रों में महत्वपूर्ण अनुप्रयोग

अनुसंधान प्रेरणा

1. सैद्धांतिक आवश्यकता: इमरान और अन्य विद्वानों द्वारा स्थिर मीट्रिक आयाम वाले (घूर्णनात्मक रूप से सममित) समतलीय ग्राफों के परिवारों को चिन्हित करने की समस्या प्रस्तुत की गई
2. तकनीकी विकास: 2000 में चार्टरैंड और अन्य द्वारा मीट्रिक आयाम समस्या को पूर्णांक प्रोग्रामिंग के रूप में तैयार किया गया, बाद में कर्री और ओएलरमैन द्वारा रैखिक प्रोग्रामिंग शिथिलीकरण प्रस्तावित किया गया, जिससे भिन्नात्मक मीट्रिक आयाम की अवधारणा प्रस्तुत की गई
3. स्थानीयकृत अनुसंधान: 2018 में बेनिश और अन्य द्वारा केवल आसन्न शीर्षों से संबंधित स्थानीय भिन्नात्मक मीट्रिक आयाम की अवधारणा प्रस्तुत की गई, यह अनुसंधान क्षेत्र अभी भी प्रारंभिक चरण में है

मौजूदा विधियों की सीमाएँ

1. स्थानीय भिन्नात्मक मीट्रिक आयाम का अनुसंधान बहुत सीमित है, केवल कुछ ग्राफ प्रकारों के लिए स्पष्ट परिणाम हैं
2. लियू और अन्य के हाल के काम में तकनीकी त्रुटियाँ हैं, जिन्हें व्यापक रूप से पुनः विश्लेषण की आवश्यकता है
3. उच्च क्रम जीवा चक्र निर्माण ग्राफों के व्यवस्थित अनुसंधान की कमी है

मुख्य योगदान

1. नया ग्राफ परिवार निर्माण: समतलीय जीवा चक्रों के किनारे-विलय के आधार पर घूर्णनात्मक रूप से सममित समतलीय ग्राफों के नए परिवार $G_m(G)$ का वर्णन
2. आयाम गणना: क्रम $n ≤ 6$ के समतलीय जीवा चक्रों से उत्पन्न सभी घूर्णनात्मक रूप से सममित समतलीय ग्राफों का स्थानीय भिन्नात्मक मीट्रिक आयाम स्थापित किया
3. स्पर्शोन्मुख विश्लेषण: इन ग्राफ परिवारों के स्थानीय भिन्नात्मक मीट्रिक आयाम का स्पर्शोन्मुख व्यवहार विश्लेषण प्रदान किया
4. सैद्धांतिक सुधार: साहित्य में पहिया ग्राफों के स्थानीय भिन्नात्मक मीट्रिक आयाम के गलत परिणामों को सुधारा
5. वर्गीकरण पूर्णता: चतुर्भुज, पंचभुज और षट्भुज जीवा चक्रों के सभी गैर-समरूप मामलों का व्यापक विश्लेषण

विधि विवरण

कार्य परिभाषा

घूर्णनात्मक रूप से सममित समतलीय ग्राफ $G_m(G)$ के स्थानीय भिन्नात्मक मीट्रिक आयाम का अनुसंधान, जहाँ $G$ क्रम $n$ का समतलीय जीवा चक्र है, $m ≥ 2$ प्रतियों की संख्या है।

ग्राफ निर्माण विधि

समतलीय जीवा चक्र $G$ की $m$ असंयुक्त प्रतियों $G_1, G_2, ..., G_m$ को देखते हुए, निम्नलिखित अनुक्रमिक किनारे-विलय के माध्यम से $G_m(G)$ का निर्माण किया जाता है:

1. $G_1(G) := G_1 \cdot G_2(v_2^1v_3^1, v_{n-1}^2v_n^2 : v_{n-1}^2v_n^2)$
2. $G_k(G) := G_{k-1}(G) \cdot G_{k+1}(v_2^kv_3^k, v_{n-1}^{k+1}v_n^{k+1} : v_{n-1}^{k+1}v_n^{k+1})$, $k \in \{2,...,m-1\}$ के लिए
3. $G_m(G) := G_{m-1}(G) \cdot G_m(v_2^mv_3^m, v_{n-1}^1v_n^1 : v_{n-1}^1v_n^1)$

परिणामी ग्राफ $G_m(G)$ क्रम $m \cdot (n-2)$ का घूर्णनात्मक रूप से सममित समतलीय ग्राफ है।

मुख्य अवधारणा परिभाषाएँ

स्थानीय भिन्नात्मक मीट्रिक आयाम

ग्राफ $G$ के लिए, स्थानीय भिन्नात्मक मीट्रिक आयाम को इस प्रकार परिभाषित किया जाता है: $\text{ldim}_f(G) := \min\left\{\sum_{v \in V(G)} \vartheta(v) : \vartheta \text{ } G \text{ का स्थानीय विश्लेषणात्मक फलन है}\right\}$

जहाँ स्थानीय विश्लेषणात्मक फलन $\vartheta: V(G) \to [0,1]$ निम्नलिखित को संतुष्ट करता है: $\sum_{u \in R\{v,w\}} \vartheta(u) \geq 1$ सभी आसन्न शीर्ष युग्मों $vw \in E(G)$ के लिए।

मुख्य लेम्मा

लेम्मा 2.1: क्रम $n ≥ 2$ के परिमित संयुक्त ग्राफ $G$ के लिए:

• $\text{ldim}_f(G) \leq \text{dim}_f(G)$
• $\frac{n}{n - \text{ldim}(G) + 1} \leq \text{ldim}_f(G) \leq \frac{n}{\ell(G)} \leq \frac{n}{2}$
• $\text{ldim}_f(G) = 1$ यदि और केवल यदि $G$ द्विपक्षीय है
• $\text{ldim}_f(G) = \frac{n}{2}$ यदि और केवल यदि $V(G)$ में प्रत्येक शीर्ष का वास्तविक जुड़वाँ शीर्ष है

तकनीकी नवाचार बिंदु

1. व्यवस्थित विश्लेषण: पहली बार सभी क्रम छः तक के समतलीय जीवा चक्रों से निर्मित घूर्णनात्मक रूप से सममित ग्राफों का पूर्ण विश्लेषण
2. गणना विधि: रैखिक प्रोग्रामिंग के माध्यम से स्थानीय भिन्नात्मक मीट्रिक आयाम के सटीक मान या ऊपरी सीमा का समाधान
3. स्पर्शोन्मुख विश्लेषण: विभिन्न ग्राफ परिवारों के स्थानीय भिन्नात्मक मीट्रिक आयाम के स्पर्शोन्मुख व्यवहार पैटर्न स्थापित किए
4. त्रुटि सुधार: साहित्य 2 में पहिया ग्राफों के स्थानीय भिन्नात्मक मीट्रिक आयाम के गलत परिणामों को सुधारा

प्रायोगिक सेटअप

ग्राफ वर्ग विश्लेषण

पेपर निम्नलिखित ग्राफ वर्गों का विश्लेषण करता है:

• चतुर्भुज जीवा चक्र: Q₁, Q₂ (2 प्रकार)
• पंचभुज जीवा चक्र: P₁ से P₆ (6 प्रकार)
• षट्भुज जीवा चक्र: H₁ से H₁₇ (17 प्रकार)

गणना विधि

1. रैखिक प्रोग्रामिंग: प्रत्येक ग्राफ वर्ग के लिए संबंधित रैखिक प्रोग्रामिंग समस्या का निर्माण
2. सममितता का उपयोग: ग्राफ की घूर्णनात्मक सममितता का उपयोग करके गणना को सरल बनाया
3. विश्लेषणात्मक पड़ोस विश्लेषण: महत्वपूर्ण किनारे युग्मों के विश्लेषणात्मक पड़ोस आकार $|R\{v,w\}|$ की गणना

मूल्यांकन संकेतक

• स्थानीय भिन्नात्मक मीट्रिक आयाम के सटीक मान
• स्पर्शोन्मुख ऊपरी सीमाएँ
• सैद्धांतिक निचली सीमा के साथ तुलना

प्रायोगिक परिणाम

मुख्य परिणाम

चतुर्भुज स्थिति

प्रस्ताव 3.1: $m ≥ 2$ के लिए:

• $\text{ldim}_f(G_m(Q_1)) = \begin{cases} \frac{3}{2}, & \text{यदि } m = 2 \\ \frac{m}{2}, & \text{अन्यथा} \end{cases}$
• $\text{ldim}_f(G_m(Q_2)) = \begin{cases} \frac{3}{2}, & \text{यदि } m \leq 4 \\ \frac{m}{4}, & \text{अन्यथा} \end{cases}$

पंचभुज स्थिति

प्रमेय 4.1: सभी पंचभुज जीवा चक्रों $P_1$ से $P_6$ के निर्मित ग्राफों के स्थानीय भिन्नात्मक मीट्रिक आयाम की ऊपरी सीमाएँ स्थापित की गई हैं, उदाहरण के लिए:

• $\text{ldim}_f(G_m(P_2)) \leq \begin{cases} \frac{2m}{m+1}, & \text{यदि } m \text{ विषम है} \\ \frac{6m}{3m+2}, & \text{अन्यथा} \end{cases}$

षट्भुज स्थिति

प्रमेय 4.2: षट्भुज जीवा चक्रों $H_1$ से $H_{17}$ के लिए:

• $\text{ldim}_f(G_m(H_1)) = \text{ldim}_f(G_m(H_2)) = 1$ (द्विपक्षीय ग्राफ)
• अन्य मामलों में संबंधित ऊपरी सीमा सूत्र दिए गए हैं

पहिया ग्राफ सुधार परिणाम

लेम्मा 3.1: क्रम $n ≥ 4$ के पहिया ग्राफ $W_n$ के लिए: