2025-11-16T18:28:12.845274

On open-separating dominating codes in graphs

Chakraborty, Wagler
Using dominating sets to separate vertices of graphs is a well-studied problem in the larger domain of identification problems. In such problems, the objective is to choose a suitable dominating set $C$ of a graph $G$ which is also separating in the sense that the neighbourhoods of any two distinct vertices of $G$ have distinct intersections with $C$. Such a dominating and separating set $C$ of a graph is often referred to as a code in the literature. Depending on the types of dominating and separating sets used, various problems arise under various names in the literature. In this paper, we introduce a new problem in the same realm of identification problems whereby the code, called open-separating dominating code, or OD-code for short, is a dominating set and uses open neighbourhoods for separating vertices. The paper studies the fundamental properties concerning the existence, hardness and minimality of OD-codes. Due to the emergence of a close and yet difficult to establish relation of the OD-code with another well-studied code in the literature called open (neighborhood)-locating dominating code (referred to as the open-separating total-dominating code and abbreviated as OTD-code in this paper), we compare the two codes on various graph families. Finally, we also provide an equivalent reformulation of the problem of finding OD-codes of a graph as a covering problem in a suitable hypergraph and discuss the polyhedra associated with OD-codes, again in relation to OTD-codes of some graph families already studied in this context.
academic

حول أكواد الهيمنة الفاصلة المفتوحة في الرسوم البيانية

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

  • معرّف الورقة: 2402.03015
  • العنوان: On open-separating dominating codes in graphs
  • المؤلفون: Dipayan Chakraborty, Annegret K. Wagler
  • التصنيف: math.CO (الرياضيات التوافقية)، cs.DM (الرياضيات المنفصلة)
  • تاريخ النشر: 5 فبراير 2024 (نسخة أولية من arXiv)
  • رابط الورقة: https://arxiv.org/abs/2402.03015

الملخص

تقدم هذه الورقة مشكلة جديدة في مجال مشاكل التعريف في الرسوم البيانية - أكواد الهيمنة الفاصلة المفتوحة (OD-code). تتطلب هذه المشكلة اختيار مجموعة فرعية من الرؤوس التي تكون في نفس الوقت مجموعة هيمنة وتمتلك خاصية الفصل، بحيث تكون تقاطعات الجوار المفتوح لأي رأسين مختلفين مع هذه المجموعة غير متطابقة. تدرس الورقة بشكل منهجي الخصائص الأساسية لأكواد OD، بما في ذلك الوجود والتعقيد الحسابي والحد الأدنى، وتجري مقارنة عميقة مع أكواد التعريف الهيمنة المفتوحة الموجودة (OTD-code). بالإضافة إلى ذلك، تعيد الورقة صياغة مشكلة OD-code كمشكلة تغطية فوق-رسم بياني وتناقش البنى متعددة الأوجه ذات الصلة.

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

خلفية المشكلة

  1. أهمية مشاكل التعريف: في نظرية الرسوم البيانية، يعتبر فصل الرؤوس باستخدام مجموعات الهيمنة اتجاهاً بحثياً كلاسيكياً في مجال مشاكل التعريف، مع تطبيقات عملية واسعة، مثل كشف الأعطال في شبكات المعالجات المتعددة وتحديد موقع المتطفلين في شبكات الاستشعار.
  2. قيود أنواع الأكواد الموجودة: يتضمن الأدب عدة مجموعات من الأكواد:
    • أكواد التعريف (ID-codes): فصل الجوار المغلق + الهيمنة
    • أكواد الهيمنة الموضعية (LD-codes): التحديد الموضعي + الهيمنة
    • أكواد الهيمنة الكلية الفاصلة المفتوحة (OTD-codes): فصل الجوار المفتوح + الهيمنة الكلية
  3. الفجوة البحثية: لم تتم دراسة الجمع بين الفصل المفتوح والهيمنة العادية (OD-code) بشكل منهجي من قبل، لكن هذا الجمع يشكل إضافة طبيعية وضرورية من الناحية النظرية.

الدافع التطبيقي

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

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

  1. إدخال نوع جديد من الأكواد: أول دراسة منهجية وتعريف أكواد الهيمنة الفاصلة المفتوحة (OD-code)
  2. إنشاء أساس نظري: إثبات الشروط الضرورية والكافية لوجود أكواد OD والعلاقات مع أنواع الأكواد الأخرى
  3. تحليل التعقيد: إثبات اكتمال NP لمشكلة OD-Code وصعوبة NP لتحديد ما إذا كانت أرقام OD و OTD متساوية
  4. تحليل الحدود: توفير الحدود العليا والدنيا لرقم OD، خاصة إثبات أنه بالنسبة لرسم بياني من الرتبة n بدون رؤوس توأم مفتوحة وبدون رؤوس معزولة G، لدينا ⌈log n⌉ ≤ γ_OD(G) ≤ n-1
  5. مقارنة عائلات الرسوم البيانية: مقارنة خصائص أكواد OD و OTD على عدة عائلات رسوم بيانية مهمة
  6. النظرية متعددة الأوجه: توفير إعادة بناء تغطية فوق-رسم بياني لمشكلة OD-code ودراسة البنى متعددة الأوجه ذات الصلة

