2025-11-17T18:31:12.470972

Distance mutual-visibility coloring: relations with (total) domination, exact distance graphs and graph products

Babu, Brešar, S et al.
The concept of mutual-visibility (MV) has been extended in several directions. A vertex subset $S$ of a graph $G$ is a $k$-distance mutual-visibility ($k$DMV) set if for any two vertices in $S$, there is a geodesic between them of length at most $k$ whose internal vertices are not in $S$. In this paper, we combine this with the MV coloring as follows. For any integer $k\geq1$, a $k$DMV coloring of $G$ is a partition of $V(G)$ into $k$DMV sets, and the $k$DMV chromatic number $χ_{μ_k}(G)$ is the minimum cardinality of such a partition. When $k=1$ or $k\ge {\rm diam}(G)$, it equals the clique cover number $θ(G)$ or the MV chromatic number $χ_μ(G)$, respectively. So, our attention is given to $1<k<{\rm diam}(G)$ with $k=2$ producing the most interesting results. We prove that $χ_{μ_2}(G)\le|V(G)|/2$ and present large families of graphs that attain the bound. In addition, $χ_{μ_2}(G)$ is bounded from above by the total domination number $γ_t(G)$ if $G$ is isolate-free, while in graphs $G$ with girth $g(G)\geq7$, $χ_{μ_2}(G)$ is bounded from below by the domination number $γ(G)$. A surprising relation with the exact distance-2 graphs is found, which results in $θ(G^{[\natural2]})=γ_{t}(G)$ for any isolate-free graph $G$ with $g(G)\geq7$. The relation is explored further in lexicographic product graphs, where we prove the sharp inequalities $χ_{μ_{2}}(G\circ H)\leq θ(G^{[\natural2]})\leq θ\big{(}(G\circ H)^{[\natural2]}\big{)}$. We also prove a sharp lower (resp. upper) bound on $χ_{μ_2}$ (resp. $χ_{μ_k}$) for the Cartesian (resp. strong) product of two connected graphs and show that they are widely sharp. Finally, we characterize the block graphs $G$ with $χ_{μ_k}(G)=χ_μ(G)$, where $k={\rm diam}(G)-1$.
academic

تلوين الرؤية المتبادلة على المسافة: العلاقات مع (الهيمنة الكاملة)، الرسوم البيانية للمسافة الدقيقة وحاصل الرسوم البيانية

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

  • معرّف الورقة: 2510.10284
  • العنوان: Distance mutual-visibility coloring: relations with (total) domination, exact distance graphs and graph products
  • المؤلفون: Saneesh Babu, Boštjan Brešar, Aparna Lakshmanan S, Babak Samadi
  • التصنيف: math.CO (الرياضيات التوافقية)
  • تاريخ النشر: 11 أكتوبر 2025
  • رابط الورقة: https://arxiv.org/abs/2510.10284

الملخص

