رقم الترابط المستقل في الرسوم البيانية تحت قيود محيط الدورة

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

• معرّف الورقة: 2411.01687
• العنوان: Independent Bondage Number in Graphs under Girth Constraints
• المؤلفون: E.G.K.M. Gamlath, Andrew Pham, Bing Wei
• التصنيف: math.CO (الرياضيات التوافقية)
• تاريخ النشر: 15 أكتوبر 2025 (نسخة أولية من arXiv)
• رابط الورقة: https://arxiv.org/abs/2411.01687

الملخص

بالنظر إلى رسم بياني بسيط محدود $G$، فإن رقم الترابط المستقل (independent bondage number) للرسم البياني $G$ هو حجم أصغر مجموعة حافة بحيث يكون للرسم البياني الناتج عن حذفها رقم هيمنة مستقل أكبر بشكل صارم من $G$. على الرغم من أن رقم الترابط في الرسوم البيانية تحت قيود محيط الدورة قد تمت دراسته، إلا أن النتائج المتعلقة برقم الترابط المستقل لا تزال نادرة جداً. تؤسس هذه الدراسة حدوداً عليا لرقم الترابط المستقل في الرسوم البيانية المستوية تحت قيود محيط الدورة المعطاة، مما يوسع نتائج Fischermann و Rautenbach و Volkmann بشأن رقم الترابط ونتائج Borodin و Ivanova حول بنية الرسوم البيانية المستوية. على وجه الخصوص، تم تحديد هياكل إضافية وتأسيس حدود لرقم الترابط المستقل للرسوم البيانية المستوية التي تحقق $\delta(G) \geq 2$ و $g(G) \geq 5$، و $\delta(G) \geq 3$ و $g(G) \geq 4$، و $\delta(G) \geq 2$ و $g(G) \geq 10$.

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

تعريف المشكلة والأهمية

1. المفاهيم الأساسية:
   • مجموعة الهيمنة المستقلة: مجموعة رؤوس تكون مستقلة وهيمنة في نفس الوقت
   • رقم الهيمنة المستقل $\gamma_i(G)$: أساس أصغر مجموعة هيمنة مستقلة
   • رقم الترابط المستقل $b_i(G)$: حجم أصغر مجموعة حافة $B$ بحيث $\gamma_i(G-B) > \gamma_i(G)$
2. أهمية البحث:
   • قياس هشاشة بنية الهيمنة المستقلة في الشبكات عند فشل الحواف
   • ذات قيمة تطبيقية مهمة في تحليل فشل الروابط في الشبكات المترابطة
   • توسيع نطاق البحث في نظرية الهيمنة الكلاسيكية
3. القيود في البحث الحالي:
   • رقم الترابط التقليدي $b(G)$ قد تمت دراسته بشكل منهجي تحت قيود محيط الدورة
   • النتائج المتعلقة برقم الترابط المستقل $b_i(G)$ محدودة جداً، خاصة تحت قيود محيط الدورة
   • نقص النتائج ذات الحد الثابت للفئات الرسومية المحددة
4. الدافع البحثي:
   • مستوحى من نتائج Fischermann وآخرين (2003) حول قيود محيط الدورة لرقم الترابط في الرسوم البيانية المستوية
   • استكشاف طبيعي لما إذا كان رقم الترابط المستقل يمكن أن يحقق أيضاً حدوداً ثابتة مماثلة تحت قيود محيط الدورة
   • ملء الفجوات في البحث النظري لرقم الترابط المستقل

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

1. تأسيس أربعة نظريات حد أعلى رئيسية:
   • عندما $\delta(G) \geq 3$ و $g(G) \geq 4$: $b_i(G) \leq 6$
   • عندما $\delta(G) \geq 2$ و $g(G) \geq 5$: $b_i(G) \leq 5$
   • عندما $\delta(G) \geq 2$ و $g(G) \geq 7$: $b_i(G) \leq 4$
   • عندما $\delta(G) \geq 2$ و $g(G) \geq 10$: $b_i(G) \leq 3$
