توصيف جميع الرسوم البيانية الخالية من $K_4$ والمدعومة جيداً بالحافة ذات محيط 3

المعلومات الأساسية

• معرّف الورقة: 2511.06095
• العنوان: Characterizing all $K_4$-free well-edge-dominated graphs of girth 3
• المؤلفون: Sarah E. Anderson (جامعة سانت توماس)، Kirsti Kuenzel (كلية ترينيتي)
• التصنيف: math.CO (التوافقيات)
• تاريخ النشر: 11 نوفمبر 2025 (نسخة أولية)
• رابط الورقة: https://arxiv.org/abs/2511.06095

الملخص

تدرس هذه الورقة مشكلة الهيمنة على الحافة في نظرية الرسوم البيانية. بالنسبة لرسم بياني معطى $G$، تُسمى مجموعة الحافات $F$ مجموعة هيمنة على الحافة إذا كانت كل حافة في $G$ إما في $F$ أو مجاورة لحافة ما في $F$. يُقال إن الرسم البياني $G$ مدعوم جيداً بالحافة (well-edge-dominated) إذا كانت جميع مجموعات الهيمنة على الحافة الدنيا متطابقة (أي لها نفس العدد الأساسي). تقوم هذه الورقة، بناءً على الأعمال السابقة، بتوصيف كامل لجميع الرسوم البيانية المدعومة جيداً بالحافة التي تحتوي على مثلثات ولا تحتوي على $K_4$ (الرسم البياني الكامل) كرسم بياني فرعي محفز.

الخلفية البحثية والدافع

المشكلة المراد حلها

تهدف هذه الورقة إلى توصيف كامل للرسوم البيانية التي تستوفي ثلاثة شروط:

1. الدعم الجيد بالحافة (well-edge-dominated)
2. محيط يساوي 3 (أي يحتوي على مثلثات)
3. خالية من $K_4$ (لا تحتوي على $K_4$ كرسم بياني فرعي محفز)

أهمية المشكلة

1. الاكتمال النظري: ترتبط الرسوم البيانية المدعومة جيداً بالحافة ارتباطاً وثيقاً بالرسوم البيانية المتطابقة المتساوية (equimatchable graphs). أي مطابقة قصوى هي مجموعة هيمنة على حافة دنيا، وبالتالي فإن الرسوم البيانية المدعومة جيداً بالحافة يجب أن تكون متطابقة متساوية. التوصيف الكامل للرسوم البيانية المدعومة جيداً بالحافة هو هدف مهم في نظرية البنية الرسومية.
2. البحث التدريجي: هذه المشكلة جزء من خطة بحثية منهجية:
   • 2010: أثبت Frendrup وآخرون أن الرسوم البيانية المتطابقة المتساوية ذات المحيط ≥5 مدعومة جيداً بالحافة
   • 2022: أثبت Anderson وآخرون أن الرسوم البيانية المدعومة جيداً بالحافة غير ثنائية ذات المحيط ≥4 تحتوي على 3 فقط ($C_5, C_7, C_7^*$)
   • 2025: قام Berg وآخرون بتوصيف الرسوم البيانية المدعومة جيداً بالحافة التي تحتوي على مثلث واحد بالضبط
   • هذه الورقة: توصيف جميع الرسوم البيانية المدعومة جيداً بالحافة التي تحتوي على مثلثات وخالية من $K_4$
3. التعقيد الحسابي: على الرغم من وجود خوارزمية زمن متعدد الحدود للتعرف على الرسوم البيانية المتطابقة المتساوية، فإن التوصيف الهيكلي لا يزال مشكلة مفتوحة، وتوفر هذه الورقة تقدماً مهماً في هذا الصدد.

حدود الطرق الموجودة

• تم حل حالة المحيط ≥4 بشكل أساسي، لكن حالة المحيط 3 (التي تحتوي على مثلثات) أكثر تعقيداً بكثير
• لا يمكن توسيع التوصيف الموجود للحالة أحادية المثلث مباشرة إلى حالات متعددة المثلثات
• يتطلب طرقاً بنائية جديدة وتقنيات إثبات للتعامل مع التفاعلات بين مثلثات متعددة

المساهمات الأساسية