تدرس هذه الورقة مسألة تلوين الرؤية المتبادلة على المسافة k، وهي امتداد لمفهوم الرؤية المتبادلة الذي قدمه Di Stefano عام 2022. بالنسبة لمجموعة فرعية S من رؤوس الرسم البياني G، تُسمى S مجموعة رؤية متبادلة على المسافة k (مجموعة k-DMV) إذا كان هناك مسار جيوديسي بطول لا يتجاوز k بين أي رأسين في S، بحيث لا تقع الرؤوس الداخلية على S. تجمع الورقة هذا المفهوم مع تلوين الرؤية المتبادلة، وتعرّف عدد تلوين k-DMV χ_μ_k(G). يكشف البحث أن الحالة k=2 تنتج أكثر النتائج إثارة للاهتمام، حيث يثبت أن χ_μ_2(G) ≤ |V(G)|/2، ويؤسس علاقات عميقة مع عدد الهيمنة وعدد الهيمنة الكاملة والرسوم البيانية للمسافة الدقيقة.

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

  1. أصل المشكلة: قُدم مفهوم الرؤية المتبادلة في الأصل بواسطة Di Stefano عام 2022، وهو مرتبط بمشكلة "عدم استقامة ثلاث نقاط" الكلاسيكية ومشاكل إعادة تحديد موضع الروبوتات المتحركة في المستوى.
  2. دافع البحث:
    • على الرغم من أن مفهوم الرؤية المتبادلة جديد، إلا أنه حظي باهتمام واسع (يوجد أكثر من 20 استشهاد في MathSciNet)
    • يركز البحث الحالي بشكل أساسي على الحد الأقصى لعدد العناصر في مجموعات الرؤية المتبادلة، مع نقص في الدراسات المنهجية لمسائل التلوين
    • يوفر تحديد المسافة k كفاءة أفضل في الاتصالات، مع قيمة تطبيقية عملية
  3. الأهمية العملية: في شبكات الحاسوب أو الشبكات الاجتماعية، يمكن للرؤوس ذات خصائص الرؤية المتبادلة أن تمثل كيانات تتطلب اتصالات فعالة وسرية، مما يضمن عدم مرور الرسائل عبر كيانات أخرى.

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

  1. إدخال مفهوم جديد: تعريف عدد تلوين الرؤية المتبادلة على المسافة k للمرة الأولى χ_μ_k(G)، مما يوحد عدد غطاء الكليك (k=1) وعدد تلوين الرؤية المتبادلة (k≥diam(G))
  2. إنشاء حدود أساسية:
    • إثبات أن χ_μ_2(G) ≤ ⌈|V(G)|/2⌉ مع تقديم عائلات الرسوم البيانية التي تحقق هذا الحد
    • بالنسبة للرسوم البيانية بدون رؤوس معزولة، χ_μ_2(G) ≤ γ_t(G)
    • بالنسبة للرسوم البيانية ذات المحيط الأدنى 7، χ_μ_2(G) ≥ γ(G)
  3. اكتشاف العلاقة مع الرسوم البيانية للمسافة الدقيقة: إثبات أنه بالنسبة للرسوم البيانية بدون رؤوس معزولة ومحيط أدنى 7، θ(G♮2) = γ_t(G)
  4. دراسة منهجية لحاصل الرسوم البيانية:
    • الحاصل القاموسي: χ_μ_2(G∘H) ≤ θ(G♮2) ≤ θ((G∘H)♮2)
    • الحاصل القوي: χ_μ_k(G⊠H) ≤ χ_μ_k(G)χ_μ_k(H)
    • الحاصل الديكارتي: χ_μ_2(G□H) ≥ max{χ_μ_2(G)ρ_2(H), χ_μ_2(H)ρ_2(G)}
  5. توصيف فئات الرسوم البيانية الخاصة: توصيف كامل للرسوم البيانية البلوكية التي تحقق χ_μ_k(G) = χ_μ(G) (حيث k = diam(G)-1)

شرح الطرق

تعريف المهمة

بالنظر إلى رسم بياني G وعدد صحيح موجب k، فإن تلوين الرؤية المتبادلة على المسافة k هو مخطط تلوين يقسم V(G) إلى عدة مجموعات k-DMV. حيث تحقق مجموعة k-DMV M الشرط: بالنسبة لأي رأسين u,v في M، يوجد مسار جيوديسي بطول لا يتجاوز k بين u و v، بحيث لا تقع الرؤوس الداخلية على M.

الإدخال: رسم بياني G = (V,E)، عدد صحيح موجب k الإخراج: تقسيم {S_1, S_2, ..., S_t} لـ V(G)، بحيث تكون كل S_i مجموعة k-DMV الهدف: تقليل عدد المجموعات في التقسيم t

الطرق التقنية الأساسية

1. إنشاء النظرية الأساسية

الملاحظة 1: بالنسبة للرسم البياني G بقطر d، يوجد سلسلة رتابة: χ_μ(G) = χ_μ_d(G) ≤ χ_μ_(G) ≤ ... ≤ χ_μ_1(G) = θ(G)

