2025-11-10T02:45:05.969614

On a Conjecture Concerning the Complementary Second Zagreb Index

Saber, Alraqad, Ali et al.
The complementary second Zagreb index of a graph $G$ is defined as $cM_2(G)=\sum_{uv\in E(G)}|(d_u(G))^2-(d_v(G))^2|$, where $d_u(G)$ denotes the degree of a vertex $u$ in $G$ and $E(G)$ represents the edge set of $G$. Let $G^*$ be a graph having the maximum value of $cM_2$ among all connected graphs of order $n$. Furtula and Oz [MATCH Commun. Math. Comput. Chem. 93 (2025) 247--263] conjectured that $G^*$ is the join $K_k+\overline{K}_{n-k}$ of the complete graph $K_k$ of order $k$ and the complement $\overline{K}_{n-k}$ of the complete graph $K_{n-k}$ such that the inequality $k<\lceil n/2 \rceil$ holds. We prove that (i) the maximum degree of $G^*$ is $n-1$ and (ii) no two vertices of minimum degree in $G^*$ are adjacent; both of these results support the aforementioned conjecture. We also prove that the number of vertices of maximum degree in $G^*$, say $k$, is at most $-\frac{2}{3}n+\frac{3}{2}+\frac{1}{6}\sqrt{52n^2-132n+81}$, which implies that $k<5352n/10000$. Furthermore, we establish results that support the conjecture under consideration for certain bidegreed and tridegreed graphs. In the aforesaid paper, it was also mentioned that determining the $k$ as a function of the $n$ is far from being an easy task; we obtain the values of $k$ for $5\le n\le 149$ in the case of certain bidegreed graphs by using computer software and found that the resulting sequence of the values of $k$ does not exist in "The On-Line Encyclopedia of Integer Sequences" (an online database of integer sequences).
academic

पूरक द्वितीय ज़ाग्रेब सूचकांक के संबंध में एक अनुमान पर

मूल जानकारी

  • पेपर ID: 2501.01295
  • शीर्षक: पूरक द्वितीय ज़ाग्रेब सूचकांक के संबंध में एक अनुमान पर
  • लेखक: Hicham Saber, Tariq Alraqad, Akbar Ali, Abdulaziz M. Alanazi, Zahid Raza
  • वर्गीकरण: math.CO (संयोजन गणित)
  • प्रकाशन समय: 2 जनवरी 2025 को arXiv पर प्रस्तुत
  • पेपर लिंक: https://arxiv.org/abs/2501.01295

सारांश

