2025-11-23T03:01:16.593819

Determining the b-chromatic number of subdivision-vertex neighbourhood coronas

Falcón, Venkatachalam, Margaret
Let $G$ and $H$ be two graphs, each one of them being a path, a cycle or a star. In this paper, we determine the $b$-chromatic number of every subdivision-vertex neighbourhood corona $G\boxdot H$ or $G\boxdot K_n$, where $K_n$ is the complete graph of order $n$. It is also established for those graphs $K_n\boxdot G$ having $m$-degree not greater than $n+2$. All the proofs are accompanied by illustrative examples.
academic

تحديد العدد اللوني b للتيجان الحي-الفرعية للرؤوس

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

  • معرّف الورقة: 2302.13667
  • العنوان: تحديد العدد اللوني b للتيجان الحي-الفرعية للرؤوس
  • المؤلفون: راؤول م. فالكون (جامعة إشبيلية، إسبانيا)، م. فينكاتاتشالام، س. جولي مارغريت (كلية كونجونادو للفنون والعلوم، الهند)
  • التصنيف: math.CO (التوافقيات)
  • تاريخ النشر: 27 فبراير 2023
  • رابط الورقة: https://arxiv.org/abs/2302.13667

الملخص

ليكن GG و HH رسمين بيانيين، كل منهما مسار أو دورة أو رسم نجمي. تحدد هذه الورقة العدد اللوني b لكل رسم بياني تاج حي-فرعي للرؤوس G⊡HG\boxdot H أو G⊡KnG\boxdot K_n، حيث KnK_n هو الرسم البياني الكامل من الرتبة nn. كما تم إنشاء النتائج المقابلة للرسم البياني Kn⊡GK_n\boxdot G حيث الدرجة m لا تتجاوز n+2n+2. جميع الإثباتات مصحوبة بأمثلة توضيحية.

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

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

  1. مفهوم العدد اللوني b: قدم إيرفينج ومانلوف في عام 1999 مفهوم التلوين b-اللوني للرسم البياني، وهو نوع خاص من التلوين k-العادي الذي يتطلب أن يكون لكل لون رأس b (رأس مجاور لجميع رؤوس الألوان الأخرى).
  2. التعقيد الحسابي: تحديد العدد اللوني b للرسم البياني هو مشكلة NP-صعبة في الحالة العامة، لكنها قابلة للحل في الوقت متعدد الحدود للأشجار.
  3. دراسة الرسوم البيانية المركبة: هناك عدد كبير من الدراسات التي تركز على العدد اللوني b للرسوم البيانية المركبة المختلفة، مثل الضرب الديكارتي والضرب المباشر والضرب القوي والضرب المعجمي.

دافع البحث

  1. تحسين النظرية: التاج الحي-الفرعي للرؤوس (SVN corona) هو طريقة بناء رسم بياني مهمة، لكن دراسة العدد اللوني b له نسبياً ناقصة.
  2. نظامية الطريقة: الحاجة إلى دراسة منهجية للعدد اللوني b لتيجان SVN للفئات الأساسية من الرسوم البيانية (المسارات والدورات والرسوم النجمية والرسوم الكاملة).
  3. القيمة التطبيقية: للعدد اللوني b تطبيقات مهمة في تلوين الشبكات وتخصيص الترددات والمشاكل العملية الأخرى.

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

  1. التحديد الكامل للعدد اللوني b لتيجان SVN للفئات الأساسية: توفير صيغ دقيقة للعدد اللوني b لتيجان SVN للمسارات PnP_n والدورات CnC_n والرسوم النجمية SnS_n مع المسارات والدورات والرسوم النجمية والرسوم الكاملة.
  2. إنشاء نتائج جزئية لتيجان الرسوم الكاملة: تحديد العدد اللوني b للرسم البياني Kn⊡GK_n\boxdot G حيث الدرجة m لا تتجاوز n+2n+2.
  3. توفير طرق إثبات بنائية: جميع النتائج يتم إثباتها من خلال بناء تلوين b-لوني أمثل محدد، مع أمثلة رسومية مفصلة.
  4. تطوير إطار عمل تحليلي منهجي: إنشاء طريقة عامة وأدوات تقنية لتحليل العدد اللوني b لتيجان SVN.