2. تحديد تكوينات هياكل رسومية حرجة متعددة:
   • لـ $\delta(G) \geq 2$ و $g(G) \geq 5$: تحديد 10 تكوينات حتمية
   • لـ $\delta(G) \geq 3$ و $g(G) \geq 4$: تحديد 3 تكوينات حرجة
   • بناء مجموعات ترابط مستقل مقابلة لكل تكوين
3. توسيع الإطار النظري الموجود:
   • تعميم نتائج Fischermann وآخرين حول الترابط إلى الترابط المستقل
   • الاستفادة من وتطوير نظرية بنية الرسوم البيانية المستوية لـ Borodin و Ivanova
4. توفير طريقة إثبات منهجية:
   • استخدام طريقة التفريغ (discharging method) لتحديد الهياكل الحتمية
   • توفير إثبات بناء لمجموعة ترابط مستقل لكل هيكل

شرح تفصيلي للطريقة

الأساس النظري

نظام التعريفات:

• رقم الترابط المستقل للرسم البياني $G$: $b_i(G) = \min\{|B| : B \subseteq E(G), \gamma_i(G-B) > \gamma_i(G)\}$
• محيط الدورة $g(G)$: طول أقصر دورة في الرسم البياني
• الحد الأدنى للدرجة $\delta(G)$: الحد الأدنى لدرجة الرؤوس في الرسم البياني

اللمة الرئيسية:

النظرية 1 (Priddy, Wang, Wei): بالنسبة للرسم البياني غير الفارغ G،
b_i(G) ≤ min{d(u) + d(v) - |N(u) ∩ N(v)| - 1 : uv ∈ E(G)}

الطريقة الأساسية: تقنية التفريغ

مبدأ طريقة التفريغ:

1. توزيع الشحنة الأولي: توزيع الشحنة وفقاً لثلاث طرق طبيعية من صيغة أويلر
   • شحنة الرأس: $d(v) - 6$، شحنة الوجه: $2\ell(f) - 6$ (تفريغ الرأس)
   • شحنة الرأس: $2d(v) - 6$، شحنة الوجه: $\ell(f) - 6$ (تفريغ الوجه)
   • شحنة الرأس: $d(v) - 4$، شحنة الوجه: $\ell(f) - 4$ (التفريغ المتوازن)
2. قواعد إعادة توزيع الشحنة: تصميم قواعد محددة لتدفق الشحنة من رؤوس/وجوه موجبة الشحنة إلى رؤوس/وجوه سالبة الشحنة
3. تحديد الهيكل: من خلال تحليل توزيع الشحنة النهائي، إثبات حتمية بعض الهياكل

استراتيجية التنفيذ المحددة

للحالة $\delta(G) \geq 2$ و $g(G) \geq 5$:

قواعد التفريغ:

• (R1) كل رأس من الدرجة 2 يأخذ $\frac{1}{2}$ شحنة من كل رأس مجاور وكل وجه مرتبط
• (R2) كل رأس من الدرجة 3 يأخذ $\frac{1}{3}$ شحنة من كل وجه مرتبط
• (R3) قواعد توزيع الشحنة لرؤوس درجة 6 محددة
• (R4) قواعد توزيع الشحنة لرؤوس درجة 5 محددة

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

• الحقيقة 1: كل رأس بدرجة ≤4 له شحنة نهائية تساوي 0
• الحقيقة 2: استبعادية توزيع الشحنة لرؤوس درجة 5+
• الحقائق 3-8: ضمان عدم سلبية الشحنة لمختلف الرؤوس والوجوه

النتائج الرئيسية

النظرية 7: توصيف الهيكل لـ $\delta(G) \geq 2$ و $g(G) \geq 5$

كل رسم بياني مستوي يحقق الشروط يجب أن يحتوي على أحد التكوينات التالية:

• (a) حافة $(2,4^-)$ أو حافة $(3,3^-)$
• (b) رأس $v \in S(5^+, [d(v)-1]^+)$ حيث الجيران المتبقون هم رؤوس من الدرجة 4 أو رؤوس في $S(5^+,1^+)$
• (c)-(j) ثمانية تكوينات معقدة تتضمن رؤوس درجة 5 مع جيران من الدرجة 2 يشاركون وجه 5

النظرية 8: حد أعلى لرقم الترابط المستقل

بالنسبة للرسم البياني المستوي $G$ حيث $\delta(G) \geq 2$ و $g(G) \geq 5$: $b_i(G) \leq 5$

خطوط الإثبات:

1. بناء مجموعة حافة $B$ بحجم ≤5 لكل تكوين
2. إثبات أن حذف $B$ يزيد رقم الهيمنة المستقل بشكل صارم
3. استخدام البرهان بالتناقض وخصائص مجموعات الهيمنة المستقلة

النتائج الرئيسية الأخرى

النظرية 10: $\delta(G) \geq 3$ و $g(G) \geq 4$ ⟹ $b_i(G) \leq 6$

النتيجة 1: $\delta(G) \geq 2$ و $g(G) \geq 7$ ⟹ $b_i(G) \leq 4$ (بناءً على لمة Cranston-West)

النظرية 13: $\delta(G) \geq 2$ و $g(G) \geq 10$ ⟹ $b_i(G) \leq 3$

نقاط الابتكار التقني

الابتكار المنهجي

1. التطبيق الأول المنهجي لطريقة التفريغ على بحث رقم الترابط المستقل
2. تطوير استراتيجيات توزيع شحنة جديدة: مصممة خصيصاً لخصائص رقم الترابط المستقل
3. بناء إطار عمل متكامل لتحديد الهيكل وبناء مجموعات الترابط

المساهمات النظرية

1. توسيع النتائج الكلاسيكية: التعميم من رقم الترابط إلى رقم الترابط المستقل
2. ملء الفجوات النظرية: توفير أول نتائج منهجية لرقم الترابط المستقل تحت قيود محيط الدورة
3. تحديد هياكل رسومية جديدة: اكتشاف التكوينات الرئيسية التي تؤثر على رقم الترابط المستقل

تقنيات الإثبات

1. تحليل شحنة دقيق: من خلال التحقق التفصيلي من الحقائق لضمان صحة عملية التفريغ
2. إثبات بناء: بناء واضح لمجموعة ترابط مستقل لكل تكوين
3. اكتمال تحليل الحالات: استنزاف جميع التكوينات الهيكلية الممكنة

الأعمال ذات الصلة

التطور التاريخي

1. 1979: أثبت Garey و Johnson أن مشكلة رقم الهيمنة هي NP-كاملة
2. 1983: قدم Bauer وآخرون مفهوم استقرار الهيمنة الخطي
3. 1990: عرّف Fink وآخرون رسمياً رقم الترابط
4. 2003: أسس Fischermann وآخرون حدود رقم الترابط تحت قيود محيط الدورة

بحث رقم الترابط المستقل

1. 2018: بدأ Priddy و Wang و Wei الدراسة المنهجية الأولى لرقم الترابط المستقل
2. 2021: أسس Pham و Wei حد ثابت لرسوم بيانية مستوية بـ $\delta(G) \geq 3$
3. هذه الورقة: أول دراسة لرقم الترابط المستقل تحت قيود محيط الدورة

مقارنة الطرق التقنية

• الطرق التقليدية: تعتمد بشكل أساسي على تحليل قيود الدرجة والبنية المحلية
• طريقة هذه الورقة: تجمع بين قيود محيط الدورة وتقنية التفريغ، توفر توصيفاً هيكلياً أكثر دقة

الخلاصة والنقاش

الاستنتاجات الرئيسية

تأسيس نظام حد أعلى متكامل لرقم الترابط المستقل في الرسوم البيانية المستوية تحت قيود محيط الدورة: