ग्राफ़ में स्वतंत्र बंधन संख्या गर्थ बाधाओं के तहत

मूल जानकारी

• पेपर ID: 2411.01687
• शीर्षक: Independent Bondage Number in Graphs under Girth Constraints
• लेखक: E.G.K.M. Gamlath, Andrew Pham, Bing Wei
• वर्गीकरण: math.CO (संयोजन गणित)
• प्रकाशन समय: 15 अक्टूबर, 2025 (arXiv प्रीप्रिंट)
• पेपर लिंक: https://arxiv.org/abs/2411.01687

सारांश

परिमित सरल ग्राफ़ $G$ को देखते हुए, ग्राफ़ $G$ की स्वतंत्र बंधन संख्या (independent bondage number) वह न्यूनतम किनारों के समुच्चय का आकार है जिसे हटाने के बाद प्राप्त ग्राफ़ की स्वतंत्र प्रभुत्व संख्या $G$ की स्वतंत्र प्रभुत्व संख्या से कड़ाई से अधिक हो। यद्यपि गर्थ बाधाओं के तहत ग्राफ़ की बंधन संख्या का अध्ययन किया जा चुका है, स्वतंत्र बंधन संख्या के परिणाम अभी भी बहुत कम हैं। यह अनुसंधान दिए गए गर्थ बाधाओं के तहत समतल ग्राफ़ की स्वतंत्र बंधन संख्या के ऊपरी सीमा स्थापित करता है, Fischermann, Rautenbach और Volkmann की बंधन संख्या के परिणामों और Borodin तथा Ivanova के समतल ग्राफ़ संरचना के परिणामों को विस्तारित करता है। विशेष रूप से, $\delta(G) \geq 2$ और $g(G) \geq 5$, $\delta(G) \geq 3$ और $g(G) \geq 4$, तथा $\delta(G) \geq 2$ और $g(G) \geq 10$ को संतुष्ट करने वाले समतल ग्राफ़ की स्वतंत्र बंधन संख्या के लिए अतिरिक्त संरचनाओं की पहचान की गई है और सीमाएं स्थापित की गई हैं।

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

समस्या परिभाषा और महत्व

1. मूल अवधारणाएं:
   • स्वतंत्र प्रभुत्व समुच्चय: शीर्षों का एक समुच्चय जो स्वतंत्र और प्रभुत्वशील दोनों हो
   • स्वतंत्र प्रभुत्व संख्या $\gamma_i(G)$: न्यूनतम स्वतंत्र प्रभुत्व समुच्चय की प्रमुखता
   • स्वतंत्र बंधन संख्या $b_i(G)$: न्यूनतम किनारों के समुच्चय $B$ का आकार जहां $\gamma_i(G-B) > \gamma_i(G)$
2. अनुसंधान का महत्व:
   • किनारों की विफलता की स्थिति में नेटवर्क में स्वतंत्र प्रभुत्व संरचना की कमजोरी को मापता है
   • अंतरसंयोजित नेटवर्क के लिंक विफलता विश्लेषण में महत्वपूर्ण अनुप्रयोग मूल्य
   • शास्त्रीय प्रभुत्व सिद्धांत के अनुसंधान के दायरे को विस्तारित करता है
3. मौजूदा अनुसंधान की सीमाएं:
   • पारंपरिक बंधन संख्या $b(G)$ पर गर्थ बाधाओं के तहत व्यवस्थित अनुसंधान किया जा चुका है
   • स्वतंत्र बंधन संख्या $b_i(G)$ संबंधी परिणाम अत्यंत सीमित हैं, विशेषकर गर्थ बाधा शर्तों के तहत
   • विशिष्ट ग्राफ़ वर्गों के लिए स्थिर ऊपरी सीमा परिणामों की कमी
4. अनुसंधान प्रेरणा:
   • Fischermann आदि (2003) द्वारा समतल ग्राफ़ की बंधन संख्या पर गर्थ बाधा परिणामों से प्रेरित
   • स्वाभाविक रूप से यह अन्वेषण करना कि क्या स्वतंत्र बंधन संख्या भी गर्थ बाधाओं के तहत समान स्थिर ऊपरी सीमा प्राप्त कर सकती है
   • स्वतंत्र बंधन संख्या सिद्धांत अनुसंधान में अंतराल को भरना

मूल योगदान

1. चार मुख्य स्थिर ऊपरी सीमा प्रमेय स्थापित किए:
   • $\delta(G) \geq 3$ और $g(G) \geq 4$ होने पर: $b_i(G) \leq 6$
   • $\delta(G) \geq 2$ और $g(G) \geq 5$ होने पर: $b_i(G) \leq 5$
   • $\delta(G) \geq 2$ और $g(G) \geq 7$ होने पर: $b_i(G) \leq 4$
   • $\delta(G) \geq 2$ और $g(G) \geq 10$ होने पर: $b_i(G) \leq 3$
