حقن الهيمنة غريب الأطوار في الرسوم البيانية

الملخص

لقد ألهم مفهوم الهيمنة الباحثين الذين ساهموا في تأليف مؤلفات واسعة حول الهيمنة. يقال أن المجموعة الفرعية D من V هي مجموعة مهيمنة، إذا كان كل قمة ليست في D مجاورة لقمة واحدة على الأقل في D. الانحراف المركزي e(v) لـ v هو المسافة إلى الرأس الأبعد من v. وبالتالي فان e(v)=max⁡{d(u,v):u∈V} . بالنسبة للقمة v، كل قمة على مسافة e(v) من v هي قمة غريبة الأطوار. يتم تعريف المجموعة اللامركزية للقمة v على أنه E(v)={u∈V(G):d(u,v)=e(v)} E(v)={u∈V(G):d(u,v)=e(v)}. على فرض S⊆V(G)، إذن S تُعرف بمجموعة نقاط غريب الأطوار من G إذا كان لكل v∈V-S ، S لديه قمة واحدة على الأقل u حيث u∈E(v). تسمى المجموعة المهيمنة S بالمجموعة المهيمنة اللامركزية إذا كانت أيضًا مجموعة نقطية غريبة الأطوار. في هذه المقالة يتم تقديم مفهوم الهيمنة اللامركزية عن طريق الحقن للرسوم البيانية البسيطة والمتصلة وغير الموجهة. تُسمى المجموعة المسيطرة اللامركزية S بالمجموعة المهيمنة اللامركزية إذا كان لكل رأس v∈V-S رأس u∈S بحيث تكون Γ(v,u)|≥11|Γ(v,u)|≥11 حيث Γ(v,u)Γ(v,u) هي مجموعة الرؤوس المختلفة عن v و u، المجاورتين لكل من v و u ‏. تم ذكر وإثبات النظريات لتحديد رقم التحكم اللامركزي الدقيق للفئة الأساسية من الرسوم البيانية. كما تم اقتراح نتائج Nordhaus-Gaddum. يتم جدولة مجموعة السيطرة اللامركزية عن طريق الحقن، ورقم الهيمنة اللامركزية عن طريق الحقن γ_ined (G)، ومجموعة الهيمنة اللامركزية عن طريق الحقن العليا ورقم الهيمنة اللامركزية عن طريق الحقن Γ_ined (G) للرسوم البيانية القياسية المختلفة