An introduction to integrated domination using K1’s and K2’s

Abstract

In Mathematics, graph theory is the study of graphs, which consist of a set of points, called vertices, and the connections between them, called edges. Domination is a subfield of this study, which looks at subsets of vertices in a graph that are adjacent to every other vertex in the graph. These subsets are called dominating sets. A vertex u is said to dominate a vertex v, if u is adjacent to v. The principal problem of domination is to find the smallest dominating set for a graph. Variations of domination exist, with the two standard types using K1’s (single vertices), or K2’s (paired vertices) as guards. To the best of our knowledge, we introduce the idea of integrating two different types of guards in one dominating set. Here, we look at the idea of dominating a graph using a combination of guards in the forms of K1’s and K2’s, and the problem of finding a minimum dominating set for this style of domination, which we call integrated domination. We look at a number of well-known variations of domination, and then characterize graphs and subgraphs where a minimum integrated dominating set can efficiently be found. As well, we present a bound for this style of domination, and then discuss further directions for this problem.