#### Degree Type

Dissertation

#### Date of Award

2018

#### Degree Name

Doctor of Philosophy

#### Department

Mathematics

#### Major

Applied Mathematics

#### First Advisor

Michael Young

#### Second Advisor

Leslie Hogben

#### 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]}).$

#### DOI

https://doi.org/10.31274/etd-180810-5968

#### Copyright Owner

Michael Dairyko

#### Copyright Date

2018-05

#### Language

en

#### File Format

application/pdf

#### File Size

79 pages

#### Recommended Citation

Dairyko, Michael, "On exponential domination of graphs" (2018). *Graduate Theses and Dissertations*. 16338.

https://lib.dr.iastate.edu/etd/16338