Date of Award
1-1-2021
Document Type
Dissertation
Degree Name
Ph.D. in Mathematics
First Advisor
Bing Wei
Second Advisor
Talmage Reid
Third Advisor
Qingying Bu
Relational Format
dissertation/thesis
Abstract
Given a simple finite graph G=(V,E), a vertex subset D ? V(G) is said to be a dominating set of G if every vertex v ? V(G)-D is adjacent to a vertex in D. The domination number of G, denoted ?(G), is the minimum cardinality among all dominating sets of G. In a network, the domination number determines the minimum number of sites required to dominate the entire network at a minimum cost. The bondage number of a graph G is the minimum cardinality among all edge sets B such that ?(G-B) > ?(G). The bondage number may serve as a parameter to measure the vulnerability of a graph or network under in the case of an edge failure. In particular, we study domination and bondage numbers for k-trees. A k-tree G is a graph with n ? k+1 vertices formed by taking the complete graph K_{k+1} and repeatedly adding vertices such that each added vertex v has k neighbors and N[v] forms a clique. In this dissertation, we study upper bounds on the domination number of k-trees for 1 ? k ? 3.
Recommended Citation
Pham, Andrew, "On Domination and Bondage Numbers of Some Classes of Graphs" (2021). Electronic Theses and Dissertations. 2125.
https://egrove.olemiss.edu/etd/2125