عدد هيمنة التعبئة p-distance: التعقيد، الدورات، والأشجار The d-distance p-packing domination number: complexity, cycles, and trees

المجلة: Aequationes Mathematicae، المجلد: 100، العدد: 2
DOI: https://doi.org/10.1007/s00010-026-01266-w
تاريخ النشر: 2026-02-20
المؤلف: Csilla Bujtá وآخرون
الموضوع الرئيسي: الحدود والهياكل في نظرية الرسوم البيانية

نظرة عامة

تقدم هذه القسم دراسة حول مفاهيم مجموعات الهيمنة ذات المسافة d والتعبئة p ضمن نظرية الرسوم البيانية، مع التركيز بشكل خاص على عدد هيمنة التعبئة p ذات المسافة d، والذي يُرمز له بـ $\gamma_{p}^{d}(G)$. تعتبر مجموعة من الرؤوس $ X \subseteq V(G) $ مجموعة هيمنة ذات مسافة d إذا كانت كل رأس $ u \in V(G) \setminus X $ ضمن مسافة $ d $ من على الأقل رأس واحد في $ X $. بالإضافة إلى ذلك، فإن $ X $ هي تعبئة p إذا كانت المسافة بين أي رأسين متميزين $ u, v \in X $ لا تقل عن $ p + 1 $. تؤكد الأبحاث أن تحديد ما إذا كانت $ \gamma_{p}^{d}(G) \leq k $ هو NP-complete للرسوم البيانية الثنائية التخطيط عندما تكون $ d $ و $ p $ أعداد صحيحة ثابتة ضمن نطاقات محددة.

علاوة على ذلك، يستنتج المؤلفون شرطًا ضروريًا وكافيًا لوجود مجموعة هيمنة تعبئة p ذات مسافة d في الدورات $ C_n $ ويحسبون $ \gamma_{p}^{d}(C_n) $ لجميع قيم $ d $، $ p $، و $ n $. بالنسبة للأشجار $ T $ التي تحتوي على $ n $ رأسًا، و $ \ell $ أوراق، و $ s $ رؤوس دعم، يحسن البحث الحدود السابقة التي وضعتها مايرلينغ وفولكمان، بالإضافة إلى راكزيك، ليمانيسكا، وسيمان. كما أنه يوسع النتائج السابقة المتعلقة بـ $ \gamma_{2}^{2}(T) $ بواسطة هينينغ. يتم مناقشة حدة الحدود المستنتجة، ويظهر أن كل رسم بياني متصل $ G $ يحتوي على شجرة ممتدة $ T $ بحيث \( \gamma_{2}^{2}(T) \leq \gamma_{2}^{2}(G) \.

مقدمة

في هذا القسم، يقدم المؤلفون مفهوم عدد هيمنة التعبئة p ذات المسافة $d$، والذي يُرمز له بـ $\gamma_p^d(G)$، لرسم بياني $G = (V(G), E(G))$. يمثل هذا العدد الحد الأدنى لحجم مجموعة من الرؤوس التي تعمل كلاً من مجموعة هيمنة ذات مسافة $d$ وتعبئة $p$. بشكل محدد، تعتبر مجموعة $X \subseteq V(G)$ مجموعة هيمنة ذات مسافة $d$ إذا كانت كل رأس ليست في $X$ ضمن مسافة $d$ من على الأقل رأس واحد في $X$. تتطلب تعبئة $p$ أن تكون المسافة بين أي رأسين في $X$ لا تقل عن $p + 1$. يشير المؤلفون إلى أنه إذا كان $d < p$، فقد لا توجد مثل هذه المجموعة، مما يؤدي إلى $\gamma_p^d(G) = \infty$. يضع البحث هذا المفهوم في سياق أوسع ضمن إطار نظرية هيمنة الرسوم البيانية، مشيرًا إلى الأعمال السابقة من بينيكي وهينينغ من عام 1994. يبرز العديد من الحالات الخاصة لعدد هيمنة التعبئة $d$-distance $p$، بما في ذلك عدد الهيمنة التقليدي $\gamma(G)$ (عندما يكون $d = 0$ و $p = 1$) وعدد الهيمنة المستقلة $i(G)$ (عندما يكون $d = 1$ و $p = 1$). يناقش المؤلفون أيضًا آثار قيم معينة لـ $d$ و $p$، مشيرين إلى أنه بالنسبة للرسوم البيانية المتصلة ذات خصائص معينة، يمكن أن يكون عدد الهيمنة غير محدود. يضع القسم الأساس لاستكشاف مفصل لعدد هيمنة التعبئة 2 ذات المسافة $d$، خاصة في سياق الأشجار، مشيرًا إلى الأدبيات ذات الصلة للحصول على مزيد من الرؤى.

النتائج

في هذا القسم، يثبت المؤلفون أن مشكلة القرار حول ما إذا كانت $ \gamma_p^d(G) \leq k $ هي NP-complete للأعداد الصحيحة الثابتة $ d $ و $ p $ (مع $ 2 \leq d $ و $ 0 \leq p \leq 2d – 1 $) عندما تقتصر على الرسوم البيانية الثنائية التخطيط. علاوة على ذلك، يظهرون أن هذه NP-completeness تمتد إلى الرسوم البيانية التخطيطية عندما يكون $ p = 2d $. بينما تم إظهار صعوبة NP للرسوم البيانية الثنائية سابقًا لـ $ d = p \geq 3 $، يصحح المؤلفون خطأً في الإثبات للحالة $ d = p = 2 $.

بالإضافة إلى ذلك، يقدم المؤلفون تحليلًا شاملاً للقيمة الدقيقة لـ $ \gamma_p^d(C_n) $ لجميع الأعداد الصحيحة $ d $، $ p $، و $ n $، بما في ذلك شرط ضروري وكافي لوجود مجموعة هيمنة تعبئة $ p $ ذات مسافة $ d $ في رسم بياني الدورة $ C_n $. كما يحددون القيمة الدقيقة لـ $ \gamma_p^d(P_n) $ لجميع الحالات. ثم يتحول التركيز إلى الأشجار، مع تعريف مجموعة $ T_d $ من الأشجار حيث تكون الأوراق متباعدة عن بعضها البعض بمسافة $ 2d $ (mod $ 2d + 1 $). يبني هذا على الأعمال السابقة، موسعًا النتائج لـ $ d = 1 $ إلى حالات أوسع.

المناقشة

في هذا القسم، يقدم المؤلفون تعريفات ونظريات أساسية تتعلق بنظرية الرسوم البيانية، مع التركيز بشكل خاص على مفاهيم مجموعات الهيمنة والانحراف في الأشجار والرسوم البيانية. يعرفون أحياء مختلفة، بما في ذلك الحي المغلق $ N[v] $ وحي المسافة $ k $ $ N_k[v] $. يتم تعريف انحراف رأس $ v $ على أنه $ \text{ecc}(v) = \max\{d(v, x) : x \in V(G)\} $، مما يؤدي إلى تعريفات نصف القطر $ \text{rad}(G) $ وقطر $ \text{diam}(G) $ لرسم بياني $ G $. يقدم القسم عدة نظريات، لا سيما النظرية 1.2، التي تؤسس حدًا أدنى لرمز $ d $-perfect في الأشجار، والنظرية 1.3، التي تصقل هذا الحد للأشجار ذات الخصائص المحددة. تستكشف النظريتان 1.4 و1.5 المزيد من الحدود على مجموعة الهيمنة ذات المسافة $ 2 $ في الأشجار، مما يظهر حدة هذه الحدود.

علاوة على ذلك، يناقش المؤلفون NP-completeness لمشكلة القرار المتعلقة بوجود $ \gamma_p^d(G) $ في الرسوم البيانية الثنائية التخطيط، مؤكدين أن هذا ينطبق على الأعداد الصحيحة الثابتة $ d $ و $ p $ تحت ظروف معينة. يوضحون بناء الرسوم البيانية من حالات مشاكل Planar 3-SAT وPlanar 1-in-3-SAT، موضحين كيف تؤدي هذه البنايات إلى نتائج صعوبة NP. يختتم القسم بمناقشة حول الدورات والمسارات، موفرًا قيمًا دقيقة لـ $ \gamma_p^d(C_n) $ و $ \gamma_p^d(P_n) $، ويؤكد على الشروط التي تكون فيها هذه القيم محدودة أو غير محدودة. بشكل عام، تسهم النتائج بشكل كبير في فهم مجموعات الهيمنة في نظرية الرسوم البيانية وتعقيداتها الحسابية.

Journal: Aequationes Mathematicae, Volume: 100, Issue: 2
DOI: https://doi.org/10.1007/s00010-026-01266-w
Publication Date: 2026-02-20
Author(s): Csilla Bujtá et al.
Primary Topic: Limits and Structures in Graph Theory

Overview

The section presents a study on the concepts of d-distance dominating sets and p-packings within graph theory, specifically focusing on the d-distance p-packing domination number, denoted as $\gamma_{p}^{d}(G)$. A set of vertices $ X \subseteq V(G) $ qualifies as a d-distance dominating set if every vertex $ u \in V(G) \setminus X $ is within a distance $ d $ of at least one vertex in $ X $. Additionally, $ X $ is a p-packing if the distance between any two distinct vertices $ u, v \in X $ is at least $ p + 1 $. The research establishes that determining whether $ \gamma_{p}^{d}(G) \leq k $ is NP-complete for bipartite planar graphs when $ d $ and $ p $ are fixed integers within specified ranges.

Furthermore, the authors derive a necessary and sufficient condition for the existence of a d-distance p-packing dominating set in cycles $ C_n $ and compute $ \gamma_{p}^{d}(C_n) $ for all values of $ d $, $ p $, and $ n $. For trees $ T $ with $ n $ vertices, $ \ell $ leaves, and $ s $ support vertices, the paper improves upon previous bounds established by Meierling and Volkmann, as well as Raczek, Lemańska, and Cyman. It also extends earlier results related to $ \gamma_{2}^{2}(T) $ by Henning. The sharpness of the derived bounds is discussed, and it is shown that every connected graph $ G $ contains a spanning tree $ T $ such that $ \gamma_{2}^{2}(T) \leq \gamma_{2}^{2}(G) $.

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))$. This number represents the minimum size of a set of vertices that serves both as a $d$-distance dominating set and a $p$-packing. Specifically, a set $X \subseteq V(G)$ is a $d$-distance dominating set if every vertex not in $X$ is within a distance $d$ from at least one vertex in $X$. A $p$-packing requires that the distance between any two vertices in $X$ is at least $p + 1$. The authors note that if $d < p$, such a set may not exist, leading to $\gamma_p^d(G) = \infty$. The paper contextualizes this concept within the broader framework of graph domination theory, referencing earlier work by Beineke and Henning from 1994. It highlights several special cases of the $d$-distance $p$-packing domination number, including the traditional domination number $\gamma(G)$ (when $d = 0$ and $p = 1$) and the independent domination number $i(G)$ (when $d = 1$ and $p = 1$). The authors also discuss the implications of specific values of $d$ and $p$, noting that for connected graphs with certain properties, the domination number can be infinite. The section sets the stage for a detailed exploration of the $d$-distance 2-packing domination number, particularly in the context of trees, referencing relevant literature for further insights.

