2025-11-17T18:31:12.470972

Distance mutual-visibility coloring: relations with (total) domination, exact distance graphs and graph products

Babu, Brešar, S et al.
The concept of mutual-visibility (MV) has been extended in several directions. A vertex subset $S$ of a graph $G$ is a $k$-distance mutual-visibility ($k$DMV) set if for any two vertices in $S$, there is a geodesic between them of length at most $k$ whose internal vertices are not in $S$. In this paper, we combine this with the MV coloring as follows. For any integer $k\geq1$, a $k$DMV coloring of $G$ is a partition of $V(G)$ into $k$DMV sets, and the $k$DMV chromatic number $χ_{μ_k}(G)$ is the minimum cardinality of such a partition. When $k=1$ or $k\ge {\rm diam}(G)$, it equals the clique cover number $θ(G)$ or the MV chromatic number $χ_μ(G)$, respectively. So, our attention is given to $1<k<{\rm diam}(G)$ with $k=2$ producing the most interesting results. We prove that $χ_{μ_2}(G)\le|V(G)|/2$ and present large families of graphs that attain the bound. In addition, $χ_{μ_2}(G)$ is bounded from above by the total domination number $γ_t(G)$ if $G$ is isolate-free, while in graphs $G$ with girth $g(G)\geq7$, $χ_{μ_2}(G)$ is bounded from below by the domination number $γ(G)$. A surprising relation with the exact distance-2 graphs is found, which results in $θ(G^{[\natural2]})=γ_{t}(G)$ for any isolate-free graph $G$ with $g(G)\geq7$. The relation is explored further in lexicographic product graphs, where we prove the sharp inequalities $χ_{μ_{2}}(G\circ H)\leq θ(G^{[\natural2]})\leq θ\big{(}(G\circ H)^{[\natural2]}\big{)}$. We also prove a sharp lower (resp. upper) bound on $χ_{μ_2}$ (resp. $χ_{μ_k}$) for the Cartesian (resp. strong) product of two connected graphs and show that they are widely sharp. Finally, we characterize the block graphs $G$ with $χ_{μ_k}(G)=χ_μ(G)$, where $k={\rm diam}(G)-1$.
academic

दूरी पारस्परिक-दृश्यता रंगाई: (कुल) प्रभुत्व, सटीक दूरी ग्राफ और ग्राफ उत्पादों के साथ संबंध

मूल जानकारी

  • पेपर ID: 2510.10284
  • शीर्षक: Distance mutual-visibility coloring: relations with (total) domination, exact distance graphs and graph products
  • लेखक: Saneesh Babu, Boštjan Brešar, Aparna Lakshmanan S, Babak Samadi
  • वर्गीकरण: math.CO (संयोजन गणित)
  • प्रकाशन तिथि: 11 अक्टूबर 2025
  • पेपर लिंक: https://arxiv.org/abs/2510.10284

सारांश

यह पेपर k-दूरी पारस्परिक-दृश्यता रंगाई समस्या का अध्ययन करता है, जो Di Stefano द्वारा 2022 में प्रस्तुत की गई पारस्परिक-दृश्यता अवधारणा का विस्तार है। ग्राफ G के शीर्ष उपसमुच्चय S के लिए, यदि S में किन्हीं दो शीर्षों के बीच लंबाई अधिकतम k की एक भू-रेखा मौजूद है, और इसके आंतरिक शीर्ष S में नहीं हैं, तो S को k-दूरी पारस्परिक-दृश्यता समुच्चय (k-DMV समुच्चय) कहा जाता है। पेपर इस अवधारणा को पारस्परिक-दृश्यता रंगाई के साथ जोड़ता है, k-DMV रंगाई संख्या χ_μ_k(G) को परिभाषित करता है। अनुसंधान से पता चलता है कि k=2 के लिए सबसे दिलचस्प परिणाम मिलते हैं, χ_μ_2(G) ≤ |V(G)|/2 साबित किया गया है, और प्रभुत्व संख्या, कुल प्रभुत्व संख्या और सटीक दूरी ग्राफ के साथ गहरे संबंध स्थापित किए गए हैं।

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

  1. समस्या की उत्पत्ति: पारस्परिक-दृश्यता अवधारणा मूल रूप से Di Stefano द्वारा 2022 में प्रस्तुत की गई थी, जो शास्त्रीय "तीन बिंदु संरेखित नहीं" समस्या और समतल गतिशील रोबोट पुनः स्थिति समस्या से संबंधित है।
  2. अनुसंधान प्रेरणा:
    • पारस्परिक-दृश्यता अवधारणा नई है, लेकिन व्यापक ध्यान आकर्षित कर चुकी है (MathSciNet में 20 से अधिक उद्धरण)
    • मौजूदा अनुसंधान मुख्य रूप से पारस्परिक-दृश्यता समुच्चय की अधिकतम कार्डिनैलिटी पर केंद्रित है, रंगाई समस्याओं का व्यवस्थित अध्ययन अभाव है
    • k-दूरी प्रतिबंध संचार को अधिक कुशल बनाता है, व्यावहारिक अनुप्रयोग मूल्य रखता है
  3. व्यावहारिक महत्व: कंप्यूटर नेटवर्क या सामाजिक नेटवर्क में, पारस्परिक-दृश्यता गुण वाले शीर्ष उन संस्थाओं का प्रतिनिधित्व कर सकते हैं जिन्हें कुशल, गोपनीय संचार की आवश्यकता है, यह सुनिश्चित करते हुए कि संदेश अन्य संस्थाओं के माध्यम से नहीं जाते हैं।

