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 dominat...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 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 γ f(G) and γ~t f(G) be the fractional domination number and fractional total domination number of a graph G respectively. Hare and Stewart gave some exact fractional domination number of P n...Let γ f(G) and γ~t f(G) be the fractional domination number and fractional total domination number of a graph G respectively. Hare and Stewart gave some exact fractional domination number of P n×P m (grid graph) with small n and m . But for large n and m , it is difficult to decide the exact fractional domination number. Motivated by this, nearly sharp upper and lower bounds are given to the fractional domination number of grid graphs. Furthermore, upper and lower bounds on the fractional total domination number of strong direct product of graphs are given.展开更多
Let <em>G</em>(<em>V</em>, <em>E</em>) be a finite connected simple graph with vertex set <em>V</em>(<em>G</em>). A function is a signed dominating function ...Let <em>G</em>(<em>V</em>, <em>E</em>) be a finite connected simple graph with vertex set <em>V</em>(<em>G</em>). A function is a signed dominating function <em>f </em>: <em style="white-space:normal;">V</em><span style="white-space:normal;">(</span><em style="white-space:normal;">G</em><span style="white-space:normal;">)</span><span style="white-space:nowrap;">→{<span style="white-space:nowrap;"><span style="white-space:nowrap;">−</span></span>1,1}</span> if for every vertex <em>v</em> <span style="white-space:nowrap;">∈</span> <em>V</em>(<em>G</em>), the sum of closed neighborhood weights of <em>v</em> is greater or equal to 1. The signed domination number <em>γ</em><sub>s</sub>(<em>G</em>) of <em>G</em> is the minimum weight of a signed dominating function on <em>G</em>. In this paper, we calculate the signed domination numbers of the Cartesian product of two paths <em>P</em><sub><em>m</em></sub> and <em>P</em><sub><em>n</em></sub> for <em>m</em> = 6, 7 and arbitrary <em>n</em>.展开更多
文摘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 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 γ f(G) and γ~t f(G) be the fractional domination number and fractional total domination number of a graph G respectively. Hare and Stewart gave some exact fractional domination number of P n×P m (grid graph) with small n and m . But for large n and m , it is difficult to decide the exact fractional domination number. Motivated by this, nearly sharp upper and lower bounds are given to the fractional domination number of grid graphs. Furthermore, upper and lower bounds on the fractional total domination number of strong direct product of graphs are given.
文摘Let <em>G</em>(<em>V</em>, <em>E</em>) be a finite connected simple graph with vertex set <em>V</em>(<em>G</em>). A function is a signed dominating function <em>f </em>: <em style="white-space:normal;">V</em><span style="white-space:normal;">(</span><em style="white-space:normal;">G</em><span style="white-space:normal;">)</span><span style="white-space:nowrap;">→{<span style="white-space:nowrap;"><span style="white-space:nowrap;">−</span></span>1,1}</span> if for every vertex <em>v</em> <span style="white-space:nowrap;">∈</span> <em>V</em>(<em>G</em>), the sum of closed neighborhood weights of <em>v</em> is greater or equal to 1. The signed domination number <em>γ</em><sub>s</sub>(<em>G</em>) of <em>G</em> is the minimum weight of a signed dominating function on <em>G</em>. In this paper, we calculate the signed domination numbers of the Cartesian product of two paths <em>P</em><sub><em>m</em></sub> and <em>P</em><sub><em>n</em></sub> for <em>m</em> = 6, 7 and arbitrary <em>n</em>.
