2025-11-16T18:28:12.845274

On open-separating dominating codes in graphs

Chakraborty, Wagler
Using dominating sets to separate vertices of graphs is a well-studied problem in the larger domain of identification problems. In such problems, the objective is to choose a suitable dominating set $C$ of a graph $G$ which is also separating in the sense that the neighbourhoods of any two distinct vertices of $G$ have distinct intersections with $C$. Such a dominating and separating set $C$ of a graph is often referred to as a code in the literature. Depending on the types of dominating and separating sets used, various problems arise under various names in the literature. In this paper, we introduce a new problem in the same realm of identification problems whereby the code, called open-separating dominating code, or OD-code for short, is a dominating set and uses open neighbourhoods for separating vertices. The paper studies the fundamental properties concerning the existence, hardness and minimality of OD-codes. Due to the emergence of a close and yet difficult to establish relation of the OD-code with another well-studied code in the literature called open (neighborhood)-locating dominating code (referred to as the open-separating total-dominating code and abbreviated as OTD-code in this paper), we compare the two codes on various graph families. Finally, we also provide an equivalent reformulation of the problem of finding OD-codes of a graph as a covering problem in a suitable hypergraph and discuss the polyhedra associated with OD-codes, again in relation to OTD-codes of some graph families already studied in this context.
academic

ग्राफ़ में खुले-अलग करने वाले प्रभावशाली कोड पर

मूल जानकारी

  • पेपर ID: 2402.03015
  • शीर्षक: ग्राफ़ में खुले-अलग करने वाले प्रभावशाली कोड पर
  • लेखक: Dipayan Chakraborty, Annegret K. Wagler
  • वर्गीकरण: math.CO (संयोजन गणित), cs.DM (असतत गणित)
  • प्रकाशन समय: 5 फरवरी 2024 (arXiv प्रीप्रिंट)
  • पेपर लिंक: https://arxiv.org/abs/2402.03015

सारांश

यह पेपर ग्राफ़ की पहचान समस्या के क्षेत्र में एक नई समस्या - खुले पड़ोस अलग करने वाले प्रभावशाली कोड (OD-code) का परिचय देता है। यह समस्या एक शीर्ष उपसमुच्चय का चयन करने की मांग करती है जो एक प्रभावशाली समुच्चय और अलग करने वाली संपत्ति दोनों है, जिससे किन्हीं दो भिन्न शीर्षों के खुले पड़ोस का इस उपसमुच्चय के साथ प्रतिच्छेदन भिन्न हो। पेपर OD-कोड की अस्तित्व, कम्प्यूटेशनल जटिलता और न्यूनतमता जैसी मूलभूत संपत्तियों का व्यवस्थित रूप से अध्ययन करता है, और मौजूदा खुले पड़ोस स्थानीयकरण प्रभावशाली कोड (OTD-code) के साथ गहन तुलना करता है। इसके अलावा, पेपर OD-कोड समस्या को हाइपरग्राफ़ कवरिंग समस्या के रूप में पुनर्निर्मित करता है और संबंधित बहुफलकीय संरचनाओं पर चर्चा करता है।

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

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

  1. पहचान समस्या का महत्व: ग्राफ़ सिद्धांत में, प्रभावशाली समुच्चय का उपयोग करके शीर्षों को अलग करना पहचान समस्या के क्षेत्र में एक शास्त्रीय अनुसंधान दिशा है, जिसके व्यापक व्यावहारिक अनुप्रयोग हैं, जैसे बहु-प्रोसेसर नेटवर्क में दोष पहचान, सेंसर नेटवर्क में घुसपैठिए की स्थिति निर्धारण आदि।
  2. मौजूदा कोड प्रकारों की सीमाएं: साहित्य में कई कोड संयोजन पहले से मौजूद हैं, जिनमें शामिल हैं:
    • पहचान कोड (ID-codes): बंद पड़ोस अलग करना + प्रभाव
    • स्थानीयकरण प्रभावशाली कोड (LD-codes): स्थानीयकरण + प्रभाव
    • खुले पड़ोस अलग करने वाले पूर्ण प्रभावशाली कोड (OTD-codes): खुले पड़ोस अलग करना + पूर्ण प्रभाव
  3. अनुसंधान अंतराल: खुले पड़ोस अलग करने और सामान्य प्रभाव का संयोजन (OD-code) पहले व्यवस्थित रूप से अध्ययन नहीं किया गया था, लेकिन यह संयोजन सैद्धांतिक रूप से एक प्राकृतिक और आवश्यक पूरक है।