यह पेपर ग्राफ के पूरक द्वितीय ज़ाग्रेब सूचकांक की चरम मूल्य समस्याओं का अध्ययन करता है। पूरक द्वितीय ज़ाग्रेब सूचकांक को cM2(G)=∑uv∈E(G)∣(du(G))2−(dv(G))2∣cM_2(G)=\sum_{uv\in E(G)}|(d_u(G))^2-(d_v(G))^2| के रूप में परिभाषित किया गया है, जहां du(G)d_u(G) ग्राफ GG में शीर्ष uu की डिग्री को दर्शाता है। लेखकों ने Furtula और Oz द्वारा प्रस्तावित अनुमान का गहन अध्ययन किया है, जो मानता है कि सभी nn-क्रम संयुक्त ग्राफ में cM2cM_2 को अधिकतम करने वाला ग्राफ G∗G^* पूर्ण ग्राफ KkK_k और इसके पूरक K‾n−k\overline{K}_{n-k} का संयोजन है, जहां k<⌈n/2⌉k<\lceil n/2 \rceil है।

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

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

  1. आणविक वर्णकों का महत्व: आणविक वर्णक आणविक पुस्तकालयों की आभासी स्क्रीनिंग और आणविक भौतिक-रासायनिक गुणों की भविष्यवाणी के लिए मौलिक उपकरण हैं। रासायनिक ग्राफ सिद्धांत में आणविक ग्राफ के माध्यम से परिभाषित वर्णकों को स्थलीय सूचकांक कहा जाता है।
  2. डिग्री-आधारित स्थलीय सूचकांक: शीर्ष डिग्री के आधार पर परिभाषित स्थलीय सूचकांक रासायनिक ग्राफ सिद्धांत में व्यापक रूप से लागू होते हैं। पूरक द्वितीय ज़ाग्रेब सूचकांक (CSZ सूचकांक) हाल ही में प्रस्तावित एक नया डिग्री-आधारित स्थलीय सूचकांक है।
  3. चरम मूल्य समस्याएं: दिए गए बाधाओं के तहत किसी स्थलीय सूचकांक को चरम करने वाली ग्राफ संरचना को निर्धारित करना ग्राफ सिद्धांत में एक महत्वपूर्ण समस्या है, जिसका सैद्धांतिक और व्यावहारिक मूल्य है।

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

  1. सैद्धांतिक पूर्णता: Furtula और Oz ने 2025 में CSZ सूचकांक के चरम ग्राफ संरचना के बारे में एक अनुमान प्रस्तावित किया, लेकिन कठोर गणितीय प्रमाण की कमी है।
  2. कम्प्यूटेशनल जटिलता: चरम ग्राफ में अधिकतम डिग्री शीर्षों की संख्या kk को nn के फलन के रूप में निर्धारित करना "दूर से आसान नहीं" माना जाता है, जिसके लिए नए सैद्धांतिक उपकरण और कम्प्यूटेशनल विधियों की आवश्यकता है।
  3. व्यावहारिक मूल्य: CSZ सूचकांक के चरम गुणों को समझना रासायनिक ग्राफ सिद्धांत और आणविक डिजाइन के लिए महत्वपूर्ण है।

मुख्य योगदान

इस पेपर के मुख्य योगदान में शामिल हैं:

  1. चरम ग्राफ के अधिकतम डिग्री गुण को प्रमाणित किया: यह प्रमाणित किया कि cM2cM_2 को अधिकतम करने वाले संयुक्त nn-क्रम ग्राफ G∗G^* की अधिकतम डिग्री n−1n-1 है।
  2. न्यूनतम डिग्री शीर्षों की आसन्नता गुण को प्रकट किया: यह प्रमाणित किया कि G∗G^* में किन्हीं दो न्यूनतम डिग्री शीर्ष आसन्न नहीं हैं।
  3. अधिकतम डिग्री शीर्षों की संख्या के लिए ऊपरी सीमा स्थापित की: यह प्रमाणित किया कि G∗G^* में अधिकतम डिग्री शीर्षों की संख्या kk निम्नलिखित को संतुष्ट करती है: k≤−23n+32+1652n2−132n+81<5352n10000k \leq -\frac{2}{3}n+\frac{3}{2}+\frac{1}{6}\sqrt{52n^2-132n+81} < \frac{5352n}{10000}
  4. विशेष ग्राफ वर्गों के लिए अनुमान को सत्यापित किया: द्विडिग्री ग्राफ और त्रिडिग्री ग्राफ वर्गों के लिए Furtula-Oz अनुमान की सत्यता को प्रमाणित किया।
  5. कम्प्यूटेशनल डेटा प्रदान किया: कंप्यूटर सॉफ्टवेयर का उपयोग करके 5≤n≤1495 \leq n \leq 149 श्रेणी में द्विडिग्री ग्राफ स्थिति के लिए kk मान की गणना की, और पाया कि प्राप्त अनुक्रम पूर्णांक अनुक्रम विश्वकोश में मौजूद नहीं है।

विधि विवरण

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

सभी nn-क्रम संयुक्त ग्राफ में पूरक द्वितीय ज़ाग्रेब सूचकांक cM2(G)=∑uv∈E(G)∣(du(G))2−(dv(G))2∣cM_2(G) = \sum_{uv\in E(G)}|(d_u(G))^2-(d_v(G))^2| को अधिकतम करने वाली ग्राफ की संरचनात्मक गुणों का अध्ययन करना।

