##
On exponential domination of graphs

##### Date

##### Authors

##### Major Professor

##### Advisor

##### Committee Member

##### Journal Title

##### Journal ISSN

##### Volume Title

##### Publisher

##### Altmetrics

##### Authors

##### Research Projects

##### Organizational Units

##### Journal Issue

##### Is Version Of

##### Versions

##### Series

##### Department

##### Abstract

Exponential domination in graphs evaluates the influence that a particular vertex exerts on the remaining vertices within a graph. The amount of influence a vertex exerts is measured through an exponential decay formula with a growth factor of one-half. An exponential dominating set consists of vertices who have significant influence on other vertices. In non-porous exponential domination, vertices in an exponential domination set block the influence of each other. Whereas in porous exponential domination, the influence of exponential dominating vertices are not blocked. For a graph $G,$ the non-porous and porous exponential domination numbers, denoted $\gamma_e(G)$ and $\gamma_e^*(G),$ are defined to be the cardinality of the minimum non-porous exponential dominating set and cardinality of the minimum porous exponential dominating set, respectively. This dissertation focuses on determining lower and upper bounds of the non-porous and porous exponential domination number of the King grid $\mathcal{K}_n,$ Slant grid $\mathcal{S}_n,$ $n$-dimensional hypercube $Q_n,$ and the general consecutive circulant graph $C_{n,[\ell]}.$

A method to determine the lower bound of the non-porous exponential domination number for any graph is derived. In particular, a lower bound for $\gamma_e^*(Q_n)$ is found. An upper bound for $\gamma_e^*(Q_n)$ is established through exploiting distance properties of $Q_n.$ For any grid graph $G,$ linear programming can be incorporated with the lower bound method to determine a general lower bound for $\gamma_e^*(G).$ Applying this technique to the grid graphs $\mathcal{K}_n$ and $\mathcal{S}_n$ yields lower bounds for $\gamma_e^*(\mathcal{K}_n)$ and $\gamma_e^*(\mathcal{S}_n).$ Upper bound constructions for $\gamma_e^*(\mathcal{K}_n)$ and $\gamma_e^*(\mathcal{S}_n)$ are also derived. Finally, it is shown that $\gamma_e(C_{n,[\ell]}) = \gamma_e^*(C_{n,[\ell]}).$