सभी $K_4$-मुक्त सुसंरचित-किनारा-प्रभुत्व वाले ग्राफ़ को गिर्थ 3 के साथ चिह्नित करना

मूल जानकारी

• पेपर ID: 2511.06095
• शीर्षक: सभी $K_4$-मुक्त सुसंरचित-किनारा-प्रभुत्व वाले ग्राफ़ को गिर्थ 3 के साथ चिह्नित करना
• लेखक: सारा ई. एंडरसन (सेंट थॉमस विश्वविद्यालय), किर्स्टी कुएंजेल (ट्रिनिटी कॉलेज)
• वर्गीकरण: math.CO (संयोजन विज्ञान)
• प्रकाशन तिथि: 11 नवंबर, 2025 (प्रीप्रिंट)
• पेपर लिंक: https://arxiv.org/abs/2511.06095

सारांश

यह पेपर ग्राफ़ सिद्धांत में किनारा प्रभुत्व समस्या का अध्ययन करता है। दिए गए ग्राफ़ $G$ के लिए, किनारों का समुच्चय $F$ को किनारा-प्रभुत्व समुच्चय कहा जाता है, यदि $G$ में सभी किनारे या तो $F$ में हैं या $F$ में किसी किनारे से सटे हुए हैं। यदि ग्राफ़ $G$ के सभी न्यूनतम किनारा-प्रभुत्व समुच्चय न्यूनतम हैं (अर्थात्, समान कार्डिनैलिटी रखते हैं), तो $G$ को सुसंरचित-किनारा-प्रभुत्व वाला ग्राफ़ (well-edge-dominated) कहा जाता है। यह पेपर पूर्ववर्ती कार्य के आधार पर, सभी ग्राफ़ों को पूरी तरह से चिह्नित करता है जिनमें त्रिकोण हैं लेकिन $K_4$ (पूर्ण ग्राफ़) को प्रेरित उपग्राफ़ के रूप में नहीं रखते हैं।

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

समाधान की जाने वाली समस्या

यह पेपर निम्नलिखित तीन शर्तों को संतुष्ट करने वाले ग्राफ़ों को पूरी तरह से चिह्नित करने का लक्ष्य रखता है:

1. सुसंरचित-किनारा-प्रभुत्व (well-edge-dominated)
2. गिर्थ 3 (अर्थात्, त्रिकोण युक्त)
3. $K_4$-मुक्त (प्रेरित उपग्राफ़ के रूप में $K_4$ नहीं रखता)

समस्या का महत्व

1. सैद्धांतिक पूर्णता: सुसंरचित-किनारा-प्रभुत्व वाले ग्राफ़ समान-मिलान योग्य ग्राफ़ (equimatchable graphs) से घनिष्ठ रूप से संबंधित हैं। कोई भी अधिकतम मिलान न्यूनतम किनारा-प्रभुत्व समुच्चय है, इसलिए सुसंरचित-किनारा-प्रभुत्व वाले ग्राफ़ आवश्यक रूप से समान-मिलान योग्य हैं। सुसंरचित-किनारा-प्रभुत्व वाले ग्राफ़ों का पूर्ण चिह्नीकरण ग्राफ़ सिद्धांत संरचना सिद्धांत का एक महत्वपूर्ण लक्ष्य है।
2. क्रमिक अनुसंधान: यह समस्या एक व्यवस्थित अनुसंधान योजना का हिस्सा है:
   • 2010: फ्रेंड्रप आदि ने साबित किया कि गिर्थ ≥5 वाले समान-मिलान योग्य ग्राफ़ सुसंरचित-किनारा-प्रभुत्व वाले हैं
   • 2022: एंडरसन आदि ने साबित किया कि गिर्थ ≥4 वाले गैर-द्विपक्षीय सुसंरचित-किनारा-प्रभुत्व वाले ग्राफ़ केवल 3 हैं ($C_5, C_7, C_7^*$)
   • 2025: बर्ग आदि ने बिल्कुल एक त्रिकोण वाले सुसंरचित-किनारा-प्रभुत्व वाले ग्राफ़ों को चिह्नित किया
   • यह पेपर: त्रिकोण युक्त और $K_4$-मुक्त सभी सुसंरचित-किनारा-प्रभुत्व वाले ग्राफ़ों को चिह्नित करता है
