Exponential domination in subcubic graphs

zbMATH Open1353.05093arXiv1511.01398MaRDI QIDQ504979FDOQ504979

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)

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.

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

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

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

zbMATH Keywords

cubic graphdominationgirthsubcubic graphcageexponential domination

Mathematics Subject Classification ID

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

Cites Work

• Title not available (Why is that?)
• Some APX-completeness results for cubic graphs
• Bounds on the \(k\)-domination number of a graph
• Onk-domination and minimum degree in graphs
• Title not available (Why is that?)
• Upper bounds on the \(k\)-domination number and the \(k\)-Roman domination number
• An upper bound for thek-domination number of a graph
• Broadcasts in graphs
• Title not available (Why is that?)
• New bounds on the \(k\)-domination number and the \(k\)-tuple domination number
• A note on the k-domination number of a graph
• Distance domination and distance irredundance in graphs
• Title not available (Why is that?)
• Distance domination versus iterated domination
• A note on distance domination numbers of graphs
• Distance domination, guarding and covering of maximal outerplanar graphs
• Distance \(k\)-domination, distance \(k\)-guarding, and distance \(k\)-vertex cover of maximal outerplanar graphs
• Domination with exponential decay
• The sextet construction for cubic graphs
• Girths of bipartite sextet graphs
• Broadcasts and domination in trees
• Bounds on the connected \(k\)-domination number in graphs
• Bounds on the exponential domination number
• Optimal broadcast domination in polynomial time

Cited In (10)

• Title not available (Why is that?)
• Exponential Domination Critical and Stability in Some Graphs
• A linear programming method for exponential domination
• Hereditary equality of domination and exponential domination
• Relating domination, exponential domination, and porous exponential domination
• Exponential independence in subcubic graphs
• Porous exponential domination in Harary graphs
• Hereditary equality of domination and exponential domination in subcubic graphs
• Exponential independence
• Bounds on the exponential domination number

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)