الملاحظة 2: الحد الأدنى الأساسي χ_μ_k(G) ≥ ⌈|V(G)|/μ_k(G)⌉

2. تحليل عميق لحالة k=2

النظرية 4: بالنسبة لأي رسم بياني متصل G، χ_μ_2(G) ≤ ⌈n/2⌉

فكرة الإثبات: من خلال البناء الاستقرائي على الشجرة الممتدة، يتم تقسيم الشجرة إلى هياكل يمكن تلوينها بلونين.

النظرية 5: إذا كان G بدون رؤوس معزولة، فإن χ_μ_2(G) ≤ γ_t(G)

طريقة الإثبات: إثبات بناء، باستخدام مجموعة الهيمنة الكاملة D = {v_1,...,v_γ_t(G)}، تُعرّف D_i = N_G(v_i)\⋃_^{i-1}N_G(v_j)، ويثبت أن كل D_i هي مجموعة 2DMV.

3. العلاقة بين المحيط وعدد الهيمنة

اللمة 6: إذا كان g(G) ≥ 7، فإن كل فئة لون C في تلوين χ_μ_2(G) هي مجموعة فرعية من الحي المغلق لبعض الرؤوس.

النظرية 7: إذا كان g(G) ≥ 7، فإن χ_μ_2(G) ≥ γ(G)

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

  1. إطار عمل موحد: توحيد غطاء الكليك وتلوين الرؤية المتبادلة في إطار تلوين k-DMV
  2. التوصيف الدقيق لشروط المحيط: إثبات أن المحيط 7 هو الحد الأدنى لضمان χ_μ_2(G) ≥ γ(G)
  3. الربط برسوم البيانية للمسافة الدقيقة: إنشاء علاقة عميقة لأول مرة بين تلوين 2DMV ورسم البياني للمسافة الدقيقة-2
  4. التحليل المنهجي لحاصل الرسوم البيانية: تقديم حدود محكمة للحاصل الثلاثي الرئيسي

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

طرق التحقق النظري

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

  1. المسارات والدورات: حساب قيم χ_μ_k الدقيقة لـ P_n و C_n
  2. عائلات الرسوم البيانية الخاصة: بناء عائلات تحقق حدود مختلفة
  3. الرسوم البيانية المركبة: تحليل خصائص حاصل الرسوم البيانية المحددة مثل P_n⊠K_m

تحليل الأمثلة الرئيسية

القضية 2:

  • بالنسبة للمسار P_n: χ_μ_k(P_n) = ⌈n/2⌉
  • بالنسبة للدورة C_n: χ_μ_k(C_n) = ⌈n/3⌉ (عندما n ≤ 3k)، ⌈n/2⌉ (وإلا)

القضية 12: بالنسبة لـ P_n⊠K_m (n≥4, m≥2, k∈{2,...,n-2}): χ_μ_k(P_n⊠K_m) = 2⌊n/(k+2)⌋ + correction_term

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

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

  1. محكمية الحدود الأساسية:
    • χ_μ_2(G) ≤ ⌈|V(G)|/2⌉ صحيح لجميع الرسوم البيانية، ويتحقق بواسطة المسارات والدورات الطويلة
    • χ_μ_2(G) ≤ γ_t(G) صحيح للرسوم البيانية بدون رؤوس معزولة، مع إمكانية بناء عائلات رسوم بيانية يمكن أن يكون الفرق فيها كبيراً بشكل تعسفي
  2. الأمثلية لشروط المحيط:
    • بناء مثال مضاد بمحيط 6 لكن γ(G) = 5 > χ_μ_2(G) = 3
    • إثبات أن المحيط 7 هو الحد الأدنى لضمان χ_μ_2(G) ≥ γ(G)
  3. حدة نتائج حاصل الرسوم البيانية:
    • يتم تحقيق حد الحاصل القوي χ_μ_k(G⊠H) ≤ χ_μ_k(G)χ_μ_k(H) بواسطة عائلات رسوم بيانية لا نهائية
    • يتم تحقيق الحد الأدنى للحاصل الديكارتي بواسطة رسوم بيانية الطارة وغيرها