Results

In this section, the authors establish that the decision problem of whether $ \gamma_p^d(G) \leq k $ is NP-complete for fixed integers $ d $ and $ p $ (with $ 2 \leq d $ and $ 0 \leq p \leq 2d – 1 $) when restricted to bipartite planar graphs. Furthermore, they demonstrate that this NP-completeness extends to planar graphs when $ p = 2d $. While NP-hardness for bipartite graphs was previously shown for $ d = p \geq 3 $, the authors correct an error in the proof for the case $ d = p = 2 $.

Additionally, the authors provide a comprehensive analysis of the exact value of $ \gamma_p^d(C_n) $ for all integers $ d $, $ p $, and $ n $, including a necessary and sufficient condition for the existence of a $ d $-distance $ p $-packing dominating set in the cycle graph $ C_n $. They also determine the exact value of $ \gamma_p^d(P_n) $ for all cases. The focus then shifts to trees, specifically defining the set $ T_d $ of trees where leaves are pairwise at a distance of $ 2d $ (mod $ 2d + 1 $). This builds on prior work, extending results for $ d = 1 $ to broader cases.

Discussion

In this section, the authors introduce essential definitions and theorems related to graph theory, particularly focusing on the concepts of dominating sets and eccentricity in trees and graphs. They define various neighborhoods, including the closed neighborhood $ N[v] $ and the $ k $-distance neighborhood $ N_k[v] $. The eccentricity of a vertex $ v $ is defined as $ \text{ecc}(v) = \max\{d(v, x) : x \in V(G)\} $, leading to the definitions of the radius $ \text{rad}(G) $ and diameter $ \text{diam}(G) $ of a graph $ G $. The section presents several theorems, notably Theorem 1.2, which establishes a lower bound for the $ d $-perfect code in trees, and Theorem 1.3, which refines this bound for trees with specific properties. Theorems 1.4 and 1.5 further explore the bounds on the $ 2 $-distance dominating set in trees, demonstrating the sharpness of these bounds.

Additionally, the authors discuss the NP-completeness of the decision problem regarding the existence of $ \gamma_p^d(G) $ in planar bipartite graphs, establishing that this holds for fixed integers $ d $ and $ p $ under certain conditions. They detail the construction of graphs from instances of Planar 3-SAT and Planar 1-in-3-SAT problems, illustrating how these constructions lead to NP-hardness results. The section concludes with a discussion on cycles and paths, providing exact values for $ \gamma_p^d(C_n) $ and $ \gamma_p^d(P_n) $, and emphasizing the conditions under which these values are finite or infinite. Overall, the findings contribute significantly to the understanding of dominating sets in graph theory and their computational complexities.