Electronic Theses and Dissertations

Date of Award


Document Type


Degree Name

Ph.D. in Mathematics

First Advisor

Bing Wei

Second Advisor

Talmage Reid

Third Advisor

Qingying Bu

Relational Format



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.

Available for download on Wednesday, December 14, 2022

Included in

Mathematics Commons