दिग्राफ में दूरस्थता, क्रम, आकार और संयोजकता बाधाएं

मूल जानकारी

• पेपर ID: 2510.08841
• शीर्षक: दिग्राफ में दूरस्थता, क्रम, आकार और संयोजकता बाधाएं
• लेखक: सुफियान मल्लू (जोहान्सबर्ग विश्वविद्यालय, दक्षिण अफ्रीका)
• वर्गीकरण: math.CO (संयोजक गणित)
• प्रकाशन समय: 13 अक्टूबर, 2025 (arXiv प्रीप्रिंट)
• पेपर लिंक: https://arxiv.org/abs/2510.08841

सारांश

यह पेपर दृढ़ता से संयुक्त दिग्राफ की दूरस्थता (remoteness) समस्या का अध्ययन करता है। दृढ़ता से संयुक्त दिग्राफ $D$ के लिए, शीर्ष $v$ की औसत दूरी को $v$ से सभी अन्य शीर्षों तक की दूरी के अंकगणितीय माध्य के रूप में परिभाषित किया जाता है, जबकि $D$ की दूरस्थता $\rho(D)$ को सभी शीर्षों की औसत दूरी के अधिकतम मान के रूप में परिभाषित किया जाता है। पेपर दिए गए क्रम, आकार और शीर्ष संयोजकता वाले दृढ़ दिग्राफ की दूरस्थता के लिए कठोर ऊपरी सीमा प्रदान करता है, सभी क्रम $n$, कम से कम आकार $m$, और शीर्ष संयोजकता $\kappa$ वाले दृढ़ दिग्राफ में दूरस्थता को अधिकतम करने वाले चरम दिग्राफ को चिन्हित करता है, और यह साबित करता है कि क्रम, आकार और संयोजकता बाधाओं के संबंध में अप्रत्यक्ष ग्राफ की दूरस्थता की ऊपरी सीमा सभी ग्राफों के बड़े वर्ग - यूलेरियन दिग्राफ तक विस्तारित की जा सकती है।

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

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

मुख्य योगदान

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

विधि विवरण

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

इनपुट: दृढ़ता से संयुक्त दिग्राफ $D$ और इसके पैरामीटर (क्रम $n$, आकार $m$, शीर्ष संयोजकता $\kappa$) आउटपुट: दूरस्थता $\rho(D)$ की ऊपरी सीमा बाधा शर्तें: $D$ को $\kappa$-संयुक्त दृढ़ दिग्राफ होना चाहिए

मुख्य अवधारणाएं

1. औसत दूरी: शीर्ष $v$ की औसत दूरी को इस प्रकार परिभाषित किया जाता है $\sigma(v,D) = \frac{1}{n-1}\sum_{w \in V(D)} d_D(v,w)$
2. दूरस्थता: दिग्राफ की दूरस्थता को इस प्रकार परिभाषित किया जाता है $\rho(D) = \max_{v \in V(D)} \sigma(v,D)$
3. $\kappa$-संयुक्त पथ पूर्ण दिग्राफ: निम्नलिखित रूप का दिग्राफ $K_1 \overleftarrow{+} [\overleftrightarrow{K_\kappa}]^\ell \overleftarrow{+} \overleftrightarrow{K_a} \overleftarrow{+} \overleftrightarrow{K_b}$ जहां $a \geq \kappa$।

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

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

मुख्य लेम्मा

लेम्मा 3.1:

• (a) $\kappa$-संयुक्त पथ पूर्ण दिग्राफ $H$ के लिए, किसी भी चाप को जोड़ने से इसकी दूरस्थता में कमी आएगी
• (b) दो अलग-अलग $\kappa$-संयुक्त पथ पूर्ण दृढ़ दिग्राफ के बीच आकार-दूरस्थता व्यापार संबंध सख्त है
• (c) दिए गए $n, \kappa$ के लिए, विशिष्ट आकार के $\kappa$-संयुक्त पथ पूर्ण दृढ़ दिग्राफ के अस्तित्व की आवश्यक और पर्याप्त शर्तें

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

यह पेपर शुद्ध सैद्धांतिक अनुसंधान है, प्रायोगिक सत्यापन में शामिल नहीं है, बल्कि कठोर गणितीय प्रमाण के माध्यम से परिणामों की सत्यता को सत्यापित करता है।

प्रमाण रणनीति

1. अस्तित्व प्रमाण: ठोस चरम ग्राफ परिवारों का निर्माण
2. अद्वितीयता प्रमाण: चरम ग्राफ की संरचना की अद्वितीयता साबित करता है
3. कठोरता सत्यापन: ठोस उदाहरणों के माध्यम से सीमाओं की कठोरता सत्यापित करता है

मुख्य परिणाम

मुख्य प्रमेय

