2025-11-19T15:13:14.550330

Generalized toughness and Q-index in a graph

Zhou
Let $G$ be a graph. We denote by $c(G)$, $α(G)$ and $q(G)$ the number of components, the independence number and the signless Laplacian spectral radius ($Q$-index for short) of $G$, respectively. The toughness of $G$ is defined by $t(G)=\min\left\{\frac{|S|}{c(G-S)}:S\subseteq V(G), c(G-S)\geq2\right\}$ for $G\neq K_n$ and $t(G)=+\infty$ for $G=K_n$. Chen, Gu and Lin [Generalized toughness and spectral radius of graphs, Discrete Math. 349 (2026) 114776] generalized this notion and defined the $l$-toughness $t_l(G)$ of a graph $G$ as $t_l(G)=\min\left\{\frac{|S|}{c(G-S)}:S\subset V(G), c(G-S)\geq l\right\}$ if $2\leq l\leqα(G)$, and $t_l(G)=+\infty$ if $l>α(G)$. If $t_l(G)\geq t$, then $G$ is said to be $(t,l)$-tough. In this paper, we put forward $Q$-index conditions for a graph to be $(b,l)$-tough and $(\frac{1}{b},l)$-tough, respectively.
academic

एक ग्राफ में सामान्यीकृत कठोरता और Q-सूचकांक

मूल जानकारी

  • पेपर ID: 2510.10498
  • शीर्षक: एक ग्राफ में सामान्यीकृत कठोरता और Q-सूचकांक
  • लेखक: Sizhong Zhou (जिआंगसु विज्ञान और प्रौद्योगिकी विश्वविद्यालय, विज्ञान महाविद्यालय)
  • वर्गीकरण: math.CO (संयोजन गणित)
  • प्रकाशन समय: 12 अक्टूबर 2025 (arXiv प्रीप्रिंट)
  • पेपर लिंक: https://arxiv.org/abs/2510.10498

सारांश

यह पेपर ग्राफ की सामान्यीकृत कठोरता और Q-सूचकांक के बीच संबंध का अध्ययन करता है। ग्राफ GG के लिए, c(G)c(G), α(G)\alpha(G) और q(G)q(G) क्रमशः ग्राफ के जुड़े हुए घटकों की संख्या, स्वतंत्र संख्या और अहस्ताक्षरित लाप्लासियन वर्णक्रमीय त्रिज्या (Q-सूचकांक) को दर्शाते हैं। पारंपरिक कठोरता को t(G)=min⁡{∣S∣c(G−S):S⊆V(G),c(G−S)≥2}t(G)=\min\left\{\frac{|S|}{c(G-S)}:S\subseteq V(G), c(G-S)\geq2\right\} के रूप में परिभाषित किया जाता है (G≠KnG\neq K_n के लिए)। Chen, Gu और Lin ने इस अवधारणा को ll-कठोरता में सामान्यीकृत किया: tl(G)=min⁡{∣S∣c(G−S):S⊂V(G),c(G−S)≥l}t_l(G)=\min\left\{\frac{|S|}{c(G-S)}:S\subset V(G), c(G-S)\geq l\right\} (2≤l≤α(G)2\leq l\leq\alpha(G) के लिए)। यह पेपर ग्राफ के (b,l)(b,l)-कठोरता और (1b,l)(\frac{1}{b},l)-कठोरता के लिए Q-सूचकांक पर्याप्त शर्तें प्रस्तावित करता है।

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

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

  1. कठोरता अवधारणा का महत्व: ग्राफ की कठोरता एक महत्वपूर्ण ग्राफ सिद्धांत पैरामीटर है जिसे Chvátal ने 1973 में प्रस्तुत किया था। यह ग्राफ की कनेक्टिविटी और स्थिरता को दर्शाता है, और हैमिल्टनियन चक्र, k-कारक आदि ग्राफ के संरचनात्मक गुणों से निकटता से संबंधित है।
  2. वर्णक्रमीय सिद्धांत का अनुप्रयोग: हाल के वर्षों में, ग्राफ के वर्णक्रमीय पैरामीटर (जैसे वर्णक्रमीय त्रिज्या, लाप्लासियन वर्णक्रमीय त्रिज्या आदि) का उपयोग करके ग्राफ के संरचनात्मक गुणों को दर्शाना एक शोध केंद्रबिंदु बन गया है। वर्णक्रमीय शर्तें अक्सर विशुद्ध संयोजन शर्तों की तुलना में अधिक आसानी से सत्यापित होती हैं।
  3. सामान्यीकृत कठोरता का प्रस्ताव: Chen, Gu और Lin ने हाल ही में पारंपरिक कठोरता को ll-कठोरता अवधारणा में सामान्यीकृत किया है, जो ग्राफ की कठोरता के अध्ययन के लिए एक अधिक लचीली रूपरेखा प्रदान करता है।

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

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

