2025-11-10T02:45:05.969614

On a Conjecture Concerning the Complementary Second Zagreb Index

Saber, Alraqad, Ali et al.
The complementary second Zagreb index of a graph $G$ is defined as $cM_2(G)=\sum_{uv\in E(G)}|(d_u(G))^2-(d_v(G))^2|$, where $d_u(G)$ denotes the degree of a vertex $u$ in $G$ and $E(G)$ represents the edge set of $G$. Let $G^*$ be a graph having the maximum value of $cM_2$ among all connected graphs of order $n$. Furtula and Oz [MATCH Commun. Math. Comput. Chem. 93 (2025) 247--263] conjectured that $G^*$ is the join $K_k+\overline{K}_{n-k}$ of the complete graph $K_k$ of order $k$ and the complement $\overline{K}_{n-k}$ of the complete graph $K_{n-k}$ such that the inequality $k<\lceil n/2 \rceil$ holds. We prove that (i) the maximum degree of $G^*$ is $n-1$ and (ii) no two vertices of minimum degree in $G^*$ are adjacent; both of these results support the aforementioned conjecture. We also prove that the number of vertices of maximum degree in $G^*$, say $k$, is at most $-\frac{2}{3}n+\frac{3}{2}+\frac{1}{6}\sqrt{52n^2-132n+81}$, which implies that $k<5352n/10000$. Furthermore, we establish results that support the conjecture under consideration for certain bidegreed and tridegreed graphs. In the aforesaid paper, it was also mentioned that determining the $k$ as a function of the $n$ is far from being an easy task; we obtain the values of $k$ for $5\le n\le 149$ in the case of certain bidegreed graphs by using computer software and found that the resulting sequence of the values of $k$ does not exist in "The On-Line Encyclopedia of Integer Sequences" (an online database of integer sequences).
academic

حول حدسية تتعلق بمؤشر زغرب الثاني المتمم

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

  • معرّف الورقة: 2501.01295
  • العنوان: حول حدسية تتعلق بمؤشر زغرب الثاني المتمم
  • المؤلفون: Hicham Saber, Tariq Alraqad, Akbar Ali, Abdulaziz M. Alanazi, Zahid Raza
  • التصنيف: math.CO (الرياضيات التوافقية)
  • تاريخ النشر: تم تقديمه إلى arXiv في 2 يناير 2025
  • رابط الورقة: https://arxiv.org/abs/2501.01295

الملخص

تتناول هذه الورقة مسائل القيم القصوى لمؤشر زغرب الثاني المتمم للرسوم البيانية. يُعرّف مؤشر زغرب الثاني المتمم بالصيغة cM2(G)=∑uv∈E(G)∣(du(G))2−(dv(G))2∣cM_2(G)=\sum_{uv\in E(G)}|(d_u(G))^2-(d_v(G))^2|، حيث du(G)d_u(G) تمثل درجة الرأس uu في الرسم البياني GG. يقدم المؤلفون دراسة متعمقة للحدسية التي طرحها Furtula و Oz، والتي تؤكد أن الرسم البياني G∗G^* الذي يحقق القيمة العظمى لـ cM2cM_2 بين جميع الرسوم البيانية المتصلة من الرتبة nn هو الاتصال بين الرسم البياني الكامل KkK_k ومتممه K‾n−k\overline{K}_{n-k}، حيث k<⌈n/2⌉k<\lceil n/2 \rceil.

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

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

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

دافع البحث

  1. الكمال النظري: طرح Furtula و Oz في عام 2025 حدسية حول بنية الرسوم البيانية ذات القيم القصوى لمؤشر CSZ، لكنها تفتقر إلى إثبات رياضي صارم.
  2. التعقيد الحسابي: يُعتبر تحديد عدد الرؤوس ذات الدرجة العظمى kk كدالة لـ nn في الرسم البياني ذي القيمة القصوى مسألة "بعيدة كل البعد عن أن تكون سهلة"، وتتطلب أدوات نظرية وطرق حسابية جديدة.
  3. القيمة التطبيقية: يحمل فهم الخصائص القصوى لمؤشر CSZ أهمية كبيرة لنظرية الرسوم البيانية الكيميائية وتصميم الجزيئات.

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