मुख्य योगदान

  1. नई अवधारणा का परिचय: पहली बार k-दूरी पारस्परिक-दृश्यता रंगाई संख्या χ_μ_k(G) को परिभाषित किया, जो क्लिक कवर संख्या (k=1) और पारस्परिक-दृश्यता रंगाई संख्या (k≥diam(G)) को एकीकृत करता है
  2. मूल सीमाएं स्थापित करना:
    • χ_μ_2(G) ≤ ⌈|V(G)|/2⌉ साबित किया, और इस सीमा को प्राप्त करने वाले ग्राफ परिवारों को दिया
    • अलग-थलग शीर्षों के बिना ग्राफ के लिए, χ_μ_2(G) ≤ γ_t(G)
    • कम से कम 7 की परिधि वाले ग्राफ के लिए, χ_μ_2(G) ≥ γ(G)
  3. सटीक दूरी ग्राफ के साथ संबंध की खोज: साबित किया कि अलग-थलग शीर्षों के बिना और कम से कम 7 की परिधि वाले ग्राफ G के लिए, θ(G♮2) = γ_t(G)
  4. ग्राफ उत्पादों का व्यवस्थित अध्ययन:
    • शब्दकोश क्रम उत्पाद: χ_μ_2(G∘H) ≤ θ(G♮2) ≤ θ((G∘H)♮2)
    • मजबूत उत्पाद: χ_μ_k(G⊠H) ≤ χ_μ_k(G)χ_μ_k(H)
    • कार्टेशियन उत्पाद: χ_μ_2(G□H) ≥ max{χ_μ_2(G)ρ_2(H), χ_μ_2(H)ρ_2(G)}
  5. विशेष ग्राफ वर्गों का लक्षण वर्णन: पूरी तरह से χ_μ_k(G) = χ_μ(G) (जहां k = diam(G)-1) को संतुष्ट करने वाले ब्लॉक ग्राफ का लक्षण वर्णन किया

विधि विवरण

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

दिए गए ग्राफ G और सकारात्मक पूर्णांक k के लिए, k-दूरी पारस्परिक-दृश्यता रंगाई V(G) को कई k-DMV समुच्चयों में विभाजित करने की एक रंगाई योजना है। जहां k-DMV समुच्चय M संतुष्ट करता है: M में किन्हीं दो शीर्षों u,v के लिए, लंबाई अधिकतम k की एक u,v-भू-रेखा मौजूद है, जिसके आंतरिक शीर्ष M में नहीं हैं।

इनपुट: ग्राफ G = (V,E), सकारात्मक पूर्णांक k आउटपुट: V(G) का एक विभाजन {S_1, S_2, ..., S_t}, जहां प्रत्येक S_i एक k-DMV समुच्चय है उद्देश्य: विभाजन के समुच्चय संख्या t को कम से कम करना

मुख्य तकनीकी विधि

1. मूल सिद्धांत स्थापना

अवलोकन 1: व्यास d वाले ग्राफ G के लिए, एकदिष्ट श्रृंखला है: χ_μ(G) = χ_μ_d(G) ≤ χ_μ_(G) ≤ ... ≤ χ_μ_1(G) = θ(G)

