Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userOn $(t,r)$ broadcast domination of directed graphs
59
0
0.0
(
0
)
Ask ChatGPT about the research
No Arabic abstract
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.
rate research
Read More
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.
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.
Given a graph $G$, a dominating set of $G$ is a set $S$ of vertices such that each vertex not in $S$ has a neighbor in $S$. The domination number of $G$, denoted $gamma(G)$, is the minimum size of a dominating set of $G$. The independent domination number of $G$, denoted $i(G)$, is the minimum size of a dominating set of $G$ that is also independent. Note that every graph has an independent dominating set, as a maximal independent set is equivalent to an independent dominating set. Let $G$ be a connected $k$-regular graph that is not $K_{k, k}$ where $kgeq 4$. Generalizing a result by Lam, Shiu, and Sun, we prove that $i(G)le frac{k-1}{2k-1}|V(G)|$, which is tight for $k = 4$. This answers a question by Goddard et al. in the affirmative. We also show that $frac{i(G)}{gamma(G)} le frac{k^3-3k^2+2}{2k^2-6k+2}$, strengthening upon a result of Knor, v{S}krekovski, and Tepeh. In addition, we prove that a graph $G$ with maximum degree at most $4$ satisfies $i(G) le frac{5}{9}|V(G)|$, which is also tight.
In this paper, we study the domination number of middle graphs. Indeed, we obtain tight bounds for this number in terms of the order of the graph. We also compute the domination number of some families of graphs such as star graphs, double start graphs, path graphs, cycle graphs, wheel graphs, complete graphs, complete bipartite graphs and friendship graphs, explicitly. Moreover, some Nordhaus-Gaddum-like relations are presented for the domination number of middle graphs.
In combinatorics, a latin square is a $ntimes n$ matrix filled with n different symbols, each occurring exactly once in each row and exactly once in each column. Associated to each latin square, we can define a simple graph called a latin square graph. In this article, we compute lower and upper bounds for the domination number and the k-tuple total domination numbers of such graphs. Moreover, we describe a formula for the 2-tuple total domination number.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