व्यावहारिक अनुप्रयोग प्रेरणा

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

मूल योगदान

  1. नए कोड प्रकार का परिचय: पहली बार खुले पड़ोस अलग करने वाले प्रभावशाली कोड (OD-code) को व्यवस्थित रूप से परिभाषित और अध्ययन किया
  2. सैद्धांतिक आधार की स्थापना: OD-कोड के अस्तित्व की आवश्यक और पर्याप्त शर्तें साबित कीं, और अन्य कोड प्रकारों के साथ संबंध स्थापित किए
  3. जटिलता विश्लेषण: OD-Code समस्या की NP-पूर्णता साबित की, और OD-संख्या और OTD-संख्या के बराबर होने का निर्णय NP-कठिन है
  4. सीमा विश्लेषण: OD-संख्या के लिए ऊपरी और निचली सीमाएं दीं, विशेष रूप से साबित किया कि खुले जुड़वां शीर्षों और अलग-थलग शीर्षों के बिना n-क्रम ग्राफ़ G के लिए, ⌈log n⌉ ≤ γ_OD(G) ≤ n-1
  5. ग्राफ़ परिवार तुलना: कई महत्वपूर्ण ग्राफ़ परिवारों पर OD-कोड और OTD-कोड की संपत्तियों की तुलना की
  6. बहुफलकीय सिद्धांत: OD-कोड समस्या का हाइपरग्राफ़ कवरिंग पुनर्निर्माण प्रदान किया और संबंधित बहुफलकीय संरचनाओं का अध्ययन किया

विधि विवरण

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

दिया गया ग्राफ़ G = (V,E), एक शीर्ष उपसमुच्चय C ⊆ V खुले पड़ोस अलग करने वाला प्रभावशाली कोड (OD-code) है यदि और केवल यदि:

  1. प्रभाव संपत्ति: प्रत्येक शीर्ष v ∈ V के लिए, Nv ∩ C ≠ ∅ (बंद पड़ोस का C के साथ प्रतिच्छेदन गैर-रिक्त है)
  2. खुले पड़ोस अलग करने वाली संपत्ति: प्रत्येक शीर्ष v ∈ V के लिए, N(v) ∩ C अद्वितीय है (खुले पड़ोस का C के साथ प्रतिच्छेदन परस्पर भिन्न है)

जहां N(v) शीर्ष v के खुले पड़ोस को दर्शाता है, Nv = N(v) ∪ {v} बंद पड़ोस को दर्शाता है।

सैद्धांतिक ढांचा

अस्तित्व विश्लेषण

प्रमेय: ग्राफ़ G OD-स्वीकार्य है यदि और केवल यदि G के पास खुले जुड़वां शीर्ष नहीं हैं।

खुले जुड़वां शीर्ष वे हैं जिनके समान खुले पड़ोस हैं, अर्थात् N(u) = N(v) और u ≠ v।

हाइपरग्राफ़ पुनर्निर्माण

पेपर OD-कोड समस्या को समकक्ष रूप से हाइपरग्राफ़ कवरिंग समस्या के रूप में पुनर्निर्मित करता है:

OD-हाइपरग्राफ़ H_OD(G) = (V, F_OD) निम्नलिखित हाइपरएज शामिल करता है:

  • सभी शीर्षों के बंद पड़ोस Nv
  • सभी भिन्न शीर्ष जोड़ियों के खुले पड़ोस सममित अंतर N(u)△N(v)

जहां A△B = (A\B) ∪ (B\A) सममित अंतर को दर्शाता है।

जटिलता प्रमाण

पेपर रैखिक SAT (LSAT) समस्या से कमी के माध्यम से OD-Code समस्या की NP-पूर्णता साबित करता है। निर्मित ग्राफ़ में निम्नलिखित संपत्तियां हैं:

  • द्विपक्षीय ग्राफ़
  • अधिकतम डिग्री 4
  • परिधि कम से कम 6

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

  1. OTD-कोड के साथ सटीक संबंध: साबित किया कि OTD-स्वीकार्य ग्राफ़ G के लिए, γ_OTD(G) - 1 ≤ γ_OD(G) ≤ γ_OTD(G)
  2. Bondy प्रमेय का अनुप्रयोग: OD-संख्या की ऊपरी सीमा साबित करने के लिए Bondy प्रमेय का कुशलतापूर्वक उपयोग किया
  3. क्लस्टर सिद्धांत विधि: अनावश्यक हाइपरएज को हटाकर OD-क्लस्टर प्राप्त किए, समस्या के विश्लेषण को सरल बनाया

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