3. कम्प्यूटेशनल जटिलता: हालांकि समान-मिलान योग्य ग्राफ़ों को पहचानने के लिए बहुपद समय एल्गोरिदम मौजूद है, संरचना चिह्नीकरण अभी भी एक खुली समस्या है, यह पेपर इसमें महत्वपूर्ण प्रगति प्रदान करता है।

मौजूदा तरीकों की सीमाएं

• गिर्थ ≥4 की स्थिति मुख्य रूप से हल हो गई है, लेकिन गिर्थ 3 (त्रिकोण युक्त) की स्थिति बहुत अधिक जटिल है
• पहले से ज्ञात एकल त्रिकोण चिह्नीकरण को सीधे कई त्रिकोणों की स्थिति में नहीं बढ़ाया जा सकता है
• कई त्रिकोणों की परस्पर क्रिया को संभालने के लिए नई निर्माण विधियों और प्रमाण तकनीकों की आवश्यकता है

मुख्य योगदान

1. तीन अनंत ग्राफ़ वर्गों को परिभाषित किया:
   • P वर्ग (प्रोपेलर ग्राफ़, Propellers): एक सामान्य शीर्ष पर कई त्रिकोणों को चिपकाकर बनाया गया
   • W वर्ग (विंडमिल ग्राफ़, Windmills): हाउस ग्राफ़ और कई त्रिकोणों को सामान्य शीर्ष पर चिपकाकर बनाया गया
   • G वर्ग: सबसे सामान्य निर्माण वर्ग, सुसंरचित-किनारा-प्रभुत्व वाले द्विपक्षीय ग्राफ़ को प्रोपेलर, विंडमिल, हीरे आदि घटकों के साथ विशिष्ट नियमों के अनुसार चिपकाकर बनाया गया
2. मुख्य प्रमेय (Theorem 4): $K_4$-मुक्त सुसंरचित-किनारा-प्रभुत्व वाले ग्राफ़ों को पूरी तरह से चिह्नित करता है: $G \text{ है } K_4\text{-मुक्त सुसंरचित-किनारा-प्रभुत्व वाला ग्राफ़ और गिर्थ 3} \Leftrightarrow G \in \mathcal{G} \cup \{DH, F_5, Cr, W_1, W_2, W_3\}$ जहां $DH$ (ड्रीम हाउस), $Cr$ (क्रिस्टल ग्राफ़), $F_5$ (5-शीर्ष पंखा), $W_1, W_2, W_3$ पांच अपवाद ग्राफ़ हैं।
3. सभी निर्मित ग्राफ़ों की सुसंरचित-किनारा-प्रभुत्व साबित की:
   • P वर्ग और W वर्ग के सभी सदस्यों की सुसंरचित-किनारा-प्रभुत्व साबित की (Lemma 5)
   • G वर्ग के सभी सदस्यों की सुसंरचित-किनारा-प्रभुत्व साबित की (Corollary 1)
4. पूर्णता प्रमाण: विस्तृत वर्गीकरण चर्चा और आगमनात्मक तर्क के माध्यम से, साबित किया कि सभी $K_4$-मुक्त सुसंरचित-किनारा-प्रभुत्व वाले ग्राफ़ उपरोक्त वर्गीकरण में हैं।
5. कम्प्यूटेशनल सत्यापन: Sage सॉफ्टवेयर का उपयोग करके सभी 7-8 क्रम के जुड़े हुए सुसंरचित-किनारा-प्रभुत्व वाले ग्राफ़ों को सत्यापित किया, जो सैद्धांतिक प्रमाण के लिए आधार प्रदान करता है।

विधि विवरण

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

इनपुट: ग्राफ़ $G = (V(G), E(G))$

उद्देश्य: यह निर्धारित करना कि क्या $G$ निम्नलिखित को संतुष्ट करता है:

1. सुसंरचित-किनारा-प्रभुत्व: $\gamma'(G) = \Gamma'(G)$ (सभी न्यूनतम किनारा-प्रभुत्व समुच्चयों की कार्डिनैलिटी समान है)
2. गिर्थ 3: त्रिकोण (3-चक्र) मौजूद है
3. $K_4$-मुक्त: प्रेरित उपग्राफ़ के रूप में $K_4$ नहीं रखता

