الحد الأدنى من هيمنة الجوار على الرسم البياني المقسم للرسوم البيانية
محتوى المقالة الرئيسي
الملخص
لنفترض أن رسم بياني بسيط غير تافه. المجموعة المسيطرة في الرسم البياني هي مجموعة من الرؤوس بحيث تكون كل قمة ليست في المجموعة مجاورة لرأس واحد على الأقل في المجموعة. المجموعة الفرعية D⊆V (G) هي مجموعة تهيمن على الجوار الأدنى إذا كانت D هي مجموعة مهيمنة وإذا كانت لكل تتحقق. يُطلق على الحد الأدنى من عدد العناصر لأدنى حد يهيمن على مجموعة الرسم البياني G على أنه الحد الأدنى من العدد المسيطر على الجوار ويُشار إليه بالرمز . الحد الأدنى للمجموعة المسيطرة على الجوار هو مجموعة مهيمنة حيث يكون تقاطع اللجوارات لجميع الرؤوس في المجموعة صغيرًا قدر الإمكان. الحد الأدنى للرقم المسيطر على الحي ، الذي يُشار إليه بالرمز ، هو الحد الأدنى لعدد العناصر المسيطرة على الجوار. بمعنى آخر ، هو أصغر عدد من الرؤوس اللازمة لتشكيل مجموعة مسيطرة على الجوار الأدنى. يرتبط هذا المفهوم بدراسة بنية وخصائص الرسوم البيانية ويستخدم في مختلف المجالات مثل علوم الكمبيوتر وبحوث العمليات وتصميم الشبكات. تعتبر مجموعة السيطرة على الجوار الأدنى مفيدة أيضًا في دراسة نظرية الرسم البياني ولها تطبيقات في مجالات مثل تصميم الشبكة ونظرية التحكم. هذا المفهوم هو تباين في مشكلة المجموعة المهيمنة التقليدية ويضيف قيدًا إضافيًا على تقاطع الجوارات للرؤوس في المجموعة. كما إنها تعتبر مشكلة NP - صعبة .الهدف الرئيسي من هذه الورقة هو دراسة الحد الأدنى لعدد هيمنة الجوارات للرسم البياني المقسم لبعض الرسوم البيانية.
Received 20/1/2023
Revised 13/2/2023
Accepted 14/2/2023
Published 1/3/2023
تفاصيل المقالة
هذا العمل مرخص بموجب Creative Commons Attribution 4.0 International License.
كيفية الاقتباس
المراجع
Cockayne EJ, Hedetniemi ST. Optimal Domination in Graphs. IEEE Trans Circuits Syst. 1975; 22(11): 855 – 857.
Bermudo S, Gómez JCH, Sigarreta JM. Total k-Domination in Graphs. Discuss. Math Graph Theory. 2018; 38: 301–317.
Al-Harere MN, Mitlif RJ, Sadiq FA. Variant Domination Types for a Complete h-Ary Tree. Baghdad Sci J. 2021; 18(1(Suppl.)): 797-802. https://doi.org/10.21123/bsj.2021.18.1(Suppl.).0797
Martínez AC, Mira HFA, Sigarreta JM, Yero IG. On Computational and Combinatorial Properties of the Total Co-Independent Domination Number of Graphs. Comput J. 2019, 62(1): 97–108. https://doi.org/10.1093/comjnl/bxy038
Aslam A, Nadeem MF, Zahid Z, Zafar S, Gao W. Computing Certain Topological Indices of the Line Graphs of Subdivision Graphs of Some Rooted Product Graphs. Mathematics. 2019; 7(5): 393.
Omran AA, Oda HH. Hn-Domination in Graphs. Baghdad Sci J. 2019; 16(1(Suppl.)): 242-247. https://doi.org/10.21123/bsj.2019.16.1(Suppl.).0242
Al-Harere MN, Bakhash PAK. Tadpole Domination in Graphs. Baghdad Sci J. 2018; 15(4): 466-471. https://doi.org/10.21123/bsj.2018.15.4.0466
Daoud SN, Mohamed K. The Complexity of Some Families of Cycle-Related Graphs. J Taibah Univ Sci. 2017; 11(2): 205-228. https://doi.org/10.1016/j.jtusci.2016.04.002
Bertossi AA. Dominating Sets for Split and Bipartite Graphs. Inf Process Lett. 1984; 19(1): 37-40. https://doi.org/10.1016/0020-0190(84)90126-1