Bounds on the exponential domination number

DOI10.1016/J.DISC.2016.08.024MaRDI QIDQ729783zbMATH OpenOpenAlexWikidataFDO

Authors Stéphane Bessy, Pascal Ochem, Dieter Rautenbach

Publication date 22 December 2016

Published in Discrete Mathematics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1510.08749

zbMATH Keywords

dominationexponential domination

Mathematics Subject Classification ID

Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)

Abstract: As a natural variant of domination in graphs, Dankelmann et al. [Domination with exponential decay, Discrete Math. 309 (2009) 5877-5883] introduce exponential domination, where vertices are considered to have some dominating power that decreases exponentially with the distance, and the dominated vertices have to accumulate a sufficient amount of this power emanating from the dominating vertices. More precisely, if $S$ is a set of vertices of a graph $G$, then $S$ is an exponential dominating set of $G$ if $sumlimit{s}_{vinS}left(frac12ight{)}^{{mdist}_{(G,S)}(u,v)-1}geq1$ for every vertex $u$ in $V(G)setminusS$, where ${mdist}_{(G,S)}(u,v)$ is the distance between $uinV(G)setminusS$ and $vinS$ in the graph $G-(Ssetminusv)$. The exponential domination number $gamm{a}_e(G)$ of $G$ is the minimum order of an exponential dominating set of $G$. Dankelmann et al. show ${\displaystyle }$frac{1}{4}({ m d}+2)leq gamma_e(G)leq frac{2}{5}(n+2)${\displaystyle }$ for a connected graph $G$ of order $n$ and diameter $md$. We provide further bounds and in particular strengthen their upper bound. Specifically, for a connected graph $G$ of order $n$, maximum degree $Delta$ at least $3$, radius $mr$ at least $1$, we show �egin{eqnarray*} gamma_e(G) & geq & left(frac{n}{13(Delta-1)^2} ight)^{frac{log_2(Delta-1)+1}{log_2^2(Delta-1)+log_2(Delta-1)+1}},\[3mm] gamma_e(G) & leq & 2^{2{ m r}-2}mbox{, and }\[3mm] gamma_e(G) & leq & frac{43}{108}(n+2). end{eqnarray*}

Recommendations

• Domination with exponential decay
• On exponential domination of some graphs
• Exponential domination in subcubic graphs
• On exponential domination of \(C_m\times C_n\)
• Exponential Domination Critical and Stability in Some Graphs

Cites work

• A note on distance domination numbers of graphs
• A note on the k-domination number of a graph
• An upper bound for thek-domination number of a graph
• Bounds on the k-domination number of a graph
• Bounds on the connected \(k\)-domination number in graphs
• Broadcasts and domination in trees
• Broadcasts in graphs
• Distance \(k\)-domination, distance \(k\)-guarding, and distance \(k\)-vertex cover of maximal outerplanar graphs
• Distance domination and distance irredundance in graphs
• Distance domination versus iterated domination
• Distance domination, guarding and covering of maximal outerplanar graphs
• Domination with exponential decay
• scientific article; zbMATH DE number 3914370 (Why is no real title available?)
• scientific article; zbMATH DE number 1095171 (Why is no real title available?)
• scientific article; zbMATH DE number 1124605 (Why is no real title available?)
• scientific article; zbMATH DE number 2109329 (Why is no real title available?)
• New bounds on the \(k\)-domination number and the \(k\)-tuple domination number
• Onk-domination and minimum degree in graphs
• Optimal broadcast domination in polynomial time
• Upper bounds on the \(k\)-domination number and the \(k\)-Roman domination number

Cited in

(19)

• Domination with exponential decay
• Hereditary equality of domination and exponential domination
• Relating domination, exponential domination, and porous exponential domination
• A simple proof for the exponential upper bound for some tenacious patterns
• Exponential independence in subcubic graphs
• A vulnerability parameter of networks
• Stability and domination exponentially in some graphs
• Porous exponential domination in Harary graphs
• Domination with decay in triangular matchstick arrangement graphs
• On exponential domination of some graphs
• Bounds on the Global Domination Number
• On exponential domination and graph operations
• A linear programming method for exponential domination
• scientific article; zbMATH DE number 6761041 (Why is no real title available?)
• Exponential domination in subcubic graphs
• On exponential edge domination number of a graph
• On exponential domination of \(C_m\times C_n\)
• A variation of distance domination in composite networks
• An exponential-type upper bound for Folkman numbers

This page was built for publication: Bounds on the exponential domination number

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q729783)