Exponential domination in subcubic graphs

MaRDI QIDQ504979zbMATH OpenFDO

Authors Stéphane Bessy, Pascal Ochem, Dieter Rautenbach

Publication date 18 January 2017

Published in The Electronic Journal of Combinatorics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1511.01398, http://www.combinatorics.org/ojs/index.php/eljc/article/view/v23i4p42

IPFS File on IPFS (Hint: this is only the Hash - if you get a timeout, this file is not available on our server.)

zbMATH Keywords

cubic graphdominationgirthsubcubic graphcageexponential 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$. In the present paper we study exponential domination in subcubic graphs. Our results are as follows: If $G$ is a connected subcubic graph of order $n(G)$, then ${\displaystyle }$frac{n(G)}{6log_2(n(G)+2)+4}leq gamma_e(G)leq frac{1}{3}(n(G)+2).${\displaystyle }$ For every $epsilon>0$, there is some $g$ such that $gamm{a}_e(G)leqepsilonn(G)$ for every cubic graph $G$ of girth at least $g$. For every $0<alpha<frac23ln(2)$, there are infinitely many cubic graphs $G$ with $gamm{a}_e(G)leqfrac3n(G)ln(n(G){)}^{alpha}$. If $T$ is a subcubic tree, then $gamm{a}_e(T)geqfrac16(n(T)+2).$ For a given subcubic tree, $gamm{a}_e(T)$ can be determined in polynomial time. The minimum exponential dominating set problem is APX-hard for subcubic graphs.

Recommendations

• Bounds on the exponential domination number
• Relating domination, exponential domination, and porous exponential domination
• Domination with exponential decay
• On exponential domination of some graphs
• Exponential independence in subcubic graphs

Cites work

• 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?)
• 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
• Bounds on the exponential domination number
• 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
• Girths of bipartite sextet graphs
• 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
• Some APX-completeness results for cubic graphs
• The sextet construction for cubic graphs
• Upper bounds on the \(k\)-domination number and the \(k\)-Roman domination number

Cited in

(10)

• Exponential Domination Critical and Stability in Some Graphs
• Hereditary equality of domination and exponential domination in subcubic graphs
• Exponential independence in subcubic graphs
• Bounds on the exponential domination number
• A linear programming method for exponential domination
• Exponential independence
• Porous exponential domination in Harary graphs
• scientific article; zbMATH DE number 6761041 (Why is no real title available?)
• Relating domination, exponential domination, and porous exponential domination
• Hereditary equality of domination and exponential domination

This page was built for publication: Exponential domination in subcubic graphs

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