अनुसंधान वस्तु

पेपर मुख्य रूप से सैद्धांतिक विश्लेषण के माध्यम से निम्नलिखित ग्राफ़ परिवारों का अध्ययन करता है:

  • पूर्ण ग्राफ़ K_n
  • क्लिकों का असंयुक्त संघ
  • k-क्लिक स्टार ग्राफ़
  • द्विपक्षीय ग्राफ़ (अर्ध-ग्राफ़, k-द्विस्टार ग्राफ़)
  • विभाजित ग्राफ़ (सिर मकड़ी ग्राफ़, विस्तारित पतली मकड़ी ग्राफ़)
  • पतली सूर्य ग्राफ़

विश्लेषण विधि

  1. OD-क्लस्टर का निर्माण: प्रत्येक ग्राफ़ परिवार की OD-क्लस्टर संरचना निर्धारित करना
  2. कवरिंग संख्या की गणना: ज्ञात हाइपरग्राफ़ कवरिंग सिद्धांत का उपयोग करके न्यूनतम कवरिंग संख्या की गणना करना
  3. तुलनात्मक विश्लेषण: संबंधित OTD-संख्या के साथ तुलना करना

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

मुख्य परिणाम

पूर्ण ग्राफ़ परिवार

  • पूर्ण ग्राफ़ K_n (n ≥ 2): γ_OD(K_n) = n-1 = γ_OTD(K_n) (जब n ≥ 3)
  • मिलान kK_2: γ_OD(kK_2) = 2k-1 < 2k = γ_OTD(kK_2)

द्विपक्षीय ग्राफ़ परिवार

  • अर्ध-ग्राफ़ B_k: γ_OD(B_k) = 2k-1 < 2k = γ_OTD(B_k)
  • k-द्विस्टार D_k (k ≥ 3): γ_OD(D_k) = 2k-1 < 2k = γ_OTD(D_k)

विभाजित ग्राफ़ परिवार

  • पतली सिर मकड़ी H_k (k ≥ 3): γ_OD(H_k) = k = γ_OTD(H_k)
  • मोटा सिर मकड़ी H̄_k (k ≥ 3): γ_OD(H̄_k) = k+1 = γ_OTD(H̄_k)
  • विस्तारित पतली मकड़ी E_k (k ≥ 4): γ_OD(E_k) = k < k+1 = γ_OTD(E_k)

चरम परिणाम

पेपर ने सैद्धांतिक सीमाओं को प्राप्त करने वाले ग्राफ़ परिवारों की खोज की:

  • ऊपरी सीमा प्राप्ति: पूर्ण ग्राफ़, अर्ध-ग्राफ़ और उनके असंयुक्त संघ ऊपरी सीमा γ_OD(G) = |V(G)| - 1 को प्राप्त करते हैं
  • निचली सीमा विश्लेषण: विभाजित ग्राफ़ लघुगणक निचली सीमा ⌈log n⌉ के करीब हो सकते हैं

महत्वपूर्ण खोजें

  1. गैर-योज्यता: कुछ असंयुक्त ग्राफ़ के लिए, γ_OD(G) उनके जुड़े घटकों की OD-संख्या के योग से अधिक है, जो अन्य कोड प्रकारों में नहीं होता है
  2. अंतर की NP-कठोरता: हालांकि OD-संख्या और OTD-संख्या अधिकतम 1 से भिन्न हैं, लेकिन यह निर्धारित करना कि वे बराबर हैं या नहीं, NP-कठिन है

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

पहचान समस्या वर्णक्रम

पेपर पहचान समस्या के विकास के पथ को व्यवस्थित रूप से प्रस्तुत करता है:

  1. पहचान कोड (1998): Karpovsky आदि द्वारा पहली बार प्रस्तावित
  2. स्थानीयकरण प्रभावशाली कोड (1988): Slater द्वारा प्रस्तुत
  3. पूर्ण प्रभाव भिन्नता (2006): Haynes आदि द्वारा अध्ययन
  4. खुले पड़ोस भिन्नता (2002-2010): Honkala आदि और Seo-Slater द्वारा स्वतंत्र रूप से OTD-कोड प्रस्तावित