अवलोकन 2: मूल निचली सीमा χ_μ_k(G) ≥ ⌈|V(G)|/μ_k(G)⌉

2. k=2 स्थिति का गहन विश्लेषण

प्रमेय 4: किसी भी जुड़े हुए ग्राफ G के लिए, χ_μ_2(G) ≤ ⌈n/2⌉

प्रमाण विचार: जनक वृक्ष पर आगमन के माध्यम से, वृक्ष को ऐसी संरचनाओं में विघटित करना जिन्हें दो रंगों से रंगा जा सकता है।

प्रमेय 5: यदि G के पास अलग-थलग शीर्ष नहीं हैं, तो χ_μ_2(G) ≤ γ_t(G)

प्रमाण विधि: रचनात्मक प्रमाण, कुल प्रभुत्व समुच्चय D = {v_1,...,v_γ_t(G)} का उपयोग करके, D_i = N_G(v_i)\⋃_^{i-1}N_G(v_j) को परिभाषित करना, यह साबित करना कि प्रत्येक D_i एक 2DMV समुच्चय है।

3. परिधि और प्रभुत्व संख्या का संबंध

लेम्मा 6: यदि g(G) ≥ 7, तो χ_μ_2(G)-रंगाई में प्रत्येक रंग वर्ग C किसी शीर्ष के बंद पड़ोस का उपसमुच्चय है।

प्रमेय 7: यदि g(G) ≥ 7, तो χ_μ_2(G) ≥ γ(G)

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

  1. एकीकृत ढांचा: क्लिक कवर, पारस्परिक-दृश्यता रंगाई को k-DMV रंगाई ढांचे में एकीकृत करना
  2. परिधि स्थिति का सटीक लक्षण वर्णन: साबित किया कि परिधि 7 χ_μ_2(G) ≥ γ(G) की गारंटी देने के लिए न्यूनतम मान है
  3. सटीक दूरी ग्राफ संबंध: पहली बार 2DMV रंगाई और सटीक दूरी-2 ग्राफ के बीच गहरा संबंध स्थापित किया
  4. ग्राफ उत्पादों का व्यवस्थित विश्लेषण: तीन मुख्य ग्राफ उत्पादों के लिए कसी हुई ऊपरी और निचली सीमाएं दी

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

सैद्धांतिक सत्यापन विधि

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

  1. पथ और चक्र: P_n और C_n की सटीक χ_μ_k मान की गणना की
  2. विशेष ग्राफ परिवार: विभिन्न सीमाओं को प्राप्त करने वाले ग्राफ परिवारों का निर्माण किया
  3. उत्पाद ग्राफ: P_n⊠K_m जैसे विशिष्ट उत्पाद ग्राफ के गुणों का विश्लेषण किया

मुख्य उदाहरण विश्लेषण

प्रस्ताव 2:

  • पथ P_n के लिए: χ_μ_k(P_n) = ⌈n/2⌉
  • चक्र C_n के लिए: χ_μ_k(C_n) = ⌈n/3⌉ (जब n ≤ 3k), ⌈n/2⌉ (अन्यथा)

प्रस्ताव 12: P_n⊠K_m के लिए (n≥4, m≥2, k∈{2,...,n-2}): χ_μ_k(P_n⊠K_m) = 2⌊n/(k+2)⌋ + correction_term

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

मुख्य सैद्धांतिक परिणाम

  1. मूल सीमाओं की कसापन:
    • χ_μ_2(G) ≤ ⌈|V(G)|/2⌉ सभी ग्राफ के लिए सत्य है, और पथ, लंबे चक्र आदि द्वारा प्राप्त किया जाता है
    • χ_μ_2(G) ≤ γ_t(G) अलग-थलग शीर्षों के बिना ग्राफ के लिए सत्य है, और ऐसे ग्राफ परिवारों का निर्माण किया जा सकता है जहां अंतर मनमाने ढंग से बड़ा हो
  2. परिधि स्थिति की इष्टतमता:
    • परिधि 6 वाले ग्राफ का निर्माण किया लेकिन γ(G) = 5 > χ_μ_2(G) = 3
    • साबित किया कि परिधि 7 χ_μ_2(G) ≥ γ(G) की गारंटी देने के लिए न्यूनतम स्थिति है
  3. ग्राफ उत्पाद परिणामों की तीक्ष्णता:
    • मजबूत उत्पाद सीमा χ_μ_k(G⊠H) ≤ χ_μ_k(G)χ_μ_k(H) अनंत ग्राफ परिवारों द्वारा प्राप्त की जाती है
    • कार्टेशियन उत्पाद निचली सीमा टोरस ग्राफ आदि द्वारा प्राप्त की जाती है

