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
Authors
Research Projects
Organizational Units
Organizational Unit
Journal Issue
Is Version Of
Versions
Series
Department
Mathematics
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]}).$

Comments
Description
Keywords
Citation
Source
Subject Categories
Copyright
Tue May 01 00:00:00 UTC 2018