आउटपुट: यदि संतुष्ट है, तो निर्धारित करें कि $G$ किस निर्माण वर्ग से संबंधित है

मुख्य निर्माण विधि

1. आधार ग्राफ़ वर्ग परिभाषा

P वर्ग (प्रोपेलर):

• $k$ असंयुक्त त्रिकोण $T_1, \ldots, T_k$ लें
• प्रत्येक $T_i$ से एक शीर्ष $v_i$ चुनें
• सभी $v_i$ को एक एकल शीर्ष में चिपकाएं (जिसे "नाक" कहा जाता है)

W वर्ग (विंडमिल):

• P वर्ग के आधार पर एक हाउस ग्राफ़ $H$ जोड़ें
• हाउस ग्राफ़ में एक त्रिकोण और एक 4-चक्र होता है
• हाउस ग्राफ़ के त्रिकोण पर डिग्री 2 वाले शीर्ष को प्रोपेलर की नाक के साथ चिपकाएं

G वर्ग (सामान्य निर्माण): निम्नलिखित घटकों से शुरू करें:

• $G' = (A \cup B, E')$: जुड़ा हुआ गैर-तुच्छ द्विपक्षीय सुसंरचित-किनारा-प्रभुत्व वाला ग्राफ़, $|A| < |B|$
• $W_1, \ldots, W_k$: विंडमिल
• $P_1, \ldots, P_r$: प्रोपेलर
• $D_1, \ldots, D_\ell$: हीरे ($K_4 - e$)

$B' \subset B$ चुनें ताकि $G' - B'$ सुसंरचित-किनारा-प्रभुत्व वाला हो और कोई तुच्छ शाखा न हो। $B' = \{s_1, \ldots, s_k, x_1, \ldots, x_r\}$ को विभाजित करें:

• दृढ़ता से अलग करने योग्य शीर्ष $s_i$: $G' - B'$ में इसके सभी पड़ोसी समर्थन शीर्ष हैं
• अलग करने योग्य शीर्ष $x_i$

चिपकाने के नियम:

• (a) $W_i$ की नाक को दृढ़ता से अलग करने योग्य शीर्ष $s_i$ के साथ चिपकाएं
• (b) $P_i$ की नाक को अलग करने योग्य शीर्ष $x_i$ के साथ चिपकाएं
• (c) $D_i$ की नाक (बाहरी शीर्ष) को $A$ में समर्थन शीर्ष $y_i$ के साथ चिपकाएं

2. सुसंरचित-किनारा-प्रभुत्व प्रमाण रणनीति

Lemma 6 (मुख्य लेम्मा): यदि $G_1, G_2$ सुसंरचित-किनारा-प्रभुत्व वाले ग्राफ़ हैं, $x \in V(G_1), y \in V(G_2)$ निम्नलिखित को संतुष्ट करते हैं:

• $G_1 - x$ सुसंरचित-किनारा-प्रभुत्व वाला है और $\gamma'(G_1 - x) = \gamma'(G_1)$
• $G_2 - y$ सुसंरचित-किनारा-प्रभुत्व वाला है और $\gamma'(G_2 - y) = \gamma'(G_2)$

तो $x, y$ को चिपकाकर प्राप्त ग्राफ़ $H$ सुसंरचित-किनारा-प्रभुत्व वाला है, और $\gamma'(H) = \gamma'(G_1) + \gamma'(G_2)$

प्रमाण विचार: किसी भी न्यूनतम किनारा-प्रभुत्व समुच्चय $F$ के लिए, साबित करें कि $F \cap E(G_1 - x)$ और $F \cap E(G_2 - y)$ क्रमशः संबंधित उपग्राफ़ के न्यूनतम किनारा-प्रभुत्व समुच्चय हैं, इसलिए कार्डिनैलिटी निश्चित है।

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