प्रमेय 3.2: मान लीजिए $D$ क्रम $n$, आकार $m$ का $\kappa$-संयुक्त दृढ़ दिग्राफ है, जहां $m \leq n^2 - 2n - 1$, तब $\rho(D) \leq \rho(DPK_{n,m,\kappa})$

जब $m \equiv (n^2-2n-1) \pmod{\kappa}$ और विशिष्ट शर्तें संतुष्ट हों, तो समानता तब और केवल तब होती है जब $D = DPK_{n,m,\kappa}$।

ठोस सीमाएं

परिणाम 3.3: उपयुक्त शर्तों के तहत, $\rho(D) \leq \frac{n}{\kappa} + 2 - \frac{1}{\kappa} - \frac{\kappa-1}{n-1} - \frac{m^*}{\kappa(n-1)}$

जहां $m^*$ वह न्यूनतम पूर्णांक है जो $m^* \geq m$ और $m^* \equiv (n^2-2n-1) \pmod{\kappa}$ को संतुष्ट करता है।

यूलेरियन दिग्राफ के परिणाम

प्रमेय 4.3: मान लीजिए $D$ क्रम $n$, कम से कम आकार $2m_0$ का $\kappa$-संयुक्त यूलेरियन दिग्राफ है, तब $\rho(D) \leq \frac{n}{2\kappa} + 2 - \frac{1}{\kappa} - \frac{\kappa-1}{n-1} - \frac{m_0}{\kappa(n-1)}$

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

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

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

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

1. Zelinka 29 और Aouchiche, Hansen 4: संयुक्त ग्राफ की दूरस्थता के लिए मूल ऊपरी सीमा $\rho(G) \leq n/2$ स्थापित करते हैं
2. Ai आदि 1: दूरस्थता की अवधारणा को दिग्राफ तक विस्तारित करते हैं
3. Entringer आदि 18: ग्राफ के आकार बाधाओं पर विचार करते हैं
4. Dankelmann आदि 15: संयोजकता बाधा के साथ अप्रत्यक्ष ग्राफ की दूरस्थता सीमा स्थापित करते हैं

इस पेपर के योगदान की स्थिति

यह दिग्राफ दूरस्थता पर विशेष रूप से अनुसंधान करने वाला दूसरा पेपर है, दिग्राफ सिद्धांत में महत्वपूर्ण अंतराल को भरता है, और सफलतापूर्वक अप्रत्यक्ष ग्राफ के सटीक परिणामों को दिग्राफ के व्यापक वर्ग तक विस्तारित करता है।

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

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

1. $\kappa$-संयुक्त दृढ़ दिग्राफ की दूरस्थता के लिए कठोर ऊपरी सीमा स्थापित करता है
2. चरम ग्राफ की संरचना को पूरी तरह से चिन्हित करता है ($\kappa$-संयुक्त पथ पूर्ण दिग्राफ)
3. साबित करता है कि अप्रत्यक्ष ग्राफ की दूरस्थता सीमा यूलेरियन दिग्राफ तक विस्तारित की जा सकती है

सैद्धांतिक महत्व

• दिग्राफ की दूरी सिद्धांत को समृद्ध करता है
• नेटवर्क विश्लेषण के लिए नए सैद्धांतिक उपकरण प्रदान करता है
• अप्रत्यक्ष ग्राफ और दिग्राफ सिद्धांत के बीच पुल स्थापित करता है

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

1. अधिक सामान्य दिग्राफ वर्गों की दूरस्थता का अध्ययन करना
2. दूरस्थता और अन्य ग्राफ पैरामीटर के बीच संबंध की खोज करना
3. भारित दिग्राफ के मामले पर विचार करना

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

लाभ

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

कमियां

1. अनुप्रयोग की सीमा: मुख्य रूप से सैद्धांतिक परिणाम हैं, व्यावहारिक अनुप्रयोग मूल्य को आगे की खोज की आवश्यकता है
2. कम्प्यूटेशनल जटिलता: संबंधित समस्याओं की कम्प्यूटेशनल जटिलता पर चर्चा नहीं करता है
3. पैरामीटर सीमा: कुछ परिणामों को विशिष्ट मॉड्यूलो ऑपरेशन शर्तों को संतुष्ट करने की आवश्यकता है, जो प्रयोज्यता को सीमित करता है

प्रभाव

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

लागू परिस्थितियां

1. नेटवर्क विश्लेषण में केंद्रीयता माप
2. दिग्राफ की संरचनात्मक विश्लेषण
3. चरम ग्राफ सिद्धांत अनुसंधान
4. एल्गोरिदम डिजाइन में सैद्धांतिक सीमा विश्लेषण

संदर्भ

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

• 1 Ai आदि का दिग्राफ निकटता और दूरस्थता पर अग्रणी कार्य
• 15 Dankelmann आदि का अप्रत्यक्ष ग्राफ दूरस्थता पर नवीनतम परिणाम
• 29 Zelinka का दूरस्थता पर प्रारंभिक कार्य

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