Background
A graph G = (V, E) is an ordered pair of objects where V denotes a set of vertices of G, and E represents the set of edges or lines connecting the vertices. Figure 1 is an example of a graph containing five vertices and six edges. Graphs can contain any number of vertices connected by edges. Graph theory is the study of these graphs and their ability to model real-world relationships. Figure 1: An example of a simple, undirected graph with five vertices and six edges.
Graphs, their properties, and the algorithms to traverse them have been widely analyzed and used to mathematically represent relationships. For example, one of the most common implementations of graph theory is in Global Positioning System (GPS) navigation devices to find the shortest path to any given destination. However, graphs can be applied in many more ways to model the way in which things interact in the real-world and in almost every field of science including physics, chemistry, biology, sociology, and linguistics. For example, in the field of biology and medicine, graphs can be used to map the progression of neuro-degenerative diseases like dementia and Alzheimer’s in the brain [1]. Likewise, they are frequently used in computer science for data organization and modeling networks. More recently, graph coloring, an area of study within graph theory, has been researched as a way to model communities within those networks [6]. In 1852, Francis Guthrie proposed the four color conjecture observing that the counties in England can be colored with only four different colors so that no regions sharing a border are colored with the same color [5]. Within graph theory, the theorem states that only four colors are necessary to color the vertices of a simple graph with no adjacent vertices of the same color. This laid the framework for graph coloring and later, domination. Domination is related to the study of colored sets in graph theory. Figure 2 is an example of a domination problem showing an 8 x 8 chessboard where the five queens are connected to every square on the board, dominating every square that is not a queen. The chessboard can be represented as a graph with each square as a vertex with edges connecting every adjacent square. This paper further explores other graph invariants, a mathematical property that holds true to all objects, related to domination. Figure 2: The paths of the five queens shows domination over every square. This means that every square is connected to at least one“ queen.
Partitioning a graph is the process of separating vertices into different sets. By assigning colors to vertices or grouping them into different sets, the graph is partitioned. Essentially, when coloring, the vertices of the graph are being separated into different groups, and the graph is being divided into smaller parts. Sets make up the partition. Partitions of graphs are the basis to the theory of domination. A set of vertices in a graph is a dominating set if the collective vertices of that set are adjacent to every vertex of not in that set. As it pertains to coloring, a set is dominating if every vertex not in the set or of a different color is dominated by the set. In Figure 3a, the set of black vertices dominates the set of gray vertices because collectively, the black vertices are connected to every gray vertex. Likewise, the set of black vertices dominate the white vertices because they are connected to every white vertex in the graph. However, if the black vertex in the center were recolored as a gray vertex, the set would no longer dominate as shown in Figure 3b.
(a) Representation of a graph with three dominating sets where V1 is the black set, V2 is the white set, and V3 is the gray set (b) The black set does not dominate the graph because the set is not connected to two white vertices and one gray vertex. Figure 3: Graphs showing both dominating and non-dominating sets. Domatic Number A domatic partition is one in which every set of vertices in a graph is dominating. Cockayne and Hedetniemi defined the domatic number d(G) is the size of the largest domatic partition [4]. In terms of coloring, this means that every vertex is adjacent to vertices of all othercolors. Therefore, Figure 3a has a domatic number of 3 or d(G) = 3 and is a domatic partition. R dominates S is denoted as R → S. Transitivity Transitivity is the idea that if a is equal to b and b is equal to c, then a must also be equal toc. The transitivity number of a graph, an extension of the domatic number, is defined as the maximum number of sets where each set dominates all successive ones [3].The transitivity number is always greater than or equal to the domatic number. In the vertex partitionπ = {V1, V2, ..., Vk}, where 1 ≤ i ≤ k, every Vi must dominate every successive set Vk to be transitive. In the case of Figure 3a, the black set dominates the white and gray sets, the white set dominates the gray set, and the gray set is the remaining set. Thus, the transitivity number of the graph, denoted by Tr(G), is three. The transitivity differs from the domatic number because each set must dominate all successive ones. This means that, for example, in a graph with four partitions, the first set must dominate the second, third, and fourth sets. The second set must dominate the third and fourth sets, and the third set must dominate the fourth set. Grundy Coloring A set is an independent set if no two of its vertices are adjacent. Christen and Selkow (1979) defined the Grundy coloring and Grundy number, denoted as Γr(G), such that each set in the partition dominates all successive ones and each set is independent. [2] The graph in Figure 3a is not a Grundy coloring because one of the three sets is not independent. The figure shows two adjacent black vertices; therefore, the set is not independent and the graph is not a Grundy coloring. Figure 4 is the correct Grundy coloring. Figure 4: V1 is the black set, V2 is the white set, and V3 is the gray set. The graph is a Grundy coloring because each set of vertices is independent, and V1 dominates V2 and V3, and V2 dominates V3.
|