تتضمن المساهمات الرئيسية للورقة ما يلي:

  1. إثبات خصائص الدرجة العظمى للرسم البياني ذي القيمة القصوى: يثبت أن الرسم البياني المتصل من الرتبة nn الذي يحقق القيمة العظمى لـ cM2cM_2 يتمتع بدرجة عظمى تساوي n−1n-1.
  2. الكشف عن خصائص التجاور للرؤوس ذات الدرجة الصغرى: يثبت أن أي رأسين من الرؤوس ذات الدرجة الصغرى في G∗G^* غير متجاورين.
  3. إنشاء حد أعلى لعدد الرؤوس ذات الدرجة العظمى: يثبت أن عدد الرؤوس ذات الدرجة العظمى kk في G∗G^* يحقق: k≤−23n+32+1652n2−132n+81<5352n10000k \leq -\frac{2}{3}n+\frac{3}{2}+\frac{1}{6}\sqrt{52n^2-132n+81} < \frac{5352n}{10000}
  4. التحقق من الحدسية لفئات رسومية خاصة: يثبت صحة حدسية Furtula-Oz للرسوم البيانية ثنائية الدرجة والثلاثية الدرجة.
  5. توفير بيانات حسابية: من خلال البرامج الحاسوبية، تم حساب قيم kk للرسوم البيانية ثنائية الدرجة في النطاق 5≤n≤1495 \leq n \leq 149، وتبين أن السلسلة الناتجة غير موجودة في موسوعة المتتاليات الصحيحة على الإنترنت.

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

تعريف المهمة

دراسة البنية الرسومية التي تحقق القيمة العظمى لمؤشر زغرب الثاني المتمم cM2(G)=∑uv∈E(G)∣(du(G))2−(dv(G))2∣cM_2(G) = \sum_{uv\in E(G)}|(d_u(G))^2-(d_v(G))^2| بين جميع الرسوم البيانية المتصلة من الرتبة nn.

النظريات الأساسية وطرق الإثبات

النظرية 1 (القضية 2): خصائص الدرجة العظمى

