اشترك بالحزمة الذهبية واحصل على وصول غير محدود شمرا أكاديميا
تسجيل مستخدم جديدUpper broadcast domination of toroidal grids and a classification of diametrical trees
69
0
0.0
(
0
)
اسأل ChatGPT حول البحث
ﻻ يوجد ملخص باللغة العربية
A broadcast on a graph $G=(V,E)$ is a function $f:V rightarrow {0,1, ldots, text{diam}(G)}$ satisfying $f(v) leq e(v)$ for all $v in V$, where $e(v)$ denotes the eccentricity of $v$ and $text{diam}(G)$ denotes the diameter of $G$. We say that a broadcast dominates $G$ if every vertex can hear at least one broadcasting node. The upper domination number is the maximum cost of all possible minimal broadcasts, where the cost of a broadcast is defined as $text{cost} (f)= sum_{v in V}f(v)$. In this paper we establish both the upper domination number and the upper broadcast domination number on toroidal grids. In addition, we classify all diametrical trees, that is, trees whose upper domination number is equal to its diameter.
قيم البحث
اقرأ أيضاً
The domination number of a graph $G = (V,E)$ is the minimum cardinality of any subset $S subset V$ such that every vertex in $V$ is in $S$ or adjacent to an element of $S$. Finding the domination numbers of $m$ by $n$ grids was an open problem for ne
arly 30 years and was finally solved in 2011 by Goncalves, Pinlou, Rao, and Thomasse. Many variants of domination number on graphs have been defined and studied, but exact values have not yet been obtained for grids. We will define a family of domination theories parameterized by pairs of positive integers $(t,r)$ where $1 leq r leq t$ which generalize domination and distance domination theories for graphs. We call these domination numbers the $(t,r)$ broadcast domination numbers. We give the exact values of $(t,r)$ broadcast domination numbers for small grids, and we identify upper bounds for the $(t,r)$ broadcast domination numbers for large grids and conjecture that these bounds are tight for sufficiently large grids.
A dominating set of a graph $G$ is a set of vertices that contains at least one endpoint of every edge on the graph. The domination number of $G$ is the order of a minimum dominating set of $G$. The $(t,r)$ broadcast domination is a generalization of
domination in which a set of broadcasting vertices emits signals of strength $t$ that decrease by 1 as they traverse each edge, and we require that every vertex in the graph receives a cumulative signal of at least $r$ from its set of broadcasting neighbors. In this paper, we extend the study of $(t,r)$ broadcast domination to directed graphs. Our main result explores the interval of values obtained by considering the directed $(t,r)$ broadcast domination numbers of all orientations of a graph $G$. In particular, we prove that in the cases $r=1$ and $(t,r) = (2,2)$, for every integer value in this interval, there exists an orientation $vec{G}$ of $G$ which has directed $(t,r)$ broadcast domination number equal to that value. We also investigate directed $(t,r)$ broadcast domination on the finite grid graph, the star graph, the infinite grid graph, and the infinite triangular lattice graph. We conclude with some directions for future study.
Let $G=( V(G), E(G) )$ be a connected graph with vertex set $V(G)$ and edge set $E(G)$. We say a subset $D$ of $V(G)$ dominates $G$ if every vertex in $V setminus D$ is adjacent to a vertex in $D$. A generalization of this concept is $(t,r)$ broadcas
t domination. We designate certain vertices to be towers of signal strength $t$, which send out signal to neighboring vertices with signal strength decaying linearly as the signal traverses the edges of the graph. We let $mathbb{T}$ be the set of all towers, and we define the signal received by a vertex $vin V(G)$ from a tower $w in mathbb T$ to be $f(v)=sum_{win mathbb{T}}max(0,t-d(v,w))$. Blessing, Insko, Johnson, Mauretour (2014) defined a $(t,r)$ broadcast dominating set, or a $(t,r) $ broadcast, on $G$ as a set $mathbb{T} subseteq V(G) $ such that $f(v)geq r$ for all $vin V(G)$. The minimal cardinality of a $(t, r)$ broadcast on $G$ is called the $(t, r)$ broadcast domination number of $G$. In this paper, we present our research on the $(t,r)$ broadcast domination number for certain graphs including paths, grid graphs, the slant lattice, and the kings lattice.
Let $ G $ be a graph. A subset $S subseteq V(G) $ is called a total dominating set if every vertex of $G$ is adjacent to at least one vertex of $S$. The total domination number, $gamma_{t}$($G$), is the minimum cardinality of a total dominating set o
f $G$. In this paper using a greedy algorithm we provide an upper bound for $gamma_{t}$($G$), whenever $G$ is a bipartite graph and $delta(G)$ $geq$ $k$. More precisely, we show that if $k$ > 1 is a natural number, then for every bipartite graph $G$ of order $n$ and $delta(G) ge k$, $ $$gamma_{t}$($G$) $leq$ $n(1- frac{k!}{prod_{i=0}^{k-1}(frac{k}{k-1}+i)}).$
A set $D$ of vertices of a graph $G$ is a total dominating set if every vertex of $G$ is adjacent to at least one vertex of $D$. The total domination number of $G$ is the minimum cardinality of any total dominating set of $G$ and is denoted by $gamma
_t(G)$. The total dominating set $D$ is called a total co-independent dominating set if $V(G)setminus D$ is an independent set and has at least one vertex. The minimum cardinality of any total co-independent dominating set is denoted by $gamma_{t,coi}(G)$. In this paper, we show that, for any tree $T$ of order $n$ and diameter at least three, $n-beta(T)leq gamma_{t,coi}(T)leq n-|L(T)|$ where $beta(T)$ is the maximum cardinality of any independent set and $L(T)$ is the set of leaves of $T$. We also characterize the families of trees attaining the extremal bounds above and show that the differences between the value of $gamma_{t,coi}(T)$ and these bounds can be arbitrarily large for some classes of trees.
سجل دخول لتتمكن من نشر تعليقات
التعليقات
جاري جلب التعليقات
سجل دخول لتتمكن من متابعة معايير البحث التي قمت باختيارها