मुख्य योगदान

  1. Q-सूचकांक और (b,l)(b,l)-कठोरता के बीच संबंध स्थापित किया: जुड़े हुए ग्राफ GG के लिए tl(G)≥bt_l(G)\geq b को संतुष्ट करने के लिए Q-सूचकांक की पर्याप्त शर्त दी गई है (प्रमेय 1.1)।
  2. Q-सूचकांक और (1b,l)(\frac{1}{b},l)-कठोरता के बीच संबंध स्थापित किया: जुड़े हुए ग्राफ GG के लिए tl(G)≥1bt_l(G)\geq \frac{1}{b} को संतुष्ट करने के लिए Q-सूचकांक की पर्याप्त शर्त दी गई है (प्रमेय 1.2)।
  3. सटीक चरम ग्राफ की विशेषता प्रदान की: दोनों मुख्य प्रमेयों के लिए, समानता के लिए आवश्यक और पर्याप्त शर्तें दी गई हैं, अर्थात् चरम ग्राफ की संपूर्ण विशेषता।
  4. नई प्रमाण तकनीकें विकसित कीं: भागफल मैट्रिक्स सिद्धांत, ग्राफ के वर्णक्रमीय गुणों और संयोजन अनुकूलन विधियों का उपयोग करके, समान समस्याओं के अनुसंधान के लिए एक तकनीकी ढांचा प्रदान किया।

विधि विवरण

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

इनपुट: जुड़ा हुआ ग्राफ GG, सकारात्मक पूर्णांक b,lb,lआउटपुट: यह निर्धारित करना कि क्या GG (b,l)(b,l)-कठोरता या (1b,l)(\frac{1}{b},l)-कठोरता है बाधा: ग्राफ GG के Q-सूचकांक को विशिष्ट निचली सीमा शर्तों को पूरा करना होगा

मुख्य प्रमेय

प्रमेय 1.1 ((b,l)(b,l)-कठोरता शर्त)

मान लीजिए b≥1b\geq 1, l≥2l\geq 2 पूर्णांक हैं, GG क्रम nn का एक जुड़ा हुआ ग्राफ है, जहां n≥max⁡{(52b2+4b+3)l−b2−2b−5,(2b+1)l2+(2b−3)l+22}n\geq \max\{(\frac{5}{2}b^2+4b+3)l-b^2-2b-5, \frac{(2b+1)l^2+(2b-3)l+2}{2}\}। यदि q(G)≥q(Kbl−1∨(Kn−(b+1)l+2∪(l−1)K1))q(G)\geq q(K_{bl-1}\vee(K_{n-(b+1)l+2}\cup(l-1)K_1)) तो tl(G)≥bt_l(G)\geq b, जब तक कि G=Kbl−1∨(Kn−(b+1)l+2∪(l−1)K1)G=K_{bl-1}\vee(K_{n-(b+1)l+2}\cup(l-1)K_1) न हो।

प्रमेय 1.2 ((1b,l)(\frac{1}{b},l)-कठोरता शर्त)

