On Domination and Bondage Numbers of Some Classes of Graphs

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) \u3e ?(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