Efficient Domination in Cartesian product of Graphs and its Critical Aspects

Abstract

In a graph G = (V;E), every vertex v 2 V (G) dominates itself and its neighbors. A set S V (G) is a dominating set of G if each vertex in V (G) is either in S or has a neighbor in S. The domination number of G, denoted by (G), is the cardinality of a minimum dominating set of G. It is noted that if S is a dominating set, then the vertices in V 􀀀 S may have more than one neighbor in S. Imposing the additional constraint on a dominating set S that, each vertex in V must have exactly one neighbor in S (inclusive of vertices in S), leads to the notion of efficient domination in graphs. A dominating set S V (G) is an efficient dominating set (EDS) of G, if each vertex in V (G) is either in S or has exactly one neighbor in S. A graph G is efficiently dominatable, if it has an EDS. If S is an EDS of G, then S is also a minimum dominating set of G, but not conversely. Thus, all efficient dominating sets have the same cardinality, namely, (G). Though an EDS of G has the same cardinality as its domination number, it is noted that for a given domination number, the properties of a graph which does not contain an EDS need not be true for an efficiently dominatable graph. This necessitates an exclusive study of the class of efficiently dominatable graphs. Though there is a significant amount of study in the literature related to efficient domination, both from graph theoretical as well as algorithmic perspective, to the best of our knowledge, it has not been much explored relative to the other domination parameters. Further, the concept of efficient domination also finds applications in diverse fields like coding theory, parallel computing, wireless ad hoc networks, etc. Motivated by the applications of efficient domination and the research gap identified in the literature, interest is shown in this thesis to study the concept of efficient domination for an arbitrary graph and for a particular type of graph product, namely cartesian product. The contributions to this thesis are organized into three chapters, namely Chapter 3, 4 and 5. Chapter 3 deals with the study on Efficient domination in general/arbitrary graphs. Some basic results on efficient domination in general graphs including some improved bounds on domination number, efficient domination in trees and some special classes of graphs are discussed. Further, the structural properties of graphs possessing pairwise disjoint efficient dominating sets are studied along with an insight into the applications of such structures in ad hoc and sensor networks. i Chapter 4 focuses on the concept of criticality in the class of efficiently dominatable graphs, where the concept of criticality in general, deals with the study of the behaviour of a graph with respect to a graph parameter, upon the removal of a vertex or a set of vertices, removal or addition of one or more edges. The study in this chapter is restricted to the removal of a single vertex and removal or addition of a single edge, at a time. Based on the research gap identified in the literature, fascinated by the applications of the concept of criticality in the design of fault-tolerant networks and its significance in graph theory, the study is initiated with respect to efficient domination. A vertex whose removal from G alters (G) is referred to as a critical vertex. Similarly, an edge, whose removal from G or whose addition between a pair of non-adjacent vertices in G alters (G) is a critical edge. The collection of such vertices (or edges) is a vertex (or edge) critical set. In this chapter, an attempt is made to explore the properties of critical vertices, critical edges with respect to both removal and addition. The vertex critical sets, edge critical sets and six classes of graphs arising thereof are characterized. Finally, the relationship between all these classes is identified and discussed. Finally, Chapter 5 deals with the study of efficient domination in the cartesian product of graphs. Here, the structural properties of the product in terms of its factors are discussed. The initial focus is on the product of two well-known graphs, followed by the product of an arbitrary graph G with a well-known graph. Further, the class of efficiently dominatable product graphs G K1; p and G Kp, for some positive integer p and an arbitrary graph G are characterized. The problem of deciding whether or not a graph is efficiently dominatable is NP-complete and so also, for the the products mentioned above. So, an attempt is made to design exact exponential time algorithms, to determine whether the products are efficiently dominatable or not. The study is also extended to Hamming graphs.