1. تعريف ثلاث فئات رسوم بيانية لا نهائية:
   • فئة P (رسوم بيانية المراوح، Propellers): تتكون من مثلثات متعددة ملتصقة عند رأس مشترك
   • فئة W (رسوم بيانية طواحين الهواء، Windmills): تتكون من رسم بياني البيت (house graph) ومثلثات متعددة ملتصقة عند رأس مشترك
   • فئة 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$
• اختر رأساً $v_i$ من كل $T_i$
• الصق جميع $v_i$ في رأس واحد (يسمى "الأنف")

فئة W (طواحين الهواء):

• أضف رسم بياني بيت $H$ إلى أساس فئة P
• يحتوي رسم بياني البيت على مثلث ودورة 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$

قواعد اللصق:

• (أ) الصق أنف $W_i$ برأس قابل للفصل القوي $s_i$
• (ب) الصق أنف $P_i$ برأس قابل للفصل $x_i$
• (ج) الصق أنف $D_i$ (الرأس الخارجي) برأس داعم $y_i$ في $A$

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)$

فإن الرسم البياني $H$ الناتج من لصق $x, y$ مدعوم جيداً بالحافة، و $\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 (الأشكال 3 من $W_1$ إلى $W_{13}$)
• جميع الرسوم البيانية المتصلة المدعومة جيداً بالحافة من الترتيب 8 (الشكل 4 من $V_1$ إلى $V_{12}$)

محتوى التحقق:

1. تعداد جميع الهياكل الرسومية الممكنة
2. فحص الدعم الجيد بالحافة: حساب جميع مجموعات الهيمنة على الحافة الدنيا، التحقق من تطابق العدد الأساسي
3. فحص خاصية الخلو من $K_4$
4. التصنيف إلى فئة البناء المقابلة

الملاحظة الرئيسية (Observation 1)

بالنسبة للرسوم البيانية من الترتيب 7 التي تحتوي على معين: $G \text{ هو رسم بياني مدعوم جيداً بالحافة خالي من } K_4 \Leftrightarrow G \in \{W_1, W_2, W_3, W_4\}$

يوفر هذا أساساً تصنيفياً مهماً للإثبات اللاحق.

نتائج التجربة

تعداد كامل بترتيب صغير