الصيغة: إذا كان الرسم البياني GG يتمتع بأكبر قيمة cM2cM_2 بين جميع الرسوم البيانية المتصلة من الرتبة nn، و n≥4n \geq 4، فإن الدرجة العظمى لـ GG تساوي n−1n-1.

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

  1. نفترض أن الدرجة العظمى Δ<n−1\Delta < n-1، ونختار رأساً vv بدرجة Δ\Delta ورأساً uu غير متجاور مع vv
  2. نبني الرسم البياني G′G' بإضافة الحافة uvuv
  3. نحسب cM2(G′)−cM2(G)cM_2(G') - cM_2(G) ونثبت أن هذا الفرق موجب، وهو تناقض مع كون GG ذا قيمة قصوى

النظرية 2 (القضية 3): عدم التجاور بين الرؤوس ذات الدرجة الصغرى

الصيغة: في الرسم البياني ذي القيمة القصوى GG، أي رأسان من الرؤوس ذات الدرجة الصغرى غير متجاورين.

طريقة الإثبات: باستخدام البرهان بالتناقض، نفترض وجود رأسين متجاورين بدرجة صغرى، وإزالة الحافة بينهما ستزيد من قيمة cM2cM_2.

النظرية 3 (القضية 4): الحد الأعلى لعدد الرؤوس ذات الدرجة العظمى

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

  1. نختار حافة تربط رأساً بدرجة عظمى برأس بدرجة صغرى ونزيلها
  2. نحلل تأثير إزالة هذه الحافة على قيمة cM2cM_2
  3. نؤسس متباينة تربيعية بشأن kk
  4. نحل المتباينة للحصول على صيغة الحد الأعلى

تحليل فئات رسومية خاصة

التوصيف الكامل للرسوم البيانية ثنائية الدرجة (القضية 5)

بالنسبة للرسم البياني المتصل ثنائي الدرجة من الرتبة nn بدرجة عظمى n−1n-1، يثبت أن: cM2(G)≤k(n−k)((n−1)2−k2)cM_2(G) \leq k(n-k)((n-1)^2 - k^2) يتحقق التساوي إذا وفقط إذا كان G=Kk+K‾n−kG = K_k + \overline{K}_{n-k}.

تحليل الرسوم البيانية ثلاثية الدرجة (القضية 7)

باستخدام أدوات المتباينات المؤسسة في اللمة 6، يتم تصنيف الرسوم البيانية ثلاثية الدرجة ومناقشة كل حالة، مما يثبت وجود بنية Kt+K‾n−tK_t + \overline{K}_{n-t} أفضل في كل حالة.

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

الطريقة الحسابية

استخدام البرامج الحاسوبية لإجراء حساب شامل للرسوم البيانية ثنائية الدرجة في النطاق 5≤n≤1495 \leq n \leq 149، وتحديد قيمة kk المثلى المقابلة لكل nn.

التحقق من البيانات

مقارنة سلسلة قيم kk المحسوبة مع قاعدة بيانات "موسوعة المتتاليات الصحيحة على الإنترنت".

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

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

يعرض الجدول 1 قيم kk المثلى المقابلة لـ nn من 5 إلى 149، على سبيل المثال:

  • عندما n=5n=5، k=2k=2
  • عندما n=10n=10، k=4k=4
  • عندما n=20n=20، k=8k=8
  • عندما n=50n=50، k=19k=19
  • عندما n=100n=100، k=39k=39
  • عندما n=149n=149، k=58k=58

جدة السلسلة

السلسلة المحسوبة 2,2,3,3,3,4,4,4,5,5,6,6,6,7,7,8,8,8,9,9,10,10,10,11,11,12,12,12,13,13,13,...2,2,3,3,3,4,4,4,5,5,6,6,6,7,7,8,8,8,9,9,10,10,10,11,11,12,12,12,13,13,13,... غير موجودة في قاعدة بيانات OEIS، مما يشير إلى أن هذه متتالية صحيحة جديدة.

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

تؤكد النتيجة الطبيعية 2 أنه بالنسبة للحالات n≥11n \geq 11، قيمة kk المثلى تحقق 3n10<k<4n10\frac{3n}{10} < k < \frac{4n}{10}، وهذا متسق مع النتائج المحسوبة.

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

تطور مؤشرات زغرب

  1. مؤشرات زغرب الكلاسيكية: مؤشر زغرب الثاني M2(G)=∑uv∈E(G)dudvM_2(G) = \sum_{uv \in E(G)} d_u d_v هو مؤشر كلاسيكي في نظرية الرسوم البيانية الكيميائية
  2. الطريقة الهندسية: الطريقة الهندسية التي قدمها Gutman توفر منظوراً جديداً لدراسة الفهارس الطوبولوجية المستندة إلى الدرجة
  3. الفهارس المتممة: تم اقتراح مؤشر CSZ بشكل مستقل في عدة دراسات، بأسماء مختلفة (مؤشر نانو زغرب، مؤشر F-minus، إلخ)

نظرية الرسوم البيانية القصوى

تستمر طرق البحث في هذه الورقة في الاستفادة من التقنيات الكلاسيكية لنظرية الرسوم البيانية القصوى، خاصة طريقة تحليل التغييرات في الفهارس الطوبولوجية من خلال تحويلات الرسوم البيانية.

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

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

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

القيود

  1. عدم اكتمال الإثبات للحالة العامة: بالنسبة للرسوم البيانية المتصلة العامة، لم يتم إثبات الحدسية بشكل كامل
  2. غياب الصيغة الدقيقة: الشكل الدقيق لـ kk كدالة لـ nn لا يزال غير معروف
  3. حدود النطاق الحسابي: يقتصر الحساب الحالي على الحالات حتى n=149n=149

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

  1. الإثبات الكامل: البحث عن إثبات رياضي كامل لحدسية Furtula-Oz
  2. السلوك التقاربي: دراسة الخصائص التقاربية والسلوك الحدي لـ k/nk/n
  3. تحسين الخوارزميات: تطوير خوارزميات أكثر كفاءة لحساب قيم kk الأكبر
  4. البحث الموسع: تعميم الطرق على أنواع أخرى من الفهارس الطوبولوجية

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

المميزات

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

أوجه القصور

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

التأثير

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

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

تنطبق طرق ونتائج هذه الورقة على:

  1. دراسة الواصفات الجزيئية في نظرية الرسوم البيانية الكيميائية
  2. التحليل النظري لنظرية الرسوم البيانية القصوى
  3. مسائل تحسين الفهارس الطوبولوجية المستندة إلى الدرجة
  4. التحسين التوافقي لبنية الرسوم البيانية

المراجع

تستشهد الورقة بـ 15 مرجعاً ذا صلة، تغطي مجالات متعددة منها الواصفات الجزيئية وأساسيات نظرية الرسوم البيانية ونظرية مؤشرات زغرب، حيث تشكل ورقة Furtula و Oz من عام 2025 الأساس المباشر لهذا البحث.