अनुप्रयोग क्षेत्र

  • बहु-प्रोसेसर नेटवर्क दोष पहचान
  • ग्राफ़ की तार्किक परिभाषितता
  • ग्राफ़ समरूपता समस्या के मानक चिह्नांकन
  • सेंसर नेटवर्क घुसपैठिए स्थिति निर्धारण

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

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

  1. सैद्धांतिक पूर्णता: OD-कोड पहचान समस्या सैद्धांतिक ढांचे में अंतराल को भरता है, अन्य कोड प्रकारों के साथ एक पूर्ण सैद्धांतिक प्रणाली बनाता है
  2. कम्प्यूटेशनल जटिलता: OD-Code समस्या NP-पूर्ण है, यहां तक कि प्रतिबंधित ग्राफ़ वर्गों पर भी
  3. OTD-कोड के साथ सूक्ष्म संबंध: दोनों संख्यात्मक रूप से अधिकतम 1 से भिन्न हैं, लेकिन यह निर्धारित करना कि वे बराबर हैं या नहीं, कठिन है
  4. ग्राफ़ परिवार वर्गीकरण: विभिन्न ग्राफ़ परिवारों पर, OD-संख्या और OTD-संख्या बराबर या भिन्न हो सकती हैं, समृद्ध संयोजन संरचना प्रदर्शित करती हैं

सीमाएं

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

भविष्य की दिशाएं

  1. एल्गोरिथम अनुसंधान: OD-कोड के लिए सन्निकटन एल्गोरिथम और सटीक एल्गोरिथम डिजाइन करना
  2. पैरामीटरीकृत विश्लेषण: विभिन्न ग्राफ़ पैरामीटर को पैरामीटर के रूप में उपयोग करके निश्चित पैरामीटर एल्गोरिथम का अध्ययन करना
  3. गतिशील समस्याएं: ग्राफ़ संरचना परिवर्तन के समय OD-कोड के रखरखाव समस्या पर विचार करना
  4. अनुप्रयोग विस्तार: व्यावहारिक नेटवर्क समस्याओं में OD-कोड के अनुप्रयोग की खोज करना

गहन मूल्यांकन

लाभ

  1. सैद्धांतिक योगदान: OD-कोड का सैद्धांतिक आधार व्यवस्थित रूप से स्थापित किया, महत्वपूर्ण अनुसंधान अंतराल को भरा
  2. विधि नवाचार: हाइपरग्राफ़ कवरिंग सिद्धांत और बहुफलकीय विधि का कुशलतापूर्वक उपयोग करके समस्या का विश्लेषण किया
  3. परिणाम गहराई: न केवल अस्तित्व और जटिलता परिणाम दिए, बल्कि संबंधित समस्याओं के साथ सटीक संबंधों का गहन विश्लेषण किया
  4. तकनीकी कठोरता: प्रमाण कठोर हैं, संयोजन गणित की कई उन्नत तकनीकों का उपयोग किया

कमियां

  1. व्यावहारिकता: शुद्ध सैद्धांतिक अनुसंधान के रूप में, व्यावहारिक अनुप्रयोग के एल्गोरिथम कार्यान्वयन और प्रदर्शन मूल्यांकन की कमी है
  2. ग्राफ़ परिवार सीमा: अध्ययन किए गए ग्राफ़ परिवार अपेक्षाकृत सीमित हैं, कई व्यावहारिक रूप से महत्वपूर्ण ग्राफ़ वर्ग शामिल नहीं हैं
  3. कम्प्यूटेशनल प्रयोग: बड़े पैमाने के ग्राफ़ पर सैद्धांतिक परिणामों को सत्यापित करने के लिए कम्प्यूटेशनल प्रयोग की कमी है

प्रभाव

  1. शैक्षणिक मूल्य: पहचान समस्या क्षेत्र के लिए नई अनुसंधान दिशा और सैद्धांतिक उपकरण प्रदान करता है
  2. सैद्धांतिक महत्व: प्रभाव सिद्धांत और ग्राफ़ के चिह्नांकन सिद्धांत को समृद्ध करता है
  3. पद्धति योगदान: संयोजन अनुकूलन में हाइपरग्राफ़ कवरिंग विधि की शक्तिशाली अनुप्रयोग प्रदर्शित करता है

उपयुक्त परिदृश्य

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

संदर्भ

पेपर 35 संबंधित संदर्भों का हवाला देता है, जो पहचान समस्या के मुख्य विकास इतिहास और तकनीकी विधियों को कवर करते हैं, विशेष रूप से:

  • 26 Karpovsky आदि का पहचान कोड अग्रणी कार्य
  • 32 Slater का स्थानीयकरण प्रभावशाली कोड मूल सिद्धांत
  • 33 Seo-Slater का OTD-कोड अनुसंधान
  • 2,4 Argiroffo आदि की बहुफलकीय विधि
  • 31 Sassano का कवरिंग बहुफलक सिद्धांत

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