شرح الطريقة

تعريف المهمة

الإدخال: رسمان بيانيان GG و HH، حيث G,H∈{Pn,Cn,Sn,Kn}G,H \in \{P_n, C_n, S_n, K_n\}الإخراج: العدد اللوني b لرسم التاج الحي-الفرعي G⊡HG\boxdot H وهو φ(G⊡H)\varphi(G\boxdot H)القيود: في حالة Kn⊡GK_n\boxdot G، يُطلب أن تكون m(Kn⊡G)≤n+2m(K_n\boxdot G) \leq n+2

بناء رسم التاج الحي-الفرعي

بالنظر إلى الرسمين البيانيين GG و HH، عملية بناء رسم التاج الحي-الفرعي G⊡HG\boxdot H:

  1. البدء من الرسم البياني الفرعي S(G)S(G) للرسم البياني GG (إدراج رأس جديد على كل حافة)
  2. إضافة ∣V(G)∣|V(G)| نسخة منفصلة من رؤوس الرسم البياني HH
  3. ربط جميع الرؤوس في الحي الأصلي لكل رأس uiu_i في S(G)S(G) بجميع رؤوس النسخة (i+1)(i+1) من HH

الأدوات التقنية الرئيسية

1. مفهوم الدرجة m

بالنسبة للرسم البياني GG من الرتبة nn، يتم تعريف درجة m كما يلي: m(G):=∣{i∈{1,…,n}:d(vi−1)≥i−1}∣m(G) := |\{i \in \{1,\ldots,n\} : d(v_{i-1}) \geq i-1\}| حيث يتم ترتيب الرؤوس بترتيب تنازلي حسب الدرجة.

2. الحدود الأساسية

  • الحد الأدنى: χ(G)≤φ(G)\chi(G) \leq \varphi(G) (العدد اللوني لا يتجاوز العدد اللوني b)
  • الحد الأقصى: φ(G)≤Δ(G)+1\varphi(G) \leq \Delta(G) + 1 (العدد اللوني b لا يتجاوز أقصى درجة زائد واحد)
  • حد درجة m: φ(G)≤m(G)\varphi(G) \leq m(G)

3. صيغة الدرجة لرسم التاج الحي-الفرعي

بالنسبة للرأس vv في G⊡HG\boxdot H:

d_G(v), & \text{إذا كان } v \in V(G) \\ 2|V(H)| + 2, & \text{إذا كان } v \in I(G) \\ d_G(u_i) + d_H(v_j), & \text{إذا كان } v = v_{i,j} \end{cases}$$ ### استراتيجية التحليل تعتمد الورقة على طريقة النقاش الحالات، موجهة نحو مجموعات رسم بياني مختلفة: 1. **تيجان SVN للمسارات** (القسم 3) 2. **تيجان SVN للدورات** (القسم 4) 3. **تيجان SVN للرسوم النجمية** (القسم 5) 4. **تيجان SVN للرسوم الكاملة** (القسم 6) في كل حالة، يتم إثبات ضيق الحد الأعلى من خلال بناء تلوين b-لوني محدد. ## النتائج الرئيسية ### العدد اللوني b لتيجان SVN للمسارات **النظرية 6** ($P_n \boxdot P_t$): $$\varphi(P_n \boxdot P_t) = \begin{cases} 4, & \text{إذا كان } n=3 \text{ و } t \in \{3,4\} \\ 5, & \text{إذا كان } (n=3 \text{ و } t \geq 5) \text{ أو } n \in \{4,5\} \\ n-1, & \text{إذا كان } 6 \leq n \leq 2t+3 \\ 2t+3, & \text{وإلا} \end{cases}$$ **النظريات 7-9**: توفير صيغ دقيقة مماثلة لـ $P_n \boxdot C_t$ و $P_n \boxdot S_t$ و $P_n \boxdot K_t$. ### العدد اللوني b لتيجان SVN للدورات **النظرية 11** ($C_n \boxdot P_t$): $$\varphi(C_n \boxdot P_t) = \begin{cases} 5, & \text{إذا كان } n \in \{3,4\} \\ n, & \text{إذا كان } 5 \leq n \leq 2t+2 \\ 2t+3, & \text{وإلا} \end{cases}$$ ### العدد اللوني b لتيجان SVN للرسوم النجمية **النظرية 17**: إنشاء صيغ العدد اللوني b الكاملة لتيجان SVN للرسوم النجمية مع فئات الرسوم الأساسية، حيث تتضمن النتائج الرئيسية: $$\varphi(S_n \boxdot K_{t'}) = \min\{n, t'+2\} + t'$$ ### العدد اللوني b لتيجان SVN للرسوم الكاملة **النظريات 20-24**: توفير العدد اللوني b لـ $K_n\boxdot G$ تحت قيود درجة m، على سبيل المثال: $$\varphi(K_n \boxdot P_t) = \begin{cases} n+1, & \text{شروط معينة} \\ n+2, & \text{شروط أخرى} \end{cases}$$ ## نقاط الابتكار التقني ### 1. طريقة الإثبات البنائية - لا يقتصر الأمر على إثبات الحد الأعلى، بل يتم إثبات الحد الأدنى من خلال بناء تلوين b-لوني أمثل صريح - كل بناء مصحوب بأمثلة رسومية مفصلة، مما يعزز قابلية التحقق من النتائج ### 2. مفهوم مجموعة قوس قزح b إدخال مفهوم مجموعة قوس قزح b لتبسيط تحديد رؤوس b، مع تمييز مختلف الرموز في الرسم البياني: - علامة الضرب ×: رؤوس مجموعة قوس قزح b المحددة - مثلث △: رؤوس b الأخرى - دائرة ●: رؤوس عادية ### 3. تقنيات العمليات الحسابية بالمعاملات استخدام واسع النطاق للعمليات الحسابية بالمعاملات في بناء التلوين لضمان الدورية والصحة، على سبيل المثال: $$c(u_i) = (i+1) \bmod \min\{m(P_n \boxdot P_t), n\}$$ ### 4. نظامية النقاش الحالات إجراء نقاش منهجي للحالات بناءً على نطاقات المعاملات، مما يضمن تغطية جميع الحالات الممكنة. ## التحقق التجريبي ### التحقق الرسومي توفر الورقة عدداً كبيراً من الأمثلة الرسومية للتحقق من النتائج النظرية: - الشكل 2: التلوين b-اللوني الأمثل لـ $P_{10} \boxdot P_3$ - الأشكال 3-4: التلوين لتيجان SVN للمسارات بمعاملات مختلفة - الشكل 11: مثال تلوين لتيجان SVN للدورات - الأشكال 17-18: بناء التلوين لتيجان SVN للرسوم النجمية ### التحقق من البناء يتضمن إثبات كل نظرية خوارزمية بناء تلوين محددة، يمكن التحقق منها مباشرة: 1. صحة التلوين (عدم تطابق ألوان الرؤوس المجاورة) 2. وجود رؤوس b (وجود رأس b لكل لون) 3. الأمثلية (تحقيق الحد النظري) ## الأعمال ذات الصلة ### تاريخ دراسة العدد اللوني b 1. **Irving-Manlove (1999)**: تقديم مفهوم العدد اللوني b لأول مرة 2. **دراسات الرسوم البيانية المركبة المختلفة**: تم بحث العدد اللوني b للضرب الديكارتي والضرب المباشر والضرب القوي وغيرها على نطاق واسع 3. **فئات الرسوم البيانية الخاصة**: معروف العدد اللوني b للمسارات والدورات والرسوم النجمية والرسوم الكاملة ### موقع هذه الورقة - **ملء الفراغ**: دراسة العدد اللوني b لتيجان SVN نسبياً ناقصة - **ابتكار الطريقة**: توفير طريقة بنائية منهجية - **اكتمال النتائج**: توفير نتائج كاملة لمجموعات الرسوم الأساسية ## الخلاصة والنقاش ### الاستنتاجات الرئيسية 1. **الاكتمال**: توفير نتائج تحديد العدد اللوني b الكاملة لتيجان SVN للفئات الأساسية (المسارات والدورات والرسوم النجمية والرسوم الكاملة) 2. **الدقة**: جميع النتائج قيم دقيقة وليست تقريبات أو حدود 3. **البنائية**: توفير طرق بناء تلوين أمثل محددة ### القيود 1. **قيود الفئات**: تم النظر فقط في الفئات الأساسية، والنتائج للرسوم البيانية العامة تحتاج إلى مزيد من البحث 2. **قيود الرسوم الكاملة**: نتائج $K_n\boxdot G$ تتطلب شروط قيود درجة m 3. **التعقيد**: نقاش الحالات في بعض الحالات معقد نسبياً ### الاتجاهات المستقبلية 1. **توسيع الفئات**: دراسة العدد اللوني b لتيجان SVN للفئات الأكثر عمومية 2. **دراسة الخوارزميات**: تطوير خوارزميات فعالة لحساب العدد اللوني b 3. **استكشاف التطبيقات**: تطبيق النتائج على مشاكل تلوين الشبكات العملية ## التقييم المتعمق ### المميزات 1. **مساهمة نظرية كبيرة**: حل منهجي لمشكلة العدد اللوني b لفئة مهمة من الرسوم البيانية المركبة 2. **طريقة صارمة**: طريقة الإثبات البنائية تضمن موثوقية النتائج 3. **تعبير واضح**: عدد كبير من الرسوم البيانية والأمثلة يجعل الإثباتات المعقدة سهلة الفهم 4. **اكتمال النتائج**: تغطية جميع المجموعات المهمة للفئات الأساسية ### أوجه القصور 1. **ابتكار تقني محدود**: في الأساس تطبيق منهجي للطرق الموجودة، يفتقر إلى تقنيات جديدة جوهرية 2. **قيمة التطبيق غير واضحة**: نقص النقاش حول سيناريوهات التطبيق العملي 3. **غياب تحليل التعقيد الحسابي**: عدم مناقشة التعقيد الزمني لخوارزميات البناء ### التأثير 1. **القيمة النظرية**: توفير مساهمة مهمة لنظرية العدد اللوني b للرسوم البيانية 2. **قيمة الطريقة**: يمكن تعميم طريقة البناء على دراسة الرسوم البيانية المركبة الأخرى 3. **قيمة الاكتمال**: ملء الفراغ في دراسة العدد اللوني b لتيجان SVN ### السيناريوهات المعمول بها 1. **البحث النظري**: البحث الأساسي في نظرية الرسوم البيانية والتحسين التوافقي 2. **تصميم الشبكات**: مشاكل تلوين الشبكات التي تحتاج إلى النظر في القيود الحية 3. **تصميم الخوارزميات**: كوحدة أساسية لخوارزميات تلوين الرسوم البيانية الأكثر تعقيداً ## المراجع تستشهد الورقة بـ 25 مرجعاً ذا صلة، تتضمن بشكل أساسي: - Irving & Manlove (1999): التعريف الأصلي للعدد اللوني b - Kouider & Mahéo وآخرون: دراسة العدد اللوني b للرسوم البيانية المركبة المختلفة - Liu & Lu (2013): دراسة النظرية الطيفية لتيجان SVN - Brooks (1941): النتائج الكلاسيكية لتلوين الرسوم البيانية