شرح الطرق

تعريف المهمة

بالنظر إلى رسم بياني G = (V,E)، مجموعة فرعية من الرؤوس C ⊆ V هي كود هيمنة فاصل مفتوح (OD-code) إذا وفقط إذا:

  1. خاصية الهيمنة: لكل رأس v ∈ V، Nv ∩ C ≠ ∅ (تقاطع الجوار المغلق مع C غير فارغ)
  2. خاصية الفصل المفتوح: لكل رأس v ∈ V، N(v) ∩ C فريد (تقاطعات الجوار المفتوح مع C متميزة)

حيث يمثل N(v) الجوار المفتوح للرأس v، و Nv = N(v) ∪ {v} يمثل الجوار المغلق.

الإطار النظري

تحليل الوجود

النظرية: الرسم البياني G قابل للقبول بـ OD إذا وفقط إذا كان G خالياً من رؤوس التوأم المفتوحة.

رؤوس التوأم المفتوحة هي رؤوس مختلفة ذات جوار مفتوح متطابق، أي N(u) = N(v) و u ≠ v.

إعادة بناء فوق-الرسم البياني

تعيد الورقة صياغة مشكلة OD-code بشكل متكافئ كمشكلة تغطية فوق-رسم بياني:

فوق-رسم البياني OD H_OD(G) = (V, F_OD) يحتوي على الحواف الفائقة التالية:

  • جميع الجوارات المغلقة للرؤوس Nv
  • جميع الفروقات المتماثلة للجوارات المفتوحة لأزواج الرؤوس المختلفة N(u)△N(v)

حيث A△B = (A\B) ∪ (B\A) يمثل الفرق المتماثل.

إثبات التعقيد

تثبت الورقة اكتمال NP لمشكلة OD-Code من خلال الاختزال من مشكلة SAT الخطية (LSAT). يتمتع الرسم البياني المُنشأ بالخصائص التالية:

  • رسم بياني ثنائي الأجزاء
  • الحد الأقصى للدرجة 4
  • محيط لا يقل عن 6

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

  1. العلاقة الدقيقة مع أكواد OTD: إثبات أنه بالنسبة لرسم بياني OTD-قابل للقبول G، لدينا γ_OTD(G) - 1 ≤ γ_OD(G) ≤ γ_OTD(G)
  2. تطبيق نظرية Bondy: التطبيق الماهر لنظرية Bondy لإثبات الحد الأعلى لرقم OD
  3. طريقة نظرية الحزم: تبسيط تحليل المشكلة من خلال إزالة الحواف الفائقة الزائدة للحصول على حزم OD

الإعداد التجريبي

موضوعات البحث

تدرس الورقة بشكل أساسي من خلال التحليل النظري عائلات الرسوم البيانية التالية:

  • الرسوم البيانية الكاملة K_n
  • الاتحادات المنفصلة للعصابات
  • رسوم بيانية نجم k-عصابة
  • الرسوم البيانية ثنائية الأجزاء (نصف الرسوم البيانية، رسوم بيانية k-نجم مزدوجة)
  • الرسوم البيانية المقسمة (رسوم بيانية العنكبوت برأس، رسوم بيانية العنكبوت الدقيقة الممتدة)
  • رسوم بيانية الشمس الدقيقة

طرق التحليل

  1. بناء حزم OD: تحديد بنية حزم OD لكل عائلة رسوم بيانية
  2. حساب أرقام التغطية: استخدام نظرية تغطية فوق-الرسم البياني المعروفة لحساب أرقام التغطية الدنيا
  3. التحليل المقارن: المقارنة مع أرقام OTD المقابلة

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

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

عائلة الرسوم البيانية الكاملة

  • الرسم البياني الكامل K_n (n ≥ 2): γ_OD(K_n) = n-1 = γ_OTD(K_n) (عندما n ≥ 3)
  • المطابقة kK_2: γ_OD(kK_2) = 2k-1 < 2k = γ_OTD(kK_2)

عائلة الرسوم البيانية ثنائية الأجزاء

  • نصف الرسم البياني B_k: γ_OD(B_k) = 2k-1 < 2k = γ_OTD(B_k)
  • النجم المزدوج k-D_k (k ≥ 3): γ_OD(D_k) = 2k-1 < 2k = γ_OTD(D_k)

