For a graph \(G\) with a (not necessarily proper) vertex coloring, a set \(D\subseteq V(G)\) is a polychromatic dominating set of \(G\) if it is a dominating set and each vertex in \(D\) is a different color. The polychromatic domination number of \(G\), \(\rho(G)\), is the minimum number of colors such that, for any \(\rho(G)\)-coloring (with exactly \(\rho(G)\) colors) of the vertices of \(G\), there exists a polychromatic dominating set of \(G\). This paper begins the exploration of the polychromatic domination number. In particular we give tight upper and lower bounds for \(\rho(G)\) both of which are functions of the minimum degree of \(G\).
In this paper, we introduce a parameter, the polychromatic domination number of a graph, with a flavor similar to some classic graph parameters. For instance, a classic Ramsey Theory question is to find the minimum \(n\) such that every \(k\)-coloring of \(K_n\) contains a monochromatic \(K_p\). The opposite problem is to find the number of colors needed to be sure that a polychromatic \(K_p\) must exist in a \(k\)-coloring of \(K_n\). The anti-Ramsey number AR\((n, G)\) is the maximum number of colors \(k\) so that there is a \(k\)-edge coloring of \(K_n\) with no polychromatic edge-coloring of \(G\). The Turan number for a graph \(G\) is the maximum number of edges an \(n\)-vertex graph can have and not contain \(G\). The field of extremal graph theory is full of variations of these problems, see for example [1, 2, 5, 9, 10], and we add to this research.
A set \(S \subseteq V(G)\) is a dominating set for a graph \(G\) if, for all \(v \in V(G)\), \(v \in N_G[S]\) where \(N_G[S] = \cup_{w \in S}N[w]\). The domination number of a graph \(G\) will be denoted \(\gamma(G)\). We define a dominating set \(D\) of a \(k\)-colored graph to be polychromatic if every vertex of \(D\) is a different color. The polychromatic domination number of \(G\), denoted \(\rho(G)\), is the minimum number of colors such that, for any \(\rho(G)\)-coloring of the vertices of \(G\) (with exactly \(\rho(G)\) colors), there exists a polychromatic dominating set of \(G\).
Note that in the anti-Ramsey literature, what we call a polychromatic set is called a rainbow set or sometimes an achromatic set. There are numerous papers in the graph theory literature that define various rainbow parameters. See, for example, [3, 4, 6, 7, 8, 11, 13, 15]. While we considered this language for our parameter in the spirit of these other works, we decided on the polychromatic terminology to minimize confusion, particularly with rainbow domination [3, 7, 8, 15]. Polychromatic colorings have appeared elsewhere in the graph theory literature, as well; see for example [14].
The paper will proceed as follows. Section 2 contains first observations and establishes \(\rho(G)\) for some classes of graphs. In Section 3 we give a lower bound for graphs with diameter at least 3 and an upper bound for graphs with no isolated vertices. Finally we look at cases not covered by the lower bound in Section 4.
Lemma 2.1. Let \(G\) be a graph with \(|V(G)| = n\). Then \(\gamma(G) \leq \rho(G) \leq n\).
Both extremes of the above bounds are possible, and we characterize some cases. If \(\gamma(G)=1\) with \(v \in V(G)\) a vertex of degree \(n-1\), then in any coloring of \(G\) the set \(\{v\}\) is a polychromatic dominating set. Thus \(\gamma(G)=1\) implies \(\rho(G)=1\). Together with the above lemma, this gives the following result.
Theorem 2.2. \(\rho(G) = 1\) if and only if \(\gamma(G) = 1\).
At the other extreme, if \(G\) is the empty graph then \(\gamma(G) = n\), and clearly \(\rho(G) = n\) as well. However it is also possible that \(\rho(G) = n > \gamma(G)\). Consider a graph \(G\) with at least 2 isolated vertices \(\{u,v\}\). In any coloring of \(G\) where \(\{u,v\}\) both receive the same color, there is no polychromatic dominating set and thus \(\rho(G) = n\). Now suppose that \(H\) is a graph with an (\(n-1\))–coloring \(c\) that has no polychromatic dominating set, and suppose \(\{u,v\}\) are the two vertices that receive the same color under \(c\). The set \(V \setminus \{u\}\) is polychromatic and dominating unless \(v\) is an isolated vertex. Thus both \(u\) and \(v\) must be isolated in order for there to be no polychromatic dominating set under \(c\). We have shown the following.
Theorem 2.3. Let \(G\) be a graph with \(|V(G)| = n\). Then \(\rho(G) = n > 1\) if and only if \(G\) contains at least 2 isolated vertices.
A sharp lower bound for the case where there is exactly one isolated vertex will be given in Subsection 2.3.
Adding more edges to a graph can only decrease the domination number. Along the same lines it is easy to see the following useful observation.
Lemma 2.4. Let \(H\) and \(G\) be graphs. If \(H\) is a spanning subgraph of \(G\), then \(\rho(G) \leq \rho(H)\).
By Lemma 2.1 and Theorem 2.3, \(\rho(G)=2\) only if \(\gamma (G)=2\). This condition is necessary but not sufficient. Two sufficient conditions are given in the next propositions.
Let \(\omega(G)\) be the clique covering number of a graph \(G\).
Proposition 2.5. Let \(G\) be a graph with \(\delta(G)<n-1\) and \(\omega(G)=2\). If \(\gamma(G) = 2\) then \(\rho(G)= 2\).
Proof. Suppose the cliques covering \(G\) are \(K_m\) and \(K_n\), with \(1 \leq m < n\). In any 2-coloring of \(G\) there is some vertex in the \(K_m\) subgraph that is a different color from some vertex in the \(K_{n-m}\) subgraph, and hence \(\rho(G)=2\). ◻
Similar reasoning gives us the following.
Proposition 2.6. If \(K_{m,n-m} \subseteq G\), for some \(1\leq m<n\), and \(\gamma(G) = 2\) then \(\rho(G)= 2\).
There are many other graphs with \(\rho(G)=2\) as well. For example, define \(G\) with vertices \(V(G) = \{1, \dots, k+l\}\) and with edges such that \(\{1, \dots, k\}\) forms a \(K_k\) except no edge \(\{1,2\}\); \(\{k+1, \dots, k+l\}\) forms a \(K_l\); and the edges \(\{1,k+1\}, \{2, k+2\} \in E(G)\).
It is clear that if \(\rho(G)=2\) then every vertex \(v\in V(G)\) is in some dominating set of size 2. If not then the coloring with \(v\) blue and all other vertices red would not admit a polychromatic dominating set. Graphs with \(\gamma(G) = 2\) that are well-dominated (all minimal dominating sets of the same cardinality) satisfy the condition that every vertex is in a dominating set of size 2. We do not know whether every graph in this class has \(\rho (G) =2\). The complete bipartite graph shows that it is not necessary for a graph to be well-dominated in order to have \(\rho(G) =2\).
For a graph \(G\), we can define the companion graph \(D(G)\) on the same set of vertices with an edge between two vertices if they form a dominating set.
Proposition 2.7. \(\rho(G)=2\) if and only if \(\delta(G) < n-1\), \(\gamma(G) = 2\), and \(D(G)\) is connected and therefore has a spanning tree.
We could define the hypergraph \(D(G)\) more generally for a graph \(G\) with \(\gamma(G)> 2\). For a graph \(G=(V,E)\), define the dominating set hypergraph \(\mathcal{H}(G)\) on the vertex set \(V(G)\) where \(D \in E(\mathcal{H}(G))\) if and only if \(D\) is dominating. Let \(\rho(\mathcal{H}(G))\) be the minimum number of colors needed so that, in any coloring of \(V(\mathcal{H}(G))\), some edge has vertices of all different colors. Then \(\rho(G) = \rho(\mathcal{H}(G))\). Proposition 2.7 then easily generalizes as follows.
Proposition 2.8. If there exists a partition of \(V(\mathcal{H}(G))\) into \(k\) parts so that every edge of \(\mathcal{H}\) has two vertices in some part, then \(\rho(\mathcal{H}) \geq k\).
The polychromatic domination number for all forests will follow easily from the results above and Theorem 3.5 in Section 3. Thus our first example is cycles.
Theorem 2.9. If \(n > 6\), then \(\rho(C_n) = n-4\).
Proof. First we establish that \(\rho(C_n) > n-5\). It will suffice to find an \((n-5)\)–coloring of \(C_n=(v_1, v_2, \ldots, v_n)\) with no polychromatic dominating set. To that end, consider the \((n-5)\)–coloring of \(C_n\) with color set \(A\) that assigns color \(c\) to vertices \(v_1, v_2, v_3, v_4, v_5\), and \(v_6\), and assigns each of the remaining \(n-6\) vertices a distinct color. Any dominating set for \(C_n\) must have at least two vertices from the set \(\{ v_1, v_2, v_3, v_4, v_5, v_6\}\). Since all of these vertices are of color \(c\), this coloring admits no polychromatic dominating set.
It remains to be shown that \(\rho(C_n) \leq n-4\). Suppose \(C_n\) is arbitrarily colored with \(n-4\) colors. Let \(R\) be a subset of the vertices of \(C_n\) such that one vertex of each color exists in \(R\). Thus, there are 4 vertices not in \(R\). There are three cases:
Case 1. Each of the four vertices is adjacent to something in \(R\) and so \(R\) is a polychromatic dominating set.
Case 2. Exactly one of the vertices is not adjacent to something in \(R\). Then three of the vertices are adjacent to each other, say \(v_j, v_{j+1},\) and \(v_{j+2}\), and only \(v_{j+1}\) is neither in nor adjacent to something in \(R\). If \(v_{j+1}\) is not the same color as either \(v_{j-1}\) or \(v_{j+3}\), then it is the same color as some other vertex, say \(v_k\). Define a new set \(R^{\prime}= R \cup\{ v_k\} \setminus \{v_{j+1}\}\); \(R^{\prime}\) is now a polychromatic dominating set.
If \(v_{j+1}\) is the same color as \(v_{j-1}\), then define \(R^{\prime}=R \setminus \{v_{j-1}\}\cup \{v_{j+1}\}\). Then \(v_j\) and \(v_{j+2}\) are adjacent to \(v_{j+1}\) and, since \(C_n\) has at least 7 vertices, there exists a vertex in \(R^{\prime}\) adjacent to \(v_{j-1}\). So \(R^{\prime}\) is a polychromatic dominating set.
Case 3. Two of the four vertices are not adjacent to something in \(R\). Then the four vertices not in \(R\) are all adjacent to each other. Label them \(v_i, v_{i+1}, v_{i+2}\), and \(v_{i+3}\).
If one of \(v_{i+1}\) and \(v_{i+2}\), say \(v_{i+1}\), is the same color as another vertex in \(C_n\) that is not \(v_{i-1}\) or \(v_{i+4}\), say \(v_k\), then define \(R^{\prime} = R \cup \{v_{i+1}\} \setminus \{v_k\}\), a polychromatic dominating set.
If \(v_{i+1}\) and \(v_{i-1}\) share a color and \(v_{i+2}\) and \(v_{i+4}\) share a color then define \(R^{\prime} = R \cup \{v_{i+1}\} \setminus \{v_{i-1}\}\). Then, since \(v_i\) and \(v_{i+2}\) are adjacent to \(v_{i+1}\) and since \(C_n\) has at least 7 vertices, there exists a vertex in \(R^{\prime}\) adjacent to \(v_{i-1}\). So, again, \(R^{\prime}\) is a polychromatic dominating set.
So essentially, if \(m\) is the maximum number of consecutive vertices of the same color, a “run” of vertices of this color, then \(1 \leq m \leq 4\). If \(m=1, 2\), then \(R\) is dominating. If \(m=3,4\), then \(R^{\prime}\) is a polychromatic dominating set where \(R^{\prime}\) is simply the set \(R\) with a vertex of the run removed and an internal vertex (one only adjacent to vertices of the same color as itself) of the run added. ◻
One can of course use brute force to show \(\rho(C_3)=1\), \(\rho(C_4)=\rho(C_5) = 2\), and \(\rho(C_3)=3\). To see that \(\rho(C_6)\geq 3\) consider the 6-cycle with two antipodal vertices blue and the other four red. It has no polychromatic dominating set. This example highlights the following useful fact.
Observation 2.10. For a graph \(G\), there may be a \(k\)-coloring in which more than one color is used multiple times that admits no polychromatic dominating set, and yet every \(k\)-coloring with only one repeated color has a polychromatic dominating set.
Observation 2.10 means that any case analysis used to determine \(\rho(G)\) must consider multiple ways to distribute any repeated colors.
In Figure 1, we show a 4-coloring of the Petersen graph with no polychromatic dominating set, thus establishing a lower bound of 5 on our parameter. Essentially, we show that there exists a partition of \(V(G)\) into four parts such that no transversal of these four sets is dominating. A straightforward case analysis shows that equality is achieved, and thus the proof of Theorem 2.11 is omitted.
Theorem 2.11. \(\rho\)(Petersen graph) \(= 5\).
In this subsection we consider how \(\rho(G)\) behaves on graphs that are combinations of other graphs. Specifically, we consider unions, some products, and joins. We begin with graph unions.
We note that Theorem 3.3 may give a better bound than Theorem 2.12 below when \(\rho(G)\) and \(\rho(H)\) are small.
Theorem 2.12. If \(\rho(G) > 1\) then \(\rho(G \cup H) \geq \rho(G) + |V(H)|\). If \(\rho(G), \rho(H) > 1\) then \(\rho(G \cup H) \geq \max\{\rho(G) + |V(H)|, \rho(H) + |V(G)|\}\).
Proof. Let \(c : G \rightarrow \{1, 2, \ldots, \rho(G)-1\}\) be a \((\rho(G)-1)\)–coloring of \(G\) that has no polychromatic dominating set. Extend \(c\) to a coloring of \(G \cup H\) by coloring each vertex of \(H\) with a new unique color. Thus \(\rho(G \cup H) \geq \rho(G) +|V(H)|\). If \(\rho(H) > 1\) as well, then similarly \(\rho(G \cup H) \geq \rho(H)+|V(G)|\). ◻
We highlight the special case when \(G\) has exactly one isolated vertex.
Corollary 2.13. If \(G\) has exactly one isolated vertex \(v\) then \(\rho(G) \geq \rho(G-\{v\}) + 1\).
Theorem 2.12 does not extend to the case \(\rho(G) = \rho(H) = 1\). As shown in Proposition 2.5 it is easy to see that \(\rho(K_k \cup K_{n-k}) = 2\) for any \(n,k\); and certainly for any graphs \(G, H\), \(\rho(G \cup H) \geq 2\). Observe that, for \(S_k\) a star on \(k\) vertices, \(\rho(S_k \cup S_{n-k}) = n-2\), and so there are a wide range of possibilities if \(\rho(G) = \rho(H) = 1\). Even when \(\rho(G) = 1\), specific cases can be surprisingly difficult to compute. For example we have the following.
Proposition 2.14. For \(n, m > 1\), \(\rho(K_{n,m} \cup \{v\}) = \max\{n,m\}+1\).
The above example also shows that the lower bound of Corollary 2.13 may be far off.
The lexicographic product of graphs \(G\) and \(H\), denoted \(G \bullet H\), has vertex set \(V(G\bullet H) = V(G) \times V(H)\), and \((u_1,v_1)(u_2,v_2) \in E(G \bullet H)\) if and only if \(u_1u_2 \in E(G)\), or \(u_1=u_2\) and \(v_1v_2 \in E(H)\).
We can think of \(G \bullet H\) as a copy of \(H\) with each of its vertices \(y\) replaced by a copy of \(G\), \(G \cdot y\) say. We note that if \(x, y \in V(H)\) and \(x \sim y\), then each of the vertices of \(G \cdot x\) is adjacent to every vertex of \(G \cdot y\).
Theorem 2.15. For \(m,n >1\), \(\rho(P_{n} \bullet P_{m}) = nm-2n-2.\)
Proof. Let the vertices of \(P_m\) be \(v_1, v_2, \ldots, v_m\), and let the vertices of \(P_n \cdot v_i\) be \(u_{i,1}, u_{i, 2}, \ldots,\) \(u_{i,n}\). To show that the right hand side of our equation is a lower bound for \(\rho\), consider the following coloring of the vertices of \(P_{n} \bullet P_{m}\): (1) all of the vertices of \(P_n \cdot v_3, P_n \cdot v_4, \ldots, P_n \cdot v_{m-2}\) receive different colors, (2) the vertices \(u_{1,1}, u_{1, 2}, u_{1,n-2}\), and \(u_{n, 1}, u_{n, 2}, u_{n, n-2}\) each receive an additional unique color, and (3) the remaining vertices all receive the same color (shown in blue in Figure 2). It is easy to see that such a coloring does not admit a polychromatic dominating set. It is a straightforward case analysis to show that the right hand side of our equation is also an upper bound and thus equality is achieved. ◻
Theorem 2.15 also follows directly from Theorem 3.3, however the proof above generalizes in a useful way. An argument as in the proof above will establish the lower bound of Theorem 2.16 below. The idea is that each of the vertices of \(G \cdot v_3, G \cdot v_4, \ldots, G \cdot v_{m-2}\) receive different colors, that we use only \(\rho(G)-1\) colors on each of \(G \cdot v_1\) and \(G \cdot v_n\), and that the remaining vertices all receive the same color.
Theorem 2.16. For \(n, m > 1\), \(\rho(G \bullet P_{m}) \geq |V(G)|(m-4) + 2(\rho(G)-1) + 2\).
Although the result given in Theorem 2.15 shows that the lower bound given in Theorem 2.16 is tight, equality does not hold in general. To see this, consider the graph \(K_{1,n-1} \cdot P_m\), with \(u_0\in K_{1,n-1}\) the universal vertex (of degree \(n-1\)) and other vertices of \(K_{1,n-1}\) \(\{u_1, \dots , u_{n-1}\}\). We show there is a coloring using many more than \(nm-4n + 2\) colors which fails to admit a polychromatic dominating set. As in the scheme used in the argument for Theorem 2.16, color each of the vertices in \(K_{1,n-1} \cdot v_2\) and \(K_{1,n-1} \cdot v_{m-1}\) the same color, say blue. Use blue on \((u_0,v_1), (u_0, v_n), (u_1, v_1),(u_1, v_n)\) and use a unique (non-blue) color on all other vertices. This coloring uses \(nm-2n-3\) colors and fails to have a polychromatic dominating set.
Recall that the join of graphs \(G\) and \(H\), \(G \vee H\), has vertex set \(V(G) \cup V(H)\) and edge set \(E(G)\cup E(H) \cup \{uv~:~ u \in V(G) \text{ and } v \in V(H) \}\). We note that \(G \vee H\) is always connected with diameter at most 2 (with equality except when both \(G\) and \(H\) are complete), and thus we revisit the results in the remainder of this section in Section 4.
Observation 2.17. Let \(G\) and \(H\) be graphs, neither of which is complete. Then \(\rho(G \vee H) = 2.\) Otherwise if \(G\) or \(H\) is complete, then \(\rho(G \vee H) = 1\).
The example following Theorem 2.16 showed that when the first graph, \(G\), in a lexicographic product has a universal vertex then \(\rho(G\bullet H)\) can take on a wide assortment of values. This is not true when the second graph \(H\) has a universal vertex.
Observation 2.18. Let \(U\) be a graph with a universal vertex. Then
\[\rho(G \bullet U) = \left\{ \begin{array}{ll} 1, & \mbox{if $G$ has a universal vertex,} \\ 2, & \mbox{otherwise.} \end{array} \right.\]
Theorem 2.19. Let \(G, H, F\) be graphs. Then
\[\rho(F \bullet (G \vee H)) = \left\{ \begin{array}{ll} 1, & \mbox{if $F$ and one of $G, H$ has a universal vertex,} \\ 2, & \mbox{otherwise.} \end{array} \right.\]
Proof. If \(F\) and one of \(G, H\) has a universal vertex, then \(F \bullet (G \vee H)\) has a universal vertex, and any vertex set of size one is a polychromatic dominating set. Otherwise, as above, we think of \(F \bullet (G \vee H)\) as a copy of \(G \vee H\) with each of its vertices replaced by a copy of \(F\). A polychromatic dominating set of any 2-coloring of this graph can be obtained by taking one vertex from any copy of \(F\) corresponding to a vertex in \(G\) and a differently colored vertex from any copy of \(F\) corresponding to a vertex in \(H\). ◻
We are now ready to present our most useful results. The upper and lower bounds below both are functions of the smallest degree(s) in the graph.
Theorem 3.1. If \(G\) is a graph with minimum degree \(\delta\) then \(\rho(G) \leq n-\delta -1\).
Proof. Consider a graph \(G\) with minimum degree \(\delta\) and an \((n-\delta-1)\)–coloring. We show it contains a polychromatic dominating set. Let \(R\) be an arbitrary set of vertices in \(G\) such that \(R\) contains exactly one vertex of every color. There are \(\delta + 1\) vertices \(\{v_1, v_2, \ldots, v_{\delta + 1}\}\in V(G)\) which are not in \(R\). If each of these vertices is adjacent to a vertex in \(R\) then \(R\) is a polychromatic dominating set.
Suppose at least one of \(v_1, v_2, \ldots, v_{\delta + 1}\) is not adjacent to a vertex in \(R\), say \(v_i\), \(1 \leq i \leq \delta+1\). Then \(v_i\) must be adjacent to all of the \(\delta\) vertices in the set \(\{v_1, v_2, \ldots, v_{i-1}, v_{i+1}, \ldots, v_{\delta + 1}\}\). Consider one such neighbor of \(v_i\), say \(v_j\). Since \(R\) contains a vertex of every color, \(R\) contains one vertex that is the same color as \(v_j\); call it \(r_j\).
Consider the set \(R'=R\setminus \{r_j\} \cup \{v_j\}.\) Because \(r_j\) has degree at least \(\delta\) and \(r_j\) is not adjacent to \(v_i\), then \(r_j\) is either adjacent to \(v_j\) or it is adjacent to something in \(R\). It remains to be shown that if \(x \in \{v_1, v_2, \ldots, v_{i-1}, v_{i+1}, \ldots, v_{\delta + 1}\}\), then \(R^ {\prime}\) dominates \(x\). Again, if \(x\) is not adjacent to \(v_j\) then it is adjacent to at least one vertex of \(R^{\prime}\) since \(x\) has minimum degree \(\delta\). In all cases, \(R'\) is a polychromatic dominating set in \(G\). ◻
Any graph with minimum degree \(\delta(G)=n-2\) and at least one universal vertex will achieve this upper bound. For an example without a universal vertex, see Figure 3.
Theorem 3.2. If a graph \(G\) has vertices \(v\) and \(w\) at distance at least 3 then \(\rho(G) \geq n – \deg(v) – \deg(w)\).
Proof. Let \(v_1, v_2\) be vertices of degree \(\delta_1\) and \(\delta_2\), respectively. By assumption \(|N[v_1] \cup N[v_2]| = \delta_1+\delta_2+2\). Define the \((n-\delta_1-\delta_2-1)\)–coloring \(c\) such that \(c\) assigns the same color to each vertex in \(N[v_1] \cup N[v_2]\), and every vertex in \(V \setminus (N[v_1] \cup N[v_2])\) receives a unique color. This coloring has no polychromatic dominating set. ◻
This upper bound is tight as shown by the family of examples \(K_k \cup K_{n-k}\). The bound is also tight for some small values of \(\delta_i\) as shown in Theorem 3.4. In particular, note that the upper and lower bounds are equal when \(\delta_1(G)\leq \delta_2(G)= 1\).
More generally, we have Theorem 3.3 below.
Theorem 3.3. Let \(G\) be a graph and let \(X \subseteq V(G)\) such that any dominating set of \(G\) intersects \(X\) in at least two vertices. Then \(\rho(G) \geq n – |X| + 2.\)
Proof. Any coloring in which all vertices of \(X\) are colored the same color admits no polychromatic dominating set. ◻
The lower bound of Theorem 3.2 is achieved for some small values of \(\delta_1, \delta_2\). Let \(\delta_1(G), \delta_2(G)\) be the degrees of \(v_1, v_2\in V(G)\) such that \(\deg (v_1) + \deg (v_2) = \delta_1(G) + \delta _2(G)\) is as small as possible and \(d(v_1, v_2) \geq 3\) (possibly \(\infty\)).
Theorem 3.4. If \(\delta_1 (G) + \delta_2(G) \leq 2\) then \(\rho (G) = n-\left(\delta_1(G) + \delta_2(G)\right)\).
Proof. Theorem 2.3 deals with the case where \(G\) has at least two isolated vertices, and thus \(\delta_1(G) + \delta_2(G) =0\). The cases where \(\delta_1(G)=0, \delta_2(G)=1\) and \(\delta_1(G) = \delta_2(G) =1\) both follow from Theorem 3.1.
For the final case, where \(\delta_1(G)=0\) and \(\delta_2(G) =2\), consider an \((n-2)\)–coloring and set \(R\) that contains exactly one vertex of each color. It is always possible to select \(R\) such that it contains the one isolated vertex. Consider the two vertices that are not in \(R\); each has degree at least \(2\), as they are of distance \(=\infty \geq 2\) from the isolated vertex. Even if these two vertices are adjacent, they each have at least one neighbor in \(R\) and hence \(R\) is a polychromatic dominating set. (Note that these correspond to particular choices for \(X\) in Theorem 3.3.) ◻
Theorem 3.4 along with Theorem 2.2 and Theorem 2.3 completes the analysis of \(\rho(G)\) for all forests.
Theorem 3.5. If \(G\) is a forest on \(n\) vertices then \[\rho(G) = \begin{cases} 1 & \text{if $G$ is a star,} \\ n & \text{if $G$ contains at least two isolated vertices,} \\ n-2 & \text{otherwise.} \end{cases} \tag{1}\]
The lower bound shown in Theorem 3.2 does not apply to graphs of diameter 2. Hence we consider them briefly here.
Notice that the graphs in Results 2.17–2.19 are graphs of diameter 2 for which \(\rho\) is very low. We will now construct some classes of graphs of diameter 2 for which we can make \(\rho\) any value between 3 and \(n-3\) inclusive.
In [12], the authors define the following family of graphs \(\mathcal{G}\) (with diameter 2): Let \(G_7\) be the graph obtained from a 3-cycle by adding a pendant edge to each vertex of the cycle and then adding a new vertex and joining it to the three degree-1 vertices. Let \(\mathcal{G}\) be the family of graphs that contains \(C_5, G_7\), and the Petersen graph and is closed under degree-2 vertex duplication. See Figures 3, 4, and 5. In their paper, the authors show these are precisely the graphs for which equality is achieved in the Erdö–Rényi Theorem, specifically: If \(G\) is a diameter 2 graph of order \(n\) and size \(m\) with no dominating vertex, then \(m \geq 2n-5\) with equality if and only if \(G \in \mathcal{G}\).
We proceed by finding the polychromatic domination numbers of the classes of graphs in this family. We have established earlier in the paper that \(\rho(C_5)=2\) and that the polychromatic domination number of the Petersen graph is 5. We now consider the other classes in this family below.
Proposition 4.1. Consider the class of graphs obtained from \(C_5\) after \(k_1\) degree-2 vertex duplications on the same vertex as shown in Figure 3. For any graph \(G\) in this class, \(\rho(G) = k_1 + 2 = n-3.\)
Proof. Let \(G\) be a graph from the class obtained from \(C_5\) after \(k_1\) degree-2 vertex duplications on the same vertex. We will refer to the (sub)graph \(C_5\) from which \(G\) was constructed as the “outer” \(C_5\).
Suppose that there are \(n-3\) colors used on the vertices of \(G\). If our coloring has three colors, each repeated twice, then the outer \(C_5\) has at least three colors. A polychromatic dominating set composed of three (or two) vertices from this outer \(C_5\) can always be found.
Otherwise, either four vertices have the same color, or else two colors are repeated, one three times, and the other two. Let \(R\) be a subset of the vertices of \(G\), one of each color. If \(R\) is a dominating set, we’re done. Otherwise, in either case, the closed neighborhood of a vertex \(t\) of \(G\) of degree 2 is monochromatic. Define a set of vertices \(R^{\prime}\) by swapping \(t\) with its like-colored vertex in \(R\). So \(\rho(G) \leq n-3\).
To see that \(n-4\) colors is insufficient, consider the coloring of Figure 3. That is, color one of the duplicated vertices the same as the original, the rest of the outer \(C_5\) all one color, and the other \(k_1-1\) vertices each a different color. ◻
The proof of Proposition 4.2 is similar, and is thus omitted.
Proposition 4.2. Consider the class of graphs obtained from \(C_5\) after \(k_1\) degree-2 vertex duplications on one vertex and \(k_2\) degree-2 vertex duplications on a different vertex, \(k_1 \geq k_2\), as shown in Figure 4. For \(G\) in this class, \(\rho(G) = k_1 + 2.\)
Since Proposition 4.3 is a special case of Proposition 4.4, the proof is omitted.
Proposition 4.3. \(\rho(G_7)=3\) as shown in Figure 5 on the left.
Proposition 4.4. Consider the class of graphs obtained from \(G_7\) after \(k_1\) degree-2 vertex duplications on one vertex, say \(x_1\), \(k_2\) degree-2 vertex duplications on a second vertex, say \(x_2\), and \(k_3\) degree-2 vertex duplications on the third, say \(x_3\), \(k_1 \geq k_2 \geq k_3\), as shown on the right in Figure 5. For any graph \(G\) in this class, \(\rho(G) = k_1 + 4.\)
Proof. Let \(G\) be a graph from the class obtained from \(G_7\) after \(k_1\) degree-2 vertex duplications on one vertex, \(k_2\) degree-2 vertex duplications on a second vertex, and \(k_3\) degree-2 vertex duplications on the third, \(k_1 \geq k_2 \geq k_3\).
Suppose there are \(k_1+4\) colors used on the vertices of \(G\). If an outer vertex is a different color than the middle (these are the vertices colored blue in the graph shown on the right in Figure 5), then the middle vertex and one of the outer vertices comprise a polychromatic dominating set. So the three outer vertices and the middle vertex all have the same color.
To build a polychromatic dominating set, choose the middle vertex. There are \(k_1+3\) colors left. Even if we use \(k_1+1\) colors on \(x_1\) and its duplicates, there are still two colors remaining. Thus \(x_2, x_3\), and their duplicates cannot be monochromatic. So \(\rho(G) \leq k_1+4\).
Now \(k_1+3\) colors are not enough. To see this, color the outer three vertices and the middle vertex the same color. The vertex \(x_1\) and each of its \(k_1\) duplicates each get different colors, and the remaining vertices all receive the same color. This coloring with \(k_1+3\) colors has no polychromatic dominating set, and thus \(\rho(G) > k_1+3.\) ◻
We note that these are interesting classes of graphs. For instance (as noted at the beginning of the section), by using the family of graphs obtained from \(G_7\), we can make \(\rho\) any value between \(3\) and \(n-3\) by manipulating \(k_1\), \(k_2\), and \(k_3\). Similarly for the graphs described in Proposition 4.2 and shown in Figure 4.
N.E. Clarke was supported by the Natural Sciences and Engineering Research Council of Canada (NSERC, Grant No. 2020-06528) and the Harrison McCain Visitorship Award. R. Haas, S. Hanson, M.Y. Harris, K. Martin, S. Viel, and J. Woods were supported by the National Science Foundation (NSF, Grant No. DMS-1143716).