सटीक दूरी ग्राफ का आश्चर्यजनक संबंध

प्रमेय 8: यदि G के पास अलग-थलग शीर्ष नहीं हैं और g(G) ≥ 7, तो θ(G♮2) = χ_i_μ_2(G) = γ_t(G)

यह परिणाम तीन प्रतीत होने वाले असंबंधित ग्राफ पैरामीटर के बीच समानता संबंध स्थापित करता है, जिसका महत्वपूर्ण सैद्धांतिक महत्व है।

हाइपरक्यूब की विशेष गुण

प्रस्ताव 16: n-हाइपरक्यूब Q_n के लिए, χ_μ_2(Q_n) ≤ γ(Q_n)

अनुमान: χ_μ_2(Q_n) = γ(Q_n) सभी n के लिए सत्य है

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

  1. पारस्परिक-दृश्यता अनुसंधान: Di Stefano (2022) ने मूल अवधारणा प्रस्तुत की, Cera आदि ने k-दूरी संस्करण तक विस्तारित किया
  2. पारस्परिक-दृश्यता रंगाई: Klavžar आदि (2025) ने पहली बार पारस्परिक-दृश्यता रंगाई समस्या का अध्ययन किया
  3. सटीक दूरी ग्राफ: 1980 के दशक में प्रस्तुत किए गए, हाल ही में फिर से ध्यान आकर्षित कर रहे हैं
  4. प्रभुत्व सिद्धांत: शास्त्रीय ग्राफ सिद्धांत अनुसंधान क्षेत्र, इस पेपर ने नए संबंध स्थापित किए

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

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

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

सीमाएं

  1. मुख्य परिणाम k=2 की स्थिति पर केंद्रित हैं, सामान्य k मान के लिए अनुसंधान कम है
  2. कुछ सीमाओं की कसापन केवल विशिष्ट ग्राफ परिवारों में सत्यापित की गई है
  3. कम्प्यूटेशनल जटिलता समस्याओं को शामिल नहीं किया गया है

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

पेपर तीन विशिष्ट खुली समस्याएं प्रस्तुत करता है:

समस्या 1: χ_μ_2(G) = θ(G) को संतुष्ट करने वाले ब्लॉक ग्राफ G का लक्षण वर्णन करें

समस्या 2: जुड़े हुए ग्राफ G,H के लिए, क्या χ_μ_2(G□H) ≥ max{χ_μ_2(G)γ(H), χ_μ_2(H)γ(G)} है?

समस्या 3: क्या χ_μ_2(Q_n) = γ(Q_n) सभी हाइपरक्यूब के लिए सत्य है?

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

लाभ

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

कमियां

  1. कम्प्यूटेशनल जटिलता अभाव: χ_μ_k(G) की कम्प्यूटेशनल जटिलता पर चर्चा नहीं की गई है
  2. अनुप्रयोग सीमा: नेटवर्क संचार अनुप्रयोग का उल्लेख किया गया है, लेकिन विशिष्ट अनुप्रयोग परिदृश्य विश्लेषण अभाव है
  3. एल्गोरिदम डिजाइन: χ_μ_k(G) की गणना या अनुमान के लिए कुशल एल्गोरिदम अभाव है

प्रभाव

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

लागू परिदृश्य

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

संदर्भ

पेपर 18 संबंधित संदर्भों का हवाला देता है, मुख्य रूप से:

  • Di Stefano (2022): पारस्परिक-दृश्यता अवधारणा का मूल साहित्य
  • Cera आदि: k-दूरी पारस्परिक-दृश्यता का विस्तार
  • Klavžar आदि: पारस्परिक-दृश्यता रंगाई का पहला अनुसंधान
  • शास्त्रीय ग्राफ सिद्धांत पाठ्यपुस्तकें और प्रभुत्व सिद्धांत साहित्य

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