On exponential domination of graphs

Thumbnail Image
Date
2018-01-01
Authors
Dairyko, Michael
Major Professor
Advisor
Michael Young
Leslie Hogben
Committee Member
Journal Title
Journal ISSN
Volume Title
Publisher
Altmetrics
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]}).$

Series Number
Journal Issue
Is Version Of
Versions
Series
Academic or Administrative Unit
Type
dissertation
Comments
Rights Statement
Copyright
Tue May 01 00:00:00 UTC 2018
Funding
Subject Categories
Supplemental Resources
Source