मुख्य प्रमेय और प्रमाण विधियां

प्रमेय 1 (प्रस्ताव 2): अधिकतम डिग्री गुण

कथन: यदि ग्राफ GG सभी nn-क्रम संयुक्त ग्राफ में अधिकतम cM2cM_2 मान रखता है, और n≥4n \geq 4 है, तो GG की अधिकतम डिग्री n−1n-1 है।

प्रमाण विचार:

  1. मान लीजिए अधिकतम डिग्री Δ<n−1\Delta < n-1 है, डिग्री Δ\Delta वाले शीर्ष vv और vv से असंयुक्त शीर्ष uu को चुनें
  2. किनारा uvuv जोड़कर ग्राफ G′G' का निर्माण करें
  3. cM2(G′)−cM2(G)cM_2(G') - cM_2(G) की गणना करें, यह प्रमाणित करें कि यह अंतर सकारात्मक है, जो GG की चरमता के विरुद्ध है

प्रमेय 2 (प्रस्ताव 3): न्यूनतम डिग्री शीर्षों की गैर-आसन्नता

कथन: चरम ग्राफ GG में, किन्हीं दो न्यूनतम डिग्री शीर्ष आसन्न नहीं हैं।

प्रमाण विधि: विरोधाभास द्वारा, मान लीजिए कि आसन्न न्यूनतम डिग्री शीर्ष मौजूद हैं, उनके बीच का किनारा हटाने से cM2cM_2 मान बढ़ता है।

प्रमेय 3 (प्रस्ताव 4): अधिकतम डिग्री शीर्षों की संख्या के लिए ऊपरी सीमा

प्रमाण तकनीक:

  1. अधिकतम डिग्री शीर्षों और न्यूनतम डिग्री शीर्षों को जोड़ने वाले किनारे को हटाने के लिए चुनें
  2. इस किनारे को हटाने के cM2cM_2 मान पर प्रभाव का विश्लेषण करें
  3. kk के संबंध में द्विघात असमानता स्थापित करें
  4. ऊपरी सीमा सूत्र प्राप्त करने के लिए हल करें

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

द्विडिग्री ग्राफ का पूर्ण लक्षण वर्णन (प्रस्ताव 5)

अधिकतम डिग्री n−1n-1 वाले nn-क्रम द्विडिग्री संयुक्त ग्राफ के लिए, यह प्रमाणित किया गया: cM2(G)≤k(n−k)((n−1)2−k2)cM_2(G) \leq k(n-k)((n-1)^2 - k^2) समानता तब और केवल तभी सत्य है जब G=Kk+K‾n−kG = K_k + \overline{K}_{n-k} हो।

त्रिडिग्री ग्राफ का विश्लेषण (प्रस्ताव 7)

लेम्मा 6 द्वारा स्थापित असमानता उपकरण का उपयोग करके, त्रिडिग्री ग्राफ का वर्गीकरण विश्लेषण करें, प्रत्येक स्थिति में अधिक इष्टतम Kt+K‾n−tK_t + \overline{K}_{n-t} संरचना के अस्तित्व को प्रमाणित करें।

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

कम्प्यूटेशनल विधि

5≤n≤1495 \leq n \leq 149 की द्विडिग्री ग्राफ स्थिति के लिए कंप्यूटर सॉफ्टवेयर का उपयोग करके व्यापक गणना करें, प्रत्येक nn के लिए इष्टतम kk मान निर्धारित करें।

डेटा सत्यापन

गणना किए गए kk मान अनुक्रम को "The On-Line Encyclopedia of Integer Sequences" डेटाबेस से तुलना करें।

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

मुख्य कम्प्यूटेशनल परिणाम

तालिका 1 में nn से 5 से 149 तक संबंधित इष्टतम kk मान दिखाए गए हैं, उदाहरण के लिए:

  • n=5n=5 पर, k=2k=2
  • n=10n=10 पर, k=4k=4
  • n=20n=20 पर, k=8k=8
  • n=50n=50 पर, k=19k=19
  • n=100n=100 पर, k=39k=39
  • n=149n=149 पर, k=58k=58

अनुक्रम की नवीनता

गणना किया गया अनुक्रम 2,2,3,3,3,4,4,4,5,5,6,6,6,7,7,8,8,8,9,9,10,10,10,11,11,12,12,12,13,13,13,...2,2,3,3,3,4,4,4,5,5,6,6,6,7,7,8,8,8,9,9,10,10,10,11,11,12,12,12,13,13,13,... OEIS डेटाबेस में मौजूद नहीं है, जो दर्शाता है कि यह एक नया पूर्णांक अनुक्रम है।

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

अनुमान 2 की पुष्टि करता है कि n≥11n \geq 11 के लिए, इष्टतम kk मान 3n10<k<4n10\frac{3n}{10} < k < \frac{4n}{10} को संतुष्ट करता है, जो कम्प्यूटेशनल परिणामों के अनुरूप है।

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

ज़ाग्रेब सूचकांक का विकास इतिहास

  1. शास्त्रीय ज़ाग्रेब सूचकांक: द्वितीय ज़ाग्रेब सूचकांक M2(G)=∑uv∈E(G)dudvM_2(G) = \sum_{uv \in E(G)} d_u d_v रासायनिक ग्राफ सिद्धांत में एक शास्त्रीय सूचकांक है
  2. ज्यामितीय विधि: Gutman द्वारा प्रस्तावित ज्यामितीय विधि डिग्री-आधारित स्थलीय सूचकांकों के अनुसंधान के लिए नया दृष्टिकोण प्रदान करती है
  3. पूरक सूचकांक: CSZ सूचकांक कई अनुसंधानों में स्वतंत्र रूप से प्रस्तावित किया गया है, विभिन्न नामों के साथ (नैनो ज़ाग्रेब सूचकांक, F-minus सूचकांक आदि)

चरम ग्राफ सिद्धांत

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

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

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

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

सीमाएं

  1. सामान्य स्थिति का पूर्ण प्रमाण: सामान्य संयुक्त ग्राफ के लिए, अनुमान अभी भी पूरी तरह से प्रमाणित नहीं हुआ है
  2. सटीक सूत्र की कमी: kk का nn के सटीक फलन रूप अभी भी अज्ञात है
  3. कम्प्यूटेशनल श्रेणी की सीमा: वर्तमान में केवल n=149n=149 तक की स्थिति की गणना की गई है

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

  1. पूर्ण प्रमाण: Furtula-Oz अनुमान का पूर्ण गणितीय प्रमाण खोजना
  2. स्पर्शोन्मुख व्यवहार: k/nk/n के स्पर्शोन्मुख गुणों और सीमा व्यवहार का अध्ययन करना
  3. एल्गोरिथम अनुकूलन: बड़े nn मानों की स्थिति की गणना के लिए अधिक कुशल एल्गोरिथम विकसित करना
  4. सामान्यीकरण अनुसंधान: विधि को अन्य प्रकार के स्थलीय सूचकांकों के अनुसंधान में सामान्यीकृत करना

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

लाभ

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

कमियां

  1. मुख्य अनुमान पूरी तरह से हल नहीं: हालांकि महत्वपूर्ण समर्थक परिणाम प्रदान करता है, Furtula-Oz अनुमान का पूर्ण प्रमाण अभी भी अनुपस्थित है
  2. तकनीकी गहराई सीमित: मुख्य रूप से अपेक्षाकृत प्राथमिक ग्राफ सिद्धांत तकनीकों का उपयोग करता है, गहरे गणितीय उपकरणों की आवश्यकता हो सकती है
  3. अनुप्रयोग पृष्ठभूमि अपर्याप्त: रासायनिक अनुप्रयोगों में CSZ सूचकांक के विशिष्ट अर्थ पर कम चर्चा

प्रभाव

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

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

इस पेपर की विधि और परिणाम निम्नलिखित के लिए लागू होते हैं:

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

संदर्भ

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