A linear programming method for exponential domination

DOI10.1090/CONM/759/15273zbMATH Open1458.05190arXiv1801.06404OpenAlexW3111966478MaRDI QIDQ4965263FDOQ4965263

Authors:

Publication date: 26 February 2021

Published in: The Golden Anniversary Celebration of the National Association of Mathematicians (Search for Journal in Brave)

Abstract: For a graph $G,$ the set $DsubseteqV(G)$ is a porous exponential dominating set if $1lesu{m}_{dinD}left(2ight{)}^{1-dist(d,v)}$ for every $vinV(G),$ where $dist(d,v)$ denotes the length of the shortest $dv$ path. The porous exponential dominating number of $G,$ denoted $gamm{a}_e^{*}(G),$ is the minimum cardinality of a porous exponential dominating set. For any graph $G,$ a technique is derived to determine a lower bound for $gamm{a}_e^{*}(G).$ Specifically for a grid graph $H,$ linear programing is used to sharpen bound found through the lower bound technique. Lower and upper bounds are determined for the porous exponential domination number of the King Grid $mathcal{K}_n,$ the Slant Grid $mathcal{S}_n,$ and the $n$-dimensional hypercube $Q_n.$

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

Recommendations

• On exponential domination of \(C_m\times C_n\)
• Porous exponential domination in Harary graphs
• Bounds on the exponential domination number
• Relating domination, exponential domination, and porous exponential domination
• Domination with exponential decay

zbMATH Keywords

porous exponential dominating numberporous exponential dominating set

Mathematics Subject Classification ID

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

Cites Work

• Title not available (Why is that?)
• Domination with exponential decay
• Exponential domination in subcubic graphs
• Bounds on the exponential domination number
• On exponential domination of \(C_m\times C_n\)
• Hereditary equality of domination and exponential domination
• On exponential domination of some graphs
• Relating domination, exponential domination, and porous exponential domination

Cited In (2)

• Positive linear relation and application to domination problem.
• On exponential domination of \(C_m\times C_n\)

This page was built for publication: A linear programming method for exponential domination

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