No description available.

A set S = {u1, u2,..., ut} of vertices of G is an efficient dominating set if every vertex of G is dominated exactly once by the vertices of S. Letting Ui denote the set of vertices dominated by ui, we note that {U1, U2,... Ut} is a partition of the vertex set of G and that each Ui contains the vertex ui and all the vertices at distance 1 from it in G. In this paper, we generalize the concept of efficient domination by considering k-efficient domination partitions of the vertex set of G, where each element of the partition is a set consisting of a vertex ui and all the vertices at distance di from it, where di ∈ {0, 1,..., k}. For any integer k ≥ 0, the k-efficient domination number of G equals the minimum order of a k-efficient partition of G. We determine bounds on the k-efficient domination number for general graphs, and for k ∈ {1, 2}, we give exact values for some graph families. Complexity results are also obtained.

We determine upper bounds on the ratios of several domination parameters in trees.

In this thesis, we will study several domination parameters of a family of graphs known as complementary prisms. We will first present the basic terminology and definitions necessary to understand the topic. Then, we will examine the known results addressing the domination number and the total domination number of complementary prisms. After this, we will present our main results, namely, results on the restrained domination number of complementary prisms. Subsequently results on the distance - k domination number, 2-step domination number and stratification of complementary prisms will be presented. Then, we will characterize when a complementary prism is Eulerian or bipartite, and we will obtain bounds on the chromatic number of a complementary prism. We will finish the thesis with a section on possible future problems.