In this paper we consider the domination number and bondage number of graph G. The domination number is defined as a minimum size of a dominating subset of vertices such that every other vertex not in it must be adjacent to some vertex in this subset. The bondage number is defined as the minimum number of edges whose removal results in a new graph with larger domination number. These parameters measure to some extent the robustness of an interconnection network with respect to link failures. By constructing a family of minimum dominating sets we compute the domination number and bondage number of the lollipop graph.
展开▼