الربط المذهل برسوم البيانية للمسافة الدقيقة

النظرية 8: إذا كان G بدون رؤوس معزولة وg(G) ≥ 7، فإن θ(G♮2) = χ_i_μ_2(G) = γ_t(G)

تؤسس هذه النتيجة علاقة مساواة بين ثلاث معاملات رسوم بيانية تبدو غير مرتبطة، وهي ذات أهمية نظرية كبيرة.

الخصائص الخاصة للمكعبات الفائقة

القضية 16: بالنسبة لـ n-مكعب فائق Q_n، χ_μ_2(Q_n) ≤ γ(Q_n)

التخمين: χ_μ_2(Q_n) = γ(Q_n) صحيح لجميع n

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

  1. أبحاث الرؤية المتبادلة: Di Stefano (2022) قدم المفهوم الأساسي، وسّع Cera وآخرون النسخة على المسافة k
  2. تلوين الرؤية المتبادلة: Klavžar وآخرون (2025) درسوا مسألة تلوين الرؤية المتبادلة لأول مرة
  3. الرسوم البيانية للمسافة الدقيقة: قُدمت في الثمانينيات، وحظيت باهتمام متجدد مؤخراً
  4. نظرية الهيمنة: مجال بحث كلاسيكي في نظرية الرسوم البيانية، أسست الورقة علاقات جديدة معه

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

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

  1. يوفر تلوين الرؤية المتبادلة على المسافة k منظوراً جديداً لدراسة خصائص بنية الرسوم البيانية
  2. تُظهر حالة k=2 علاقات عميقة مع نظرية الهيمنة والرسوم البيانية للمسافة الدقيقة
  3. يكشف السلوك تحت حاصل الرسوم البيانية المختلفة عن الخصائص الأساسية لهذا المعامل
  4. تلعب شروط المحيط دوراً حاسماً في تحديد حدود المعامل

القيود

  1. تركز النتائج الرئيسية على حالة k=2، مع دراسة أقل للقيم العامة لـ k
  2. يتم التحقق من محكمية بعض الحدود فقط في عائلات رسوم بيانية محددة
  3. لم يتم تناول مسائل التعقيد الحسابي

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

تقترح الورقة ثلاث مسائل مفتوحة محددة:

المسألة 1: توصيف الرسوم البيانية البلوكية G التي تحقق χ_μ_2(G) = θ(G)

المسألة 2: بالنسبة للرسوم البيانية المتصلة G,H، هل يكون χ_μ_2(G□H) ≥ max{χ_μ_2(G)γ(H), χ_μ_2(H)γ(G)}؟

المسألة 3: هل χ_μ_2(Q_n) = γ(Q_n) صحيح لجميع المكعبات الفائقة؟

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

المميزات

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

أوجه القصور

  1. غياب التعقيد الحسابي: لم يتم مناقشة التعقيد الحسابي لـ χ_μ_k(G)
  2. قيود التطبيق: على الرغم من الإشارة إلى تطبيقات الاتصالات الشبكية، إلا أن هناك نقصاً في تحليل السيناريوهات التطبيقية المحددة
  3. تصميم الخوارزميات: غياب الخوارزميات الفعالة لحساب أو تقريب χ_μ_k(G)

التأثير

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

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

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

المراجع

تستشهد الورقة بـ 18 مرجعاً ذا صلة، تشمل بشكل أساسي:

  • Di Stefano (2022): المرجع الأصلي لمفهوم الرؤية المتبادلة
  • Cera وآخرون: امتداد الرؤية المتبادلة على المسافة k
  • Klavžar وآخرون: أول دراسة لتلوين الرؤية المتبادلة
  • كتب نظرية الرسوم البيانية الكلاسيكية وأدبيات نظرية الهيمنة

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