عائلة الرسوم البيانية المقسمة

  • العنكبوت برأس دقيق H_k (k ≥ 3): γ_OD(H_k) = k = γ_OTD(H_k)
  • العنكبوت برأس سميك H̄_k (k ≥ 3): γ_OD(H̄_k) = k+1 = γ_OTD(H̄_k)
  • العنكبوت الدقيق الممتد E_k (k ≥ 4): γ_OD(E_k) = k < k+1 = γ_OTD(E_k)

النتائج القيمة

اكتشفت الورقة عائلات رسوم بيانية تحقق الحدود النظرية:

  • تحقيق الحد الأعلى: الرسوم البيانية الكاملة ونصف الرسوم البيانية واتحاداتها المنفصلة تحقق الحد الأعلى γ_OD(G) = |V(G)| - 1
  • تحليل الحد الأدنى: يمكن للرسوم البيانية المقسمة الاقتراب من الحد الأدنى اللوغاريتمي ⌈log n⌉

الاكتشافات المهمة

  1. عدم الإضافية: بالنسبة لبعض الرسوم البيانية غير المتصلة، γ_OD(G) أكبر من مجموع أرقام OD للمكونات المتصلة، وهذا لا يحدث في أنواع الأكواد الأخرى
  2. صعوبة NP للفرق: على الرغم من أن أرقام OD و OTD تختلف بمقدار 1 على الأكثر، فإن تحديد ما إذا كانت متساوية هو NP-صعب

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

طيف مشاكل التعريف

تقوم الورقة بتتبع منهجي لتطور مشاكل التعريف:

  1. أكواد التعريف (1998): قدمها Karpovsky وآخرون لأول مرة
  2. أكواد الهيمنة الموضعية (1988): قدمها Slater
  3. متغيرات الهيمنة الكلية (2006): درسها Haynes وآخرون
  4. متغيرات الجوار المفتوح (2002-2010): قدمها Honkala وآخرون و Seo-Slater بشكل مستقل

مجالات التطبيق

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

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

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

  1. الاكتمال النظري: تملأ أكواد OD فجوة في الإطار النظري لمشاكل التعريف وتشكل نظاماً نظرياً متكاملاً مع أنواع الأكواد الأخرى
  2. التعقيد الحسابي: مشكلة OD-Code هي NP-كاملة، حتى على فئات الرسوم البيانية المقيدة
  3. العلاقة الدقيقة مع أكواد OTD: يختلف الاثنان بمقدار 1 على الأكثر، لكن تحديد ما إذا كانا متساويين صعب
  4. تصنيف عائلات الرسوم البيانية: على عائلات رسوم بيانية مختلفة، قد تكون أرقام OD و OTD متساوية أو غير متساوية، مما يعكس بنية توافقية غنية

القيود

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

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

  1. البحث الخوارزمي: تصميم خوارزميات تقريبية وخوارزميات دقيقة لأكواد OD
  2. التحليل المعاملي: دراسة الخوارزميات ذات المعاملات الثابتة باستخدام معاملات رسوم بيانية مختلفة
  3. المشاكل الديناميكية: النظر في مشاكل صيانة أكواد OD عند تغيير بنية الرسم البياني
  4. توسيع التطبيقات: استكشاف تطبيقات أكواد OD في مشاكل الشبكات العملية

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

المزايا

  1. المساهمة النظرية: إنشاء أساس نظري منهجي لأكواد OD، ملء فجوة بحثية مهمة
  2. الابتكار الطريقة: التطبيق الماهر لنظرية تغطية فوق-الرسم البياني والطرق متعددة الأوجه لتحليل المشكلة
  3. عمق النتائج: لا توفر فقط نتائج الوجود والتعقيد، بل تحلل أيضاً بعمق العلاقات الدقيقة مع المشاكل ذات الصلة
  4. الدقة التقنية: الإثباتات صارمة وتستخدم تقنيات متقدمة متعددة من الرياضيات التوافقية

أوجه القصور

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

التأثير

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

السيناريوهات المعمول بها

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

المراجع

تستشهد الورقة بـ 35 مرجعاً ذا صلة، يغطي المسار الرئيسي لتطور مشاكل التعريف والطرق التقنية، خاصة:

  • 26 العمل الرائد لـ Karpovsky وآخرين في أكواد التعريف
  • 32 النظرية الأساسية لـ Slater في أكواد الهيمنة الموضعية
  • 33 بحث Seo-Slater في أكواد OTD
  • 2,4 طرق Argiroffo وآخرين متعددة الأوجه
  • 31 نظرية Sassano في متعددات التغطية

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