1. पुनरावर्ती निर्माण ढांचा: Lemma 6 को बार-बार लागू करके, जटिल ग्राफ़ों को सरल घटकों के चिपकाने में विघटित करें
2. अलग करने योग्यता अवधारणा: दृढ़ता से अलग करने योग्य और सामान्य अलग करने योग्य के बीच अंतर पेश करें, यह सटीक रूप से चिह्नित करें कि कौन से शीर्ष चिपकाने के लिए उपयोग किए जा सकते हैं
3. वर्गीकरण चर्चा रणनीति:
   • ग्राफ़ के क्रम द्वारा आगमन
   • हीरे युक्त होने या न होने से वर्गीकृत करें
   • त्रिकोणों की स्थिति (प्रोपेलर/विंडमिल/हीरे) द्वारा वर्गीकृत करें
   • शीर्ष से त्रिकोण की दूरी द्वारा संकुचन किनारे चुनें
4. Sage कम्प्यूटेशनल सहायता: कंप्यूटर का उपयोग करके छोटे क्रम के मामलों ($n \leq 8$) की गणना करें, बड़े क्रम के आगमन के लिए आधार प्रदान करें
5. Lemma 7 की संरचना चिह्नीकरण: विशेष स्थलाकृति संरचना (स्वतंत्र समुच्चय + त्रिकोण + कनेक्शन समुच्चय) के लिए पूर्ण चिह्नीकरण दें

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

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

उपकरण: Sage गणितीय सॉफ्टवेयर

सत्यापन सीमा:

• सभी 7-क्रम जुड़े हुए सुसंरचित-किनारा-प्रभुत्व वाले ग्राफ़ (Figure 3 में $W_1$ से $W_{13}$)
• सभी 8-क्रम जुड़े हुए सुसंरचित-किनारा-प्रभुत्व वाले ग्राफ़ (Figure 4 में $V_1$ से $V_{12}$)

सत्यापन सामग्री:

1. सभी संभावित ग्राफ़ संरचनाओं की गणना करें
2. सुसंरचित-किनारा-प्रभुत्व की जांच करें: सभी न्यूनतम किनारा-प्रभुत्व समुच्चयों की गणना करें, कार्डिनैलिटी समान है यह सत्यापित करें
3. $K_4$-मुक्त संपत्ति की जांच करें
4. संबंधित निर्माण वर्ग में वर्गीकृत करें

मुख्य अवलोकन (Observation 1)

7-क्रम हीरे युक्त ग्राफ़ के लिए: $G \text{ है } K_4\text{-मुक्त सुसंरचित-किनारा-प्रभुत्व वाला ग्राफ़} \Leftrightarrow G \in \{W_1, W_2, W_3, W_4\}$

यह बाद के प्रमाण के लिए महत्वपूर्ण वर्गीकरण आधार प्रदान करता है।

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

छोटे क्रम की पूर्ण गणना

7-क्रम ग्राफ़ (Figure 3):

• कुल 13 जुड़े हुए सुसंरचित-किनारा-प्रभुत्व वाले ग्राफ़: $W_1$ से $W_{13}$
• जिनमें से $W_1, W_2, W_3$ हीरे युक्त हैं लेकिन G वर्ग में नहीं हैं (अपवाद ग्राफ़)
• $W_4$ हीरे युक्त है लेकिन G वर्ग में है (3 लटकते किनारों वाला हीरा)
• $W_{10} \cong DH$ (ड्रीम हाउस), $W_{12} \cong Cr$ (क्रिस्टल ग्राफ़)
• बाकी सभी $\mathcal{G}$ में हैं

8-क्रम ग्राफ़ (Figure 4):

• कुल 12 जुड़े हुए सुसंरचित-किनारा-प्रभुत्व वाले ग्राफ़: $V_1$ से $V_{12}$
• केवल $V_1, V_2, V_3$ हीरे युक्त हैं
• सभी ग्राफ़ $\mathcal{G} \cup \{W_1, W_2, W_3\}$ में हैं

मुख्य प्रमेय सत्यापन

Theorem 4 की पूर्ण कथन: यदि $G$ एक $K_4$-मुक्त ग्राफ़ है, तो $G \text{ सुसंरचित-किनारा-प्रभुत्व वाला है और गिर्थ 3} \Leftrightarrow G \in \mathcal{G} \cup \{DH, F_5, Cr, W_1, W_2, W_3\}$

प्रमाण संरचना:

1. अग्रगामी (Corollary 1): $\mathcal{G}$ में सभी ग्राफ़ सुसंरचित-किनारा-प्रभुत्व वाले हैं
2. पश्चगामी: मान लें कि एक न्यूनतम प्रतिउदाहरण मौजूद है, निम्नलिखित चरणों के माध्यम से विरोधाभास प्राप्त करें:
   • यदि केवल एक त्रिकोण है, तो Theorem 3 द्वारा वर्गीकरण में है
   • यदि $n(G) \leq 8$, तो Sage सत्यापन द्वारा वर्गीकरण में है
   • यदि $n(G) \geq 9$, तो उपयुक्त किनारे $st$ चुनें, $G' = G - N_e[st]$ पर विचार करें
   • $G'$ की विभिन्न संभावनाओं (किस वर्ग से संबंधित है) के लिए विस्तृत वर्गीकरण चर्चा करें
   • प्रत्येक स्थिति $G \in \mathcal{G}$ या विरोधाभास तक पहुंचाती है

मुख्य लेम्मा का अनुप्रयोग

Lemma 7: विशिष्ट स्थलाकृति संरचना (स्वतंत्र समुच्चय $I$, कनेक्शन समुच्चय $S$, त्रिकोण $xyz$) को संतुष्ट करने वाले ग्राफ़ के लिए, पूरी तरह से चिह्नित करें: $G \in \{Cr, H\} \cup \mathcal{K} \cup \mathcal{P} \cup \mathcal{R} \cup \mathcal{W}$

जहां $\mathcal{K}$ (पतंग), $\mathcal{R}$ $\mathcal{G}$ के उप-वर्ग हैं।

प्रमाण विधि:

• न्यूनतम प्रतिउदाहरण चुनें
• $I$ खाली है या नहीं इसके अनुसार वर्गीकृत करें
• $S$ स्वतंत्र है या नहीं इसके अनुसार वर्गीकृत करें
• किनारे हटाने के आगमन और विरोधाभास तर्क के माध्यम से

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

समान-मिलान योग्य ग्राफ़ अनुसंधान

1. प्रारंभिक कार्य:
   • लेविन (1974), मेंग (1974): स्वतंत्र रूप से समान-मिलान योग्य ग्राफ़ को परिभाषित करें
   • लेस्क, प्लम्मर, पुलेब्लैंक (1984): बहुपद समय पहचान एल्गोरिदम
2. संरचना चिह्नीकरण:
   • समनर (1979, Theorem 1): यादृच्छिक रूप से मिलान योग्य ग्राफ़ केवल $K_{2n}$ या $K_{n,n}$ हैं
   • फ्रेंड्रप आदि (2010): गिर्थ ≥5 वाले समान-मिलान योग्य ग्राफ़ चिह्नीकरण
   • बुयुकचोलक आदि (2022): 4-चक्र युक्त गैर-द्विपक्षीय समान-मिलान योग्य ग्राफ़
3. द्विपक्षीय समान-मिलान योग्य ग्राफ़:
   • Lemma 1 (मुख्य संपत्ति): यदि $G = (A \cup B, E)$ समान-मिलान योग्य है और $|A| < |B|$, तो $A$ में प्रत्येक शीर्ष या तो समर्थन शीर्ष है, या $K_{2,2}$ में है

सुसंरचित-किनारा-प्रभुत्व वाले ग्राफ़ अनुसंधान

1. गिर्थ ≥4 की स्थिति:
   • Theorem 2 (एंडरसन आदि, 2022): गिर्थ ≥4 वाले सुसंरचित-किनारा-प्रभुत्व वाले ग्राफ़ या तो द्विपक्षीय हैं, या $\{C_5, C_7, C_7^*\}$ में से एक हैं
2. एकल त्रिकोण की स्थिति:
   • Theorem 3 (बर्ग आदि, 2025): बिल्कुल एक त्रिकोण वाले सुसंरचित-किनारा-प्रभुत्व वाले ग्राफ़ पूरी तरह से चिह्नित हैं $\mathcal{T} \cup \mathcal{F} \cup \{K_3, Cr, H, DH\}$ के रूप में
3. यह पेपर का योगदान: गिर्थ 3 और $K_4$-मुक्त की स्थिति को पूरा करता है, पूर्ण चिह्नीकरण की ओर महत्वपूर्ण कदम

तकनीकी उपकरण