رسوم بيانية من الترتيب 7 (الشكل 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 (الشكل 4):

• إجمالي 12 رسم بياني متصل مدعوم جيداً بالحافة: $V_1$ إلى $V_{12}$
• فقط $V_1, V_2, V_3$ تحتوي على معين
• جميع الرسوم البيانية في $\mathcal{G} \cup \{W_1, W_2, W_3\}$

التحقق من النظرية الرئيسية

البيان الكامل للنظرية 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. الأعمال المبكرة:
   • Lewin (1974)، Meng (1974): تعريف مستقل للرسوم البيانية المتطابقة المتساوية
   • Lesk, Plummer, Pulleyblank (1984): خوارزمية التعرف بزمن متعدد الحدود
2. التوصيف الهيكلي:
   • Sumner (1979, Theorem 1): الرسوم البيانية القابلة للمطابقة العشوائية فقط $K_{2n}$ أو $K_{n,n}$
   • Frendrup وآخرون (2010): توصيف الرسوم البيانية المتطابقة المتساوية ذات المحيط ≥5
   • Büyükçolak وآخرون (2022): الرسوم البيانية المتطابقة المتساوية غير الثنائية التي تحتوي على 4-دورة
3. الرسوم البيانية الثنائية المتطابقة المتساوية:
   • Lemma 1 (الخاصية الرئيسية): إذا كان $G = (A \cup B, E)$ متطابقة متساوية و $|A| < |B|$، فإن كل رأس في $A$ إما رأس داعم أو في $K_{2,2}$

بحث الرسوم البيانية المدعومة جيداً بالحافة

1. حالة المحيط ≥4:
   • Theorem 2 (Anderson وآخرون، 2022): الرسوم البيانية المدعومة جيداً بالحافة ذات المحيط ≥4 إما ثنائية أو واحدة من $\{C_5, C_7, C_7^*\}$
2. حالة المثلث الواحد:
   • Theorem 3 (Berg وآخرون، 2025): الرسوم البيانية المدعومة جيداً بالحافة التي تحتوي على مثلث واحد بالضبط موصوفة بالكامل كـ $\mathcal{T} \cup \mathcal{F} \cup \{K_3, Cr, H, DH\}$
3. مساهمة هذه الورقة: إكمال حالة المحيط 3 والخالية من $K_4$، خطوة مهمة نحو التوصيف الكامل

الأدوات التقنية

• Lemma 3 (Anderson وآخرون، 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. جوهر الرسوم البيانية الاستثنائية: لماذا لا يمكن دمج الرسوم البيانية الاستثنائية الخمسة في إطار موحد، يفتقر إلى شرح متعمق

الاتجاهات المستقبلية

يوضح القسم 3 بوضوح:

"الخطوة الأخيرة لتوصيف جميع الرسوم البيانية المدعومة جيداً بالحافة غير الثنائية ستكون توصيف تلك التي تحتوي على $K_4$ محفز."

الاتجاهات المحددة:

1. حالة احتواء $K_4$: يعتقد المؤلفون أنه يمكن توصيفها من خلال إضافة $K_4$ إلى الرسوم البيانية في $\mathcal{G}$
2. الرسوم البيانية الثنائية المدعومة جيداً بالحافة: توصيف كامل لبنية الرسوم البيانية الثنائية المدعومة جيداً بالحافة
3. تنفيذ الخوارزمية: تصميم خوارزميات أكثر كفاءة بناءً على نتائج التوصيف
4. التعميم: دراسة خصائص الهيمنة على الحافة الأكثر عمومية، مثل الهيمنة على الحافة $k$

التقييم المتعمق

المميزات

1. الاكتمال النظري:
   • حل كامل لحالة الخلو من $K_4$ ذات المحيط 3، ملء فجوة مهمة
   • إثبات صارم، نقاش تصنيفي شامل (الحالات 1-3، لكل منها عدة مستويات من الحالات الفرعية المتداخلة)
   • حجج كاملة في كلا الاتجاهين
2. ابتكار الطريقة:
   • إدخال مفهوم القابلية للفصل القوي، توصيف دقيق لشروط اللصق
   • Lemma 6 توفير إطار بناء وإثبات معياري
   • دمج التحقق الحسابي والإثبات النظري، دعم متبادل
3. وضوح البنية:
   • من البسيط إلى المعقد: $\mathcal{P} \subset \mathcal{W} \subset \mathcal{G}$
   • قواعد البناء واضحة، سهلة التحقق والتطبيق
   • الملحق يسرد تعاريف جميع الفئات بالتفصيل
4. دعم التصور:
   • الأشكال 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 Anderson وآخرون (2022): توصيف الرسوم البيانية المدعومة جيداً بالحافة ذات المحيط ≥4 (أساس Theorem 2)

3 Berg وآخرون (2025): توصيف الرسوم البيانية المدعومة جيداً بالحافة ذات المثلث الواحد (أساس Theorem 3)

5 Büyükçolak وآخرون (2023): خصائص الرسوم البيانية الثنائية المتطابقة المتساوية (Lemma 1)

9 Frendrup وآخرون (2010): الرسوم البيانية المتطابقة المتساوية ذات المحيط ≥5

11 Lesk وآخرون (1984): خوارزمية التعرف على الرسوم البيانية المتطابقة المتساوية بزمن متعدد الحدود

14 Sumner (1979): توصيف الرسوم البيانية القابلة للمطابقة العشوائية (Theorem 1)

التقييم الإجمالي: هذه ورقة عالية الجودة في الرياضيات التوافقية النظرية، تحل بشكل كامل مشكلة توصيف الرسوم البيانية المدعومة جيداً بالحافة الخالية من $K_4$ من خلال نقاش تصنيفي صارم وإثبات بنائي. على الرغم من أن الإثبات معقد ويعتمد على مشكلة الرسوم البيانية الثنائية غير المحلولة، فإنه يحقق مساهمات مهمة في الاكتمال النظري وابتكار الطريقة. إنه تقدم متين في مجال توصيف الرسوم البيانية المدعومة جيداً بالحافة والرسوم البيانية المتطابقة المتساوية.