اشترك بالحزمة الذهبية واحصل على وصول غير محدود شمرا أكاديميا
تسجيل مستخدم جديدOn the $2$-packing differential of a graph
73
0
0.0
(
0
)
اسأل ChatGPT حول البحث
ﻻ يوجد ملخص باللغة العربية
Let $G$ be a graph of order $n(G)$ and vertex set $V(G)$. Given a set $Ssubseteq V(G)$, we define the external neighbourhood of $S$ as the set $N_e(S)$ of all vertices in $V(G)setminus S$ having at least one neighbour in $S$. The differential of $S$ is defined to be $partial(S)=|N_e(S)|-|S|$. In this paper, we introduce the study of the $2$-packing differential of a graph, which we define as $partial_{2p}(G)=max{partial(S): Ssubseteq V(G) text{ is a }2text{-packing}}.$ We show that the $2$-packing differential is closely related to several graph parameters, including the packing number, the independent domination number, the total domination number, the perfect differential, and the unique response Roman domination number. In particular, we show that the theory of $2$-packing differentials is an appropriate framework to investigate the unique response Roman domination number of a graph without the use of functions. Among other results, we obtain a Gallai-type theorem, which states that $partial_{2p}(G)+mu_{_R}(G)=n(G)$, where $mu_{_R}(G)$ denotes the unique response Roman domination number of $G$. As a consequence of the study, we derive several combinatorial results on $mu_{_R}(G)$, and we show that the problem of finding this parameter is NP-hard. In addition, the particular case of lexicographic product graphs is discussed.
قيم البحث
اقرأ أيضاً
A linear system is a pair $(P,mathcal{L})$ where $mathcal{L}$ is a family of subsets on a ground finite set $P$, such that $|lcap l^prime|leq 1$, for every $l,l^prime in mathcal{L}$. The elements of $P$ and $mathcal{L}$ are called points and lines, r
espectively, and the linear system is called intersecting if any pair of lines intersect in exactly one point. A subset $T$ of points of $P$ is a transversal of $(P,mathcal{L})$ if $T$ intersects any line, and the transversal number, $tau(P,mathcal{L})$, is the minimum order of a transversal. On the other hand, a 2-packing set of a linear system $(P,mathcal{L})$ is a set $R$ of lines, such that any three of them have a common point, then the 2-packing number of $(P,mathcal{L})$, $ u_2(P,mathcal{L})$, is the size of a maximum 2-packing set. It is known that the transversal number $tau(P,mathcal{L})$ is bounded above by a quadratic function of $ u_2(P,mathcal{L})$. An open problem is to haracterize the families of linear systems which satisfies $tau(P,mathcal{L})leq lambda u_2(P,mathcal{L})$, for some $lambdageq1$. In this paper, we give an infinite family of linear systems $(P,mathcal{L})$ which satisfies $tau(P,mathcal{L})= u_2(P,mathcal{L})$ with smallest possible cardinality of $mathcal{L}$, as well as some properties of $r$-uniform intersecting linear systems $(P,mathcal{L})$, such that $tau(P,mathcal{L})= u_2(P,mathcal{L})=r$. Moreover, we state a characterization of $4$-uniform intersecting linear systems $(P,mathcal{L})$ with $tau(P,mathcal{L})= u_2(P,mathcal{L})=4$.
Let $G=(V,E)$ and $H$ be two graphs. Packing problem is to find in $G$ the largest number of independent subgraphs each of which is isomorphic to $H$. Let $Usubset{V}$. If the graph $G-U$ has no subgraph isomorphic to $H$, $U$ is a cover of $G$. Cove
ring problem is to find the smallest set $U$. The vertex-disjoint tree packing was not sufficiently discussed in literature but has its applications in data encryption and in communication networks such as multi-cast routing protocol design. In this paper, we give the kind of $(k+1)$-connected graph $G$ into which we can pack independently the subgraphs that are each isomorphic to the $(2^{k+1}-1)$-order perfect binary tree $T_k$. We prove that in $G$ the largest number of vertex-disjoint subgraphs isomorphic to $T_k$ is equal to the smallest number of vertices that cover all subgraphs isomorphic to $T_k$. Then, we propose that $T_k$ does not have the emph{ErdH{o}s-P{o}sa} property. We also prove that the $T_k$ packing problem in an arbitrary graph is NP-hard, and propose the distributed approximation algorithms.
For positive integers $ngeq kgeq t$, a collection $ mathcal{B} $ of $k$-subsets of an $n$-set $ X $ is called a $t$-packing if every $t$-subset of $ X $ appears in at most one set in $mathcal{B}$. In this paper, we give some upper and lower bounds fo
r the maximum size of $3$-packings when $n$ is sufficiently larger than $k$. In one case, the upper and lower bounds are equal, in some cases, they differ by at most an additive constant depending only on $k$ and in one case they differ by a linear bound in $ n $.
It is well-known that the Pachner graph of $n$-vertex triangulated $2$-spheres is connected, i.e., each pair of $n$-vertex triangulated $2$-spheres can be turned into each other by a sequence of edge flips for each $ngeq 4$. In this article, we study
various induced subgraphs of this graph. In particular, we prove that the subgraph of $n$-vertex flag $2$-spheres distinct from the double cone is still connected. In contrast, we show that the subgraph of $n$-vertex stacked $2$-spheres has at least as many connected components as there are trees on $lfloorfrac{n-5}{3}rfloor$ nodes with maximum node-degree at most four.
We consider the second weighted Bartholdi zeta function of a graph $G$, and present weight
سجل دخول لتتمكن من نشر تعليقات
التعليقات
جاري جلب التعليقات
سجل دخول لتتمكن من متابعة معايير البحث التي قمت باختيارها