मान लीजिए b≥2b\geq 2, l≥2l\geq 2 पूर्णांक हैं, GG क्रम nn का एक जुड़ा हुआ ग्राफ है, जहां n≥6b⌈l−1b⌉n\geq 6b\lceil\frac{l-1}{b}\rceil। यदि q(G)≥q(K⌊l−1b⌋∨(Kn−⌊l−1b⌋−l+1∪(l−1)K1))q(G)\geq q(K_{\lfloor\frac{l-1}{b}\rfloor}\vee(K_{n-\lfloor\frac{l-1}{b}\rfloor-l+1}\cup(l-1)K_1)) तो tl(G)≥1bt_l(G)\geq \frac{1}{b}, जब तक कि G=K⌊l−1b⌋∨(Kn−⌊l−1b⌋−l+1∪(l−1)K1)G=K_{\lfloor\frac{l-1}{b}\rfloor}\vee(K_{n-\lfloor\frac{l-1}{b}\rfloor-l+1}\cup(l-1)K_1) न हो।

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

मुख्य लेम्मा

  1. लेम्मा 2.1 (भागफल मैट्रिक्स सिद्धांत): यदि मैट्रिक्स MM के पास समतुल्य विभाजन π\pi है, तो भागफल मैट्रिक्स MπM_\pi के eigenvalues भी MM के eigenvalues हैं।
  2. लेम्मा 2.2 (वर्णक्रमीय एकरसता): यदि HH जुड़े हुए ग्राफ GG का एक उपग्राफ है, तो q(H)≤q(G)q(H)\leq q(G), समानता तब होती है जब H=GH=G हो।
  3. लेम्मा 2.3 (वर्णक्रमीय तुलना): विशिष्ट शर्तों के तहत, कुछ ग्राफ के Q-सूचकांक में कड़ी असमानता संबंध होते हैं।

प्रमाण विचार

  1. विरोधाभास द्वारा ढांचा: मान लीजिए tl(G)<bt_l(G)<b (या <1b<\frac{1}{b}), विरोधाभास खोजें।
  2. चरम ग्राफ का निर्माण: कठोरता शर्त के उल्लंघन के आधार पर, अधिक बड़े Q-सूचकांक वाली विशेष ग्राफ संरचनाएं बनाएं।
  3. वर्गीकृत चर्चा: ग्राफ के क्रम और पैरामीटर संबंधों के अनुसार विस्तृत वर्गीकृत चर्चा।
  4. वर्णक्रमीय अनुमान: भागफल मैट्रिक्स सिद्धांत और वर्णक्रमीय सीमा अनुमान तकनीकों का उपयोग करके प्रमाण पूरा करें।

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

  1. वर्णक्रमीय विधि का सूक्ष्म अनुप्रयोग: अहस्ताक्षरित लाप्लासियन मैट्रिक्स की भागफल मैट्रिक्स संरचना का कुशलतापूर्वक उपयोग किया गया है, समतुल्य विभाजन के माध्यम से eigenvalues की गणना की गई है।
  2. चरम ग्राफ की सटीक विशेषता: न केवल पर्याप्त शर्तें दी गई हैं, बल्कि समानता के मामलों को पूरी तरह से दर्शाया गया है, जो वर्णक्रमीय ग्राफ सिद्धांत में काफी कठिन है।
  3. जटिल पैरामीटर शर्तों का प्रबंधन: कई पैरामीटर (b,l,nb,l,n) से संबंधित जटिल असमानता शर्तों को सफलतापूर्वक संभाला गया है, सटीक सीमाएं दी गई हैं।

प्रारंभिक ज्ञान और लेम्मा

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

  • Q-सूचकांक: q(G)q(G) अहस्ताक्षरित लाप्लासियन मैट्रिक्स Q(G)=D(G)+A(G)Q(G)=D(G)+A(G) का सबसे बड़ा eigenvalue है
  • ll-कठोरता: tl(G)=min⁡{∣S∣c(G−S):S⊂V(G),c(G−S)≥l}t_l(G)=\min\{\frac{|S|}{c(G-S)}:S\subset V(G), c(G-S)\geq l\}
  • ग्राफ का संयोजन: G1∨G2G_1\vee G_2 G1∪G2G_1\cup G_2 के आधार पर V(G1)V(G_1) और V(G2)V(G_2) के बीच सभी किनारों को जोड़ने को दर्शाता है

