DOI: https://doi.org/10.1016/j.disc.2025.114972
تاريخ النشر: 2026-01-05
المؤلف: Csilla Bujtás وآخرون
الموضوع الرئيسي: أبحاث نظرية الرسوم البيانية المتقدمة
نظرة عامة
عدد الهيمنة بالتعبئة على مسافة d، والذي يُرمز له بـ $\gamma^p_d(G)$، يمثل أصغر حجم لمجموعة من الرؤوس في رسم بياني $G$ تعمل كمجموعة هيمنة على مسافة d ومجموعة تعبئة p. في عام 1994، تخمّن بينيكي وهينينغ أنه بالنسبة لأي شجرة $T$ من الرتبة $n \geq d + 1$ و$d \geq 1$، فإن عدم المساواة $\gamma^1_d(T) \leq n^{d+1}$ صحيحة. وقد تحققوا من صحة هذه التخمينات لقيم محددة من $d$ (1، 2، و3).
تقوم هذه الورقة بتوسيع نتائجهم من خلال إثبات أن عدم المساواة $\gamma^1_d(G) \leq n^{d+1}$ صحيحة لأي رسم بياني ثنائي القطب $G$ برتبة $n \geq d + 1$ وأي $d \geq 1$. بالإضافة إلى ذلك، تصف الأشجار $T$ التي تحقق $\gamma^1_d(T) = n^{d+1}$ وتثبت أنه إذا كانت الشجرة $T$ تحتوي على $\ell$ أوراق، فإن $\gamma^1_d(T) \leq n – \ell^{d}$ (بشرط أن يكون $n – \ell \geq d$) و$\gamma^1_d(T) \leq n + \ell^{d+2}$ (بشرط أن يكون $n \geq d$). هذه النتيجة الأخيرة تعمّم نظرية فافارون لعام 1992، التي ذكرت أن $\gamma^1_1(T) \leq n + \ell^{3}$. كما تحدد الورقة الأشجار التي تحقق المساواة في هذه عدم المساوات وتناقش الآثار المترتبة على عدد الهيمنة على مسافة d للأشجار.
مقدمة
في هذا القسم، يقدم المؤلفون مفهوم عدد الهيمنة بالتعبئة على مسافة $d$، والذي يُرمز له بـ $\gamma^p_d(G)$، لرسم بياني $G = (V(G), E(G))$. يتم تعريف مجموعة فرعية $S \subseteq V(G)$ كمجموعة هيمنة على مسافة $d$ إذا كان كل رأس ليس في $S$ ضمن مسافة $d$ من بعض الرؤوس في $S$. بالإضافة إلى ذلك، تعتبر $S$ تعبئة $p$ إذا كانت المسافة بين أي رأسين متميزين في $S$ لا تقل عن $p + 1$. تشير الورقة إلى الأعمال السابقة التي أثبتت NP-completeness لتحديد $\gamma^p_d(G) \leq k$ للرسم البياني الثنائي القطب المخطط وتقدم حدودًا للأشجار، بما في ذلك $\gamma^0_2(T) \geq n – \ell – s + 4$ و$\gamma^{2}_d(T) \leq \frac{n – 2\sqrt{n} + d + 1}{d}$ لـ $d \geq 2$.
تركز الورقة على الثوابت $\gamma_d$ و$\gamma^1_d$، حيث يتم تبسيط $\gamma_d$ من $\gamma^0_d$ ويتعلق بعدد الهيمنة على مسافة $d$، بينما تتعلق $\gamma^1_d$ بمجموعات الهيمنة على مسافة $d$ التي هي أيضًا مجموعات مستقلة. يلخص المؤلفون النتائج المهمة من الدراسات السابقة، بما في ذلك الحدود والتخمينات المتعلقة بهذه الثوابت في الأشجار، ويحددون أهدافهم لإثبات هذه الحدود للرسم البياني الثنائي القطب وتوصيف الأشجار التي تحقق قيم محددة من $\gamma^1_d(T)$. تمهد المقدمة الطريق لاستكشاف المزيد من هذه المفاهيم وآثارها في نظرية الرسوم البيانية.
نقاش
في هذا القسم، يثبت المؤلفون نتائج مهمة تتعلق بتقسيم الرؤوس في الرسوم البيانية الثنائية القطب المتصلة إلى مجموعات هيمنة مستقلة، مع التركيز بشكل خاص على المعامل $\gamma_1^d(G)$. تُظهر النظرية 2.1 أنه بالنسبة لأي عدد صحيح $d \geq 1$، يمكن تقسيم رسم بياني ثنائي القطب متصل $G$ يحتوي على ما لا يقل عن $d + 1$ رأس إلى $d + 1$ مجموعة هيمنة مستقلة تكون على مسافة $d$. يتضمن الإثبات تحليل قطر الرسم البياني وبناء مستويات المسافة من رأس مختار، مما يظهر في النهاية أن كل مجموعة في التقسيم مستقلة وتسيطر على الرسم البياني بفعالية.
توسع النتيجة 2.2 هذه النتيجة، حيث تقدم حدًا أعلى لـ $\gamma_1^d(G)$، مشيرة إلى أنه بالنسبة للرسوم البيانية الثنائية القطب برتبة $n \geq d + 1$، فإن $\gamma_1^d(G) \leq \frac{n}{d + 1}$. تعمّم هذه النتيجة النتائج السابقة وتبرز أن الحد الأعلى قد لا يكون صحيحًا للرسوم البيانية غير الثنائية القطب، كما يتضح من أمثلة محددة. يستكشف القسم أيضًا الأشجار التي تحقق المساواة في هذا الحد، مما يؤدي إلى النظرية 3.4، التي تصف الأشجار من الرتبة $n$ التي تحقق $\gamma_1^d(T) = \frac{n}{d + 1}$. يختتم المؤلفون بمناقشة آثار هذه النتائج على هيكل الأشجار ومجموعات الهيمنة الخاصة بها، مع التأكيد على الشروط التي يتم فيها تحقيق المساواة.
DOI: https://doi.org/10.1016/j.disc.2025.114972
Publication Date: 2026-01-05
Author(s): Csilla Bujtás et al.
Primary Topic: Advanced Graph Theory Research
Overview
The d-distance p-packing domination number, denoted as $\gamma^p_d(G)$, represents the smallest size of a vertex set in a graph $G$ that serves as both a d-distance dominating set and a p-packing. In 1994, Beineke and Henning conjectured that for any tree $T$ of order $n \geq d + 1$ and $d \geq 1$, the inequality $\gamma^1_d(T) \leq n^{d+1}$ holds. They validated this conjecture for specific values of $d$ (1, 2, and 3).
This paper extends their findings by proving that the inequality $\gamma^1_d(G) \leq n^{d+1}$ is valid for any bipartite graph $G$ with order $n \geq d + 1$ and for any $d \geq 1$. Additionally, it characterizes trees $T$ for which $\gamma^1_d(T) = n^{d+1}$ and establishes that if a tree $T$ has $\ell$ leaves, then $\gamma^1_d(T) \leq n – \ell^{d}$ (given that $n – \ell \geq d$) and $\gamma^1_d(T) \leq n + \ell^{d+2}$ (given that $n \geq d$). This latter result generalizes Favaron’s 1992 theorem, which stated that $\gamma^1_1(T) \leq n + \ell^{3}$. The paper also identifies trees that achieve equality in these inequalities and discusses implications for the d-distance domination number of trees.
Introduction
In this section, the authors introduce the concept of the $d$-distance $p$-packing domination number, denoted as $\gamma^p_d(G)$, for a graph $G = (V(G), E(G))$. A subset $S \subseteq V(G)$ is defined as a $d$-distance dominating set if every vertex not in $S$ is within a distance $d$ from some vertex in $S$. Additionally, $S$ is a $p$-packing if the distance between any two distinct vertices in $S$ is at least $p + 1$. The paper references previous work that established the NP-completeness of determining $\gamma^p_d(G) \leq k$ for bipartite planar graphs and presents bounds for trees, including $\gamma^0_2(T) \geq n – \ell – s + 4$ and $\gamma^{2}_d(T) \leq \frac{n – 2\sqrt{n} + d + 1}{d}$ for $d \geq 2$.
The focus of the paper is on the invariants $\gamma_d$ and $\gamma^1_d$, where $\gamma_d$ is simplified from $\gamma^0_d$ and relates to the $d$-distance domination number, while $\gamma^1_d$ pertains to $d$-distance dominating sets that are also independent sets. The authors summarize significant results from prior studies, including bounds and conjectures regarding these invariants in trees, and outline their objectives to prove these bounds for bipartite graphs and characterize trees achieving specific values of $\gamma^1_d(T)$. The introduction sets the stage for further exploration of these concepts and their implications in graph theory.
Discussion
In this section, the authors establish significant results regarding the partitioning of vertices in connected bipartite graphs into independent dominating sets, specifically focusing on the parameter $\gamma_1^d(G)$. Theorem 2.1 demonstrates that for any integer $d \geq 1$, a connected bipartite graph $G$ with at least $d + 1$ vertices can be partitioned into $d + 1$ independent dominating sets that are $d$-distance apart. The proof involves analyzing the graph’s diameter and constructing distance levels from a chosen root vertex, ultimately showing that each set in the partition is independent and dominates the graph effectively.
Corollary 2.2 extends this result, providing an upper bound for $\gamma_1^d(G)$, stating that for bipartite graphs of order $n \geq d + 1$, $\gamma_1^d(G) \leq \frac{n}{d + 1}$. This corollary generalizes previous findings and highlights that the upper bound may not hold for non-bipartite graphs, as illustrated by specific examples. The section further explores trees that achieve equality in this bound, leading to Theorem 3.4, which characterizes trees of order $n$ for which $\gamma_1^d(T) = \frac{n}{d + 1}$. The authors conclude by discussing the implications of these results for the structure of trees and their dominating sets, emphasizing the conditions under which equality is attained.