• Lemma 3 (एंडरसन आदि, 2022): यदि $M$ मिलान है, $G$ सुसंरचित-किनारा-प्रभुत्व वाला है, तो $G - N_e[M]$ सुसंरचित-किनारा-प्रभुत्व वाला है
• Lemma 4: यदि $y \in A$ समर्थन शीर्ष नहीं है, तो $y$ से संबंधित किनारे के बिना न्यूनतम किनारा-प्रभुत्व समुच्चय मौजूद है

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

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

1. पूर्ण वर्गीकरण: सभी $K_4$-मुक्त, गिर्थ 3 वाले सुसंरचित-किनारा-प्रभुत्व वाले ग्राफ़ निम्नलिखित से संबंधित हैं:
   • अनंत वर्ग $\mathcal{G}$ (उप-वर्ग $\mathcal{P}, \mathcal{W}, \mathcal{K}, \mathcal{R}$ युक्त)
   • 5 परिमित अपवाद: $DH, F_5, Cr, W_1, W_2, W_3$
2. निर्माण विधि: सुसंरचित-किनारा-प्रभुत्व वाले द्विपक्षीय ग्राफ़ से शुरू करके, चिपकाने की क्रिया के माध्यम से सभी संभावित ग्राफ़ों को उत्पन्न करने के लिए एक व्यवस्थित ढांचा प्रदान करता है
3. आवश्यकता और पर्याप्तता: सभी निर्मित ग्राफ़ सुसंरचित-किनारा-प्रभुत्व वाले हैं (पर्याप्तता) साबित किया, और सभी संतुष्ट ग्राफ़ निर्माण में हैं (आवश्यकता) साबित किया

सीमाएं

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

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

Section 3 स्पष्ट रूप से बताता है:

"सभी गैर-द्विपक्षीय, सुसंरचित-किनारा-प्रभुत्व वाले ग्राफ़ों को चिह्नित करने का अंतिम कदम प्रेरित $K_4$ युक्त ग्राफ़ों को चिह्नित करना होगा।"

विशिष्ट दिशाएं:

1. $K_4$ युक्त स्थिति: लेखकों का विश्वास है कि $\mathcal{G}$ में ग्राफ़ पर $K_4$ जोड़कर चिह्नित किया जा सकता है
2. द्विपक्षीय सुसंरचित-किनारा-प्रभुत्व वाले ग्राफ़: सुसंरचित-किनारा-प्रभुत्व वाले द्विपक्षीय ग्राफ़ की संरचना को पूरी तरह से चिह्नित करें
3. एल्गोरिदम कार्यान्वयन: चिह्नीकरण परिणामों के आधार पर अधिक कुशल पहचान एल्गोरिदम डिजाइन करें
4. सामान्यीकरण: अधिक सामान्य किनारा-प्रभुत्व गुणों का अध्ययन करें, जैसे $k$-किनारा-प्रभुत्व

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

लाभ

1. सैद्धांतिक पूर्णता:
   • $K_4$-मुक्त गिर्थ 3 की स्थिति को पूरी तरह से हल करता है, महत्वपूर्ण रिक्त स्थान भरता है
   • प्रमाण कठोर है, वर्गीकरण चर्चा विस्तृत है (Case 1-3, प्रत्येक में कई स्तरीय उप-मामले)
   • आगे और पीछे दोनों दिशाएं पूर्ण तर्क प्रदान करती हैं
2. विधि नवाचार:
   • दृढ़ता से अलग करने योग्य अवधारणा पेश करता है, चिपकाने की स्थितियों को सटीक रूप से चिह्नित करता है
   • Lemma 6 मॉड्यूलर निर्माण और प्रमाण ढांचा प्रदान करता है
   • कम्प्यूटेशनल सत्यापन और सैद्धांतिक प्रमाण को जोड़ता है, एक दूसरे को समर्थन देते हैं
3. संरचना स्पष्टता:
   • सरल से जटिल: $\mathcal{P} \subset \mathcal{W} \subset \mathcal{G}$
   • निर्माण नियम स्पष्ट हैं, सत्यापन और अनुप्रयोग में आसान
   • परिशिष्ट सभी वर्गों की परिभाषाएं विस्तार से सूचीबद्ध करता है