2. कई महत्वपूर्ण ग्राफ़ संरचना विन्यास की पहचान की:
   • $\delta(G) \geq 2$ और $g(G) \geq 5$ के लिए: 10 अपरिहार्य विन्यास की पहचान
   • $\delta(G) \geq 3$ और $g(G) \geq 4$ के लिए: 3 महत्वपूर्ण विन्यास की पहचान
   • प्रत्येक विन्यास के लिए संबंधित स्वतंत्र बंधन समुच्चय का निर्माण
3. मौजूदा सैद्धांतिक ढांचे को विस्तारित किया:
   • Fischermann आदि के बंधन संख्या परिणामों को स्वतंत्र बंधन संख्या तक सामान्यीकृत किया
   • Borodin और Ivanova के समतल ग्राफ़ संरचना सिद्धांत का उपयोग और विकास किया
4. व्यवस्थित प्रमाण विधि प्रदान की:
   • अपरिहार्य संरचनाओं की पहचान के लिए डिस्चार्जिंग विधि (discharging method) का उपयोग
   • प्रत्येक संरचना के लिए निर्माणात्मक स्वतंत्र बंधन समुच्चय प्रमाण

विधि विवरण

सैद्धांतिक आधार

परिभाषा प्रणाली:

• ग्राफ़ $G$ की स्वतंत्र बंधन संख्या: $b_i(G) = \min\{|B| : B \subseteq E(G), \gamma_i(G-B) > \gamma_i(G)\}$
• गर्थ $g(G)$: ग्राफ़ में सबसे छोटे चक्र की लंबाई
• न्यूनतम डिग्री $\delta(G)$: ग्राफ़ में शीर्षों की न्यूनतम डिग्री

मुख्य लेम्मा:

प्रमेय 1 (Priddy, Wang, Wei): गैर-रिक्त ग्राफ़ G के लिए,
b_i(G) ≤ min{d(u) + d(v) - |N(u) ∩ N(v)| - 1 : uv ∈ E(G)}

मूल विधि: डिस्चार्जिंग तकनीक

डिस्चार्जिंग विधि का सिद्धांत:

1. प्रारंभिक आवेश वितरण: Euler सूत्र के तीन प्राकृतिक तरीकों के अनुसार आवेश वितरित करें
   • शीर्ष आवेश: $d(v) - 6$, फलक आवेश: $2\ell(f) - 6$ (शीर्ष डिस्चार्जिंग)
   • शीर्ष आवेश: $2d(v) - 6$, फलक आवेश: $\ell(f) - 6$ (फलक डिस्चार्जिंग)
   • शीर्ष आवेश: $d(v) - 4$, फलक आवेश: $\ell(f) - 4$ (संतुलित डिस्चार्जिंग)
2. आवेश पुनर्वितरण नियम: सकारात्मक आवेश शीर्षों/फलकों से नकारात्मक आवेश शीर्षों/फलकों की ओर प्रवाह के लिए विशिष्ट नियम डिजाइन करें
3. संरचना पहचान: अंतिम आवेश वितरण के विश्लेषण के माध्यम से कुछ संरचनाओं की अपरिहार्यता सिद्ध करें

विशिष्ट कार्यान्वयन रणनीति

$\delta(G) \geq 2$ और $g(G) \geq 5$ के मामले के लिए:

डिस्चार्जिंग नियम:

• (R1) प्रत्येक 2-डिग्री शीर्ष प्रत्येक आसन्न शीर्ष और प्रत्येक संबंधित फलक से $\frac{1}{2}$ आवेश लेता है
• (R2) प्रत्येक 3-डिग्री शीर्ष प्रत्येक संबंधित फलक से $\frac{1}{3}$ आवेश लेता है
• (R3) विशिष्ट 6-डिग्री शीर्षों का आवेश वितरण नियम
• (R4) विशिष्ट 5-डिग्री शीर्षों का आवेश वितरण नियम

मुख्य तथ्य सत्यापन:

• तथ्य 1: प्रत्येक डिग्री ≤ 4 के शीर्ष का अंतिम आवेश 0 है
• तथ्य 2: 5+ डिग्री शीर्षों के आवेश वितरण की पारस्परिक एकीकरणीयता
• तथ्य 3-8: विभिन्न शीर्षों और फलकों के गैर-नकारात्मक आवेश की गारंटी

मुख्य परिणाम

प्रमेय 7: $\delta(G) \geq 2$ और $g(G) \geq 5$ की संरचना विशेषता

प्रत्येक शर्तों को संतुष्ट करने वाले समतल ग्राफ़ $G$ में निम्नलिखित विन्यासों में से एक अवश्य होना चाहिए:

• (a) $(2,4^-)$ किनारा या $(3,3^-)$ किनारा
• (b) शीर्ष $v \in S(5^+, [d(v)-1]^+)$ और इसके शेष पड़ोसी 4-डिग्री शीर्ष या $S(5^+,1^+)$ में शीर्ष हों
• (c)-(j) आठ जटिल विन्यास जिनमें 5-डिग्री शीर्ष और 2-डिग्री पड़ोसी 5-फलक साझा करते हैं

प्रमेय 8: स्वतंत्र बंधन संख्या ऊपरी सीमा

$\delta(G) \geq 2$ और $g(G) \geq 5$ के समतल ग्राफ़ $G$ के लिए: $b_i(G) \leq 5$

प्रमाण दृष्टिकोण:

1. प्रत्येक विन्यास के लिए आकार ≤ 5 के किनारों के समुच्चय $B$ का निर्माण करें
2. सिद्ध करें कि $B$ को हटाने के बाद स्वतंत्र प्रभुत्व संख्या कड़ाई से बढ़ती है
3. विरोधाभास विधि और स्वतंत्र प्रभुत्व समुच्चय के गुणों का उपयोग करें

अन्य मुख्य परिणाम

प्रमेय 10: $\delta(G) \geq 3$ और $g(G) \geq 4$ ⟹ $b_i(G) \leq 6$

परिणाम 1: $\delta(G) \geq 2$ और $g(G) \geq 7$ ⟹ $b_i(G) \leq 4$ (Cranston-West लेम्मा पर आधारित)

प्रमेय 13: $\delta(G) \geq 2$ और $g(G) \geq 10$ ⟹ $b_i(G) \leq 3$

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

पद्धति संबंधी नवाचार

1. स्वतंत्र बंधन संख्या अनुसंधान में पहली बार डिस्चार्जिंग विधि का व्यवस्थित अनुप्रयोग
2. नई आवेश वितरण रणनीति का विकास: स्वतंत्र बंधन संख्या की विशेष विशेषताओं के लिए डिजाइन किया गया
3. संरचना पहचान और बंधन समुच्चय निर्माण का संपूर्ण ढांचा स्थापित किया

सैद्धांतिक योगदान

1. शास्त्रीय परिणामों का विस्तार: बंधन संख्या से स्वतंत्र बंधन संख्या तक सामान्यीकरण
2. सैद्धांतिक अंतराल को भरना: गर्थ बाधाओं के तहत स्वतंत्र बंधन संख्या के पहले व्यवस्थित परिणाम प्रदान करना
3. नई ग्राफ़ संरचनाओं की पहचान: स्वतंत्र बंधन संख्या को प्रभावित करने वाली मुख्य विन्यास की खोज

प्रमाण तकनीकें

1. सूक्ष्म आवेश विश्लेषण: विस्तृत तथ्य सत्यापन के माध्यम से डिस्चार्जिंग प्रक्रिया की सही्ता सुनिश्चित करना
2. निर्माणात्मक प्रमाण: प्रत्येक विन्यास के लिए स्पष्ट रूप से स्वतंत्र बंधन समुच्चय का निर्माण
3. केस विश्लेषण की पूर्णता: सभी संभावित संरचना विन्यासों का विस्तृत विश्लेषण

संबंधित कार्य

ऐतिहासिक विकास

1. 1979: Garey और Johnson ने प्रभुत्व संख्या समस्या की NP पूर्णता सिद्ध की
2. 1983: Bauer आदि ने प्रभुत्व रेखा स्थिरता की अवधारणा प्रस्तुत की
3. 1990: Fink आदि ने औपचारिक रूप से बंधन संख्या को परिभाषित किया
4. 2003: Fischermann आदि ने गर्थ बाधाओं के तहत बंधन संख्या ऊपरी सीमा स्थापित की

स्वतंत्र बंधन संख्या अनुसंधान

1. 2018: Priddy, Wang, Wei ने पहली बार स्वतंत्र बंधन संख्या का व्यवस्थित अध्ययन किया
2. 2021: Pham और Wei ने $\delta(G) \geq 3$ समतल ग्राफ़ के लिए स्थिर ऊपरी सीमा स्थापित की
3. यह पेपर: गर्थ बाधाओं के तहत स्वतंत्र बंधन संख्या का पहला अध्ययन

तकनीकी विधि तुलना

• पारंपरिक विधि: मुख्य रूप से डिग्री बाधाओं और स्थानीय संरचना विश्लेषण पर आधारित
• यह पेपर की विधि: गर्थ बाधाओं और डिस्चार्जिंग तकनीक को जोड़ते हुए, अधिक सूक्ष्म संरचना विशेषता प्रदान करता है

निष्कर्ष और चर्चा

मुख्य निष्कर्ष

समतल ग्राफ़ की स्वतंत्र बंधन संख्या के लिए गर्थ बाधाओं के तहत एक संपूर्ण ऊपरी सीमा प्रणाली स्थापित की गई: