#### Title

On exponential domination of graphs

Dissertation

2018

#### Degree Name

Doctor of Philosophy

Mathematics

#### Major

Applied Mathematics

Michael Young

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

Michael Dairyko

en

application/pdf

79 pages

COinS