तकनीकी लेम्मा

पेपर चार मुख्य लेम्मा का उपयोग करता है, जो भागफल मैट्रिक्स सिद्धांत, वर्णक्रमीय एकरसता, ग्राफ परिवर्तन के वर्णक्रमीय प्रभाव और Q-सूचकांक के ऊपरी सीमा अनुमान को कवर करते हैं। ये लेम्मा मुख्य प्रमेयों के प्रमाण के लिए एक ठोस तकनीकी आधार प्रदान करते हैं।

प्रमाण विश्लेषण

प्रमेय 1.1 के प्रमाण की संरचना

प्रमाण विरोधाभास द्वारा उपयोग करता है, मान लीजिए tl(G)<bt_l(G)<b, फिर दो मामलों में विभाजित करता है:

  1. केस 1: n≥(b+1)ω−1n\geq (b+1)\omega-1
  2. केस 2: n≤(b+1)ω−2n\leq (b+1)\omega-2

प्रत्येक मामले में, संबंधित चरम ग्राफ बनाए जाते हैं, और वर्णक्रमीय तुलना के माध्यम से विरोधाभास प्राप्त किया जाता है।

प्रमेय 1.2 के प्रमाण की संरचना

समान रूप से विरोधाभास द्वारा उपयोग करता है, लेकिन वर्गीकरण मानदंड अलग हैं:

  1. केस 1: bs+1≥lbs+1\geq l
  2. केस 2: bs+1<lbs+1<l

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

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

कठोरता सिद्धांत विकास

  1. Chvátal (1973): पहली बार कठोरता अवधारणा प्रस्तुत की, हैमिल्टनियन चक्र के साथ संबंध स्थापित किए
  2. Enomoto आदि (1989): k-कारक के अस्तित्व के लिए कठोरता शर्तें दीं
  3. Liu और Zhang (2008): भिन्नात्मक k-कारक की कठोरता शर्तों का अध्ययन किया

वर्णक्रमीय ग्राफ सिद्धांत अनुप्रयोग

  1. Fan आदि (2023): वर्णक्रमीय त्रिज्या और 1-कठोरता के बीच संबंध स्थापित किए
  2. Jia और Lou (2024): Q-सूचकांक और पारंपरिक कठोरता के बीच संबंध का अध्ययन किया
  3. Zhou (2025): दूरी वर्णक्रमीय त्रिज्या और कठोरता की शर्तें दीं

सामान्यीकृत कठोरता

Chen, Gu और Lin (2026) ने पहली बार ll-कठोरता अवधारणा प्रस्तुत की और सामान्य वर्णक्रमीय त्रिज्या के साथ संबंध स्थापित किए। यह पेपर Q-सूचकांक दिशा में उनके कार्य का एक महत्वपूर्ण विस्तार है।

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

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

  1. Q-सूचकांक और सामान्यीकृत कठोरता के बीच मात्रात्मक संबंध स्थापित किए
  2. दो प्रकार की कठोरता शर्तों की सटीक वर्णक्रमीय विशेषता दी
  3. चरम ग्राफ की संरचना को पूरी तरह से निर्धारित किया

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

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

सीमाएं

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

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

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

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

शक्तियां

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

कमियां

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

प्रभाव

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

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

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

संदर्भ

पेपर 31 संबंधित संदर्भों का हवाला देता है, जो वर्णक्रमीय ग्राफ सिद्धांत, कठोरता सिद्धांत, ग्राफ कारक आदि कई क्षेत्रों के महत्वपूर्ण कार्यों को कवर करता है। यह लेखक के संबंधित क्षेत्रों की गहन समझ और व्यापक ज्ञान को दर्शाता है। विशेष रूप से Chen, Gu और Lin (2026) के कार्य का सीधा विस्तार और पारंपरिक कठोरता सिद्धांत साहित्य का व्यवस्थित संदर्भ उल्लेखनीय है।

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