4. दृश्य समर्थन:
   • Figure 1-4 मुख्य ग्राफ़ों का सहज प्रदर्शन प्रदान करते हैं
   • सभी 7-8 क्रम ग्राफ़ों की पूर्ण गणना विश्वसनीयता बढ़ाती है

कमियां

1. प्रमाण जटिलता:
   • Theorem 4 का प्रमाण 12 पृष्ठ लंबा है (पृष्ठ 12-24), वर्गीकरण चर्चा अत्यंत जटिल है
   • कुछ स्थितियों का तर्क कई पूर्व-शर्त लेम्मा पर निर्भर करता है, ट्रैकिंग कठिन है
   • पठनीयता प्रभावित होती है, मुख्य विचार को तेजी से समझना मुश्किल है
2. अपवाद ग्राफ़ हैंडलिंग:
   • 5 अपवाद ग्राफ़ों का दिखना अचानक है, एकीकृत व्याख्या की कमी है
   • क्यों $W_1, W_2, W_3$ को $\mathcal{G}$ में नहीं रखा जा सकता? सैद्धांतिक कारण पर्याप्त स्पष्ट नहीं है
3. द्विपक्षीय ग्राफ़ ब्लैक बॉक्स:
   • निर्माण सुसंरचित-किनारा-प्रभुत्व वाले द्विपक्षीय ग्राफ़ पर गहराई से निर्भर करता है, लेकिन बाद वाले की संरचना अज्ञात है
   • यह निर्माण को "स्पष्ट" नहीं बनाता है, अनुप्रयोग सीमित है
4. कम्प्यूटेशनल विवरण की कमी:
   • Sage सत्यापन का विशिष्ट कोड और एल्गोरिदम प्रदान नहीं किया गया है
   • कम्प्यूटेशनल परिणामों को स्वतंत्र रूप से पुनरुत्पादित नहीं किया जा सकता है
   • कम्प्यूटेशनल जटिलता का विश्लेषण नहीं किया गया है
5. सामान्यीकरण चर्चा अपर्याप्त:
   • क्या विधि $K_4$ युक्त स्थिति तक विस्तारित हो सकती है?
   • अन्य ग्राफ़ वर्गों (जैसे समतल ग्राफ़, पंजा-मुक्त ग्राफ़) के साथ संबंध?

प्रभाव

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

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

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

संदर्भ

मुख्य उद्धरण:

2 एंडरसन आदि (2022): गिर्थ ≥4 वाले सुसंरचित-किनारा-प्रभुत्व वाले ग्राफ़ चिह्नीकरण (Theorem 2 आधार)

3 बर्ग आदि (2025): एकल त्रिकोण सुसंरचित-किनारा-प्रभुत्व वाले ग्राफ़ चिह्नीकरण (Theorem 3 आधार)

5 बुयुकचोलक आदि (2023): समान-मिलान योग्य द्विपक्षीय ग्राफ़ गुण (Lemma 1)

9 फ्रेंड्रप आदि (2010): गिर्थ ≥5 वाले समान-मिलान योग्य ग्राफ़

11 लेस्क आदि (1984): समान-मिलान योग्य ग्राफ़ बहुपद पहचान एल्गोरिदम

14 समनर (1979): यादृच्छिक रूप से मिलान योग्य ग्राफ़ चिह्नीकरण (Theorem 1)

समग्र मूल्यांकन: यह एक उच्च-गुणवत्ता वाला संयोजन गणित सैद्धांतिक पेपर है, जो कठोर वर्गीकरण चर्चा और निर्माणात्मक प्रमाण के माध्यम से, $K_4$-मुक्त सुसंरचित-किनारा-प्रभुत्व वाले ग्राफ़ों की चिह्नीकरण समस्या को पूरी तरह से हल करता है। हालांकि प्रमाण जटिल है और अनसुलझी द्विपक्षीय ग्राफ़ समस्या पर निर्भर करता है, लेकिन सैद्धांतिक पूर्णता और विधि नवाचार दोनों में महत्वपूर्ण योगदान है। सुसंरचित-किनारा-प्रभुत्व वाले ग्राफ़ और समान-मिलान योग्य ग्राफ़ों के पूर्ण चिह्नीकरण को आगे बढ़ाने के लिए महत्वपूर्ण है, यह क्षेत्र में ठोस प्रगति है।