Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userOn (t,r) Broadcast Domination Numbers of Grids
159
0
0.0
(
0
)
Ask ChatGPT about the research
No Arabic abstract
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 nearly 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.
rate research
Read More
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)$ broadcast 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.
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.
Let $mathcal{H}$ be a hypergraph on a finite set $V$. A {em cover} of $mathcal{H}$ is a set of vertices that meets all edges of $mathcal{H}$. If $W$ is not a cover of $mathcal{H}$, then $W$ is said to be a {em noncover} of $mathcal{H}$. The {em noncover complex} of $mathcal{H}$ is the abstract simplicial complex whose faces are the noncovers of $mathcal{H}$. In this paper, we study homological properties of noncover complexes of hypergraphs. In particular, we obtain an upper bound on their Leray numbers. The bound is in terms of hypergraph domination numbers. Also, our proof idea is applied to compute the homotopy type of the noncover complexes of certain uniform hypergraphs, called {em tight paths} and {em tight cycles}. This extends to hypergraphs known results on graphs.
The concept of power domination emerged from the problem of monitoring electrical systems. Given a graph G and a set S $subseteq$ V (G), a set M of monitored vertices is built as follows: at first, M contains only the vertices of S and their direct neighbors, and then each time a vertex in M has exactly one neighbor not in M, this neighbor is added to M. The power domination number of a graph G is the minimum size of a set S such that this process ends up with the set M containing every vertex of G. We here show that the power domination number of a triangular grid T_k with hexagonal-shape border of length k -- 1 is exactly $lceil k/3 rceil.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
