×

A linear programming method for exponential domination. (English) Zbl 1458.05190

Ortega, Omayra (ed.) et al., The golden anniversary celebration of the National Association of Mathematicians. AMS special session on the mathematics of historically black colleges and universities, HBCUs in the Mid-Atlantic. MAA invited paper session on the past 50 years of African Americans in the mathematical sciences. Haynes-Granville-Browne session of presentations by recent doctoral recipients. 2019 Claytor-Wookdard lecture. NAM David Harold Blackwell lecture, Baltimore, MD, USA and Cincinnati, OH, USA, January 17, 18 and 19 and August 2, 2019. Providence, RI: American Mathematical Society (AMS). Contemp. Math. 759, 157-166 (2020).
Summary: For a graph \(G,\) the set \(D\subseteq V(G)\) is a porous exponential dominating set if \(1\leq\sum_{d\in D}2^{1-\operatorname{dist} (d,v)}\) for every \(v\in V(G),\) where \(\operatorname{dist}(d,v)\) denotes the length of the shortest \(dv\) path. The porous exponential dominating number of \(G\), denoted \(\gamma^\ast_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 \(\gamma^\ast_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\).
For the entire collection see [Zbl 1455.00030].

MSC:

05C69 Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.)
90C05 Linear programming
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[1] Anderson, Mark; Brigham, Robert C.; Carrington, Julie R.; Vitray, Richard P.; Yellen, Jay, On exponential domination of \(C_m\times C_n\), AKCE Int. J. Graphs Comb., 6, 3, 341-351 (2009) · Zbl 1209.05163
[2] Ayta\c{c}, A.; Atay, B., On exponential domination of some graphs, Nonlinear Dyn. Syst. Theory, 16, 1, 12-19 (2016) · Zbl 1342.05097
[3] Bessy, St\'{e}phane; Ochem, Pascal; Rautenbach, Dieter, Exponential domination in subcubic graphs, Electron. J. Combin., 23, 4, Paper 4.42, 17 pp. (2016) · Zbl 1353.05093 · doi:10.37236/5711
[4] Bessy, St\'{e}phane; Ochem, Pascal; Rautenbach, Dieter, Bounds on the exponential domination number, Discrete Math., 340, 3, 494-503 (2017) · Zbl 1351.05167 · doi:10.1016/j.disc.2016.08.024
[5] Chassidy Bozeman, Joshua Carlson, Michael Dairyko, Derek Young, and Michael Young. Lower bounds for the exponential domination number of \(C_m xC_n\). \arXiv{1803.01933}.
[6] Dankelmann, Peter; Day, David; Erwin, David; Mukwembi, Simon; Swart, Henda, Domination with exponential decay, Discrete Math., 309, 19, 5877-5883 (2009) · Zbl 1191.05070 · doi:10.1016/j.disc.2008.06.040
[7] Haynes, Teresa W.; Hedetniemi, Stephen T.; Slater, Peter J., Fundamentals of domination in graphs, Monographs and Textbooks in Pure and Applied Mathematics 208, xii+446 pp. (1998), Marcel Dekker, Inc., New York · Zbl 0890.05002
[8] Henning, Michael A.; J\"{a}ger, Simon; Rautenbach, Dieter, Hereditary equality of domination and exponential domination, Discuss. Math. Graph Theory, 38, 1, 275-285 (2018) · Zbl 1377.05140 · doi:10.7151/dmgt.2006
[9] Henning, Michael A.; J\"{a}ger, Simon; Rautenbach, Dieter, Relating domination, exponential domination, and porous exponential domination, Discrete Optim., 23, 81-92 (2017) · Zbl 1387.90136 · doi:10.1016/j.disopt.2016.12.002
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.