A special type of algebraic intersection graph called the \(n\)-inordinate invariant intersection graph has been constructed based on the symmetric group, and its structural properties are studied in the literature. In this article, we discuss the different types of dominator coloring schemes of the \(n\)-inordinate invariant intersection graphs and their complements, \(n\)-inordinate invariant non-intersection graphs, by obtaining the required coloring pattern and determining the graph invariant associated with the coloring.
For terminology in group theory, we refer to [4]. For basic definitions and results in graph theory, see [13] and for further concepts related to the dominator coloring patterns considered in the study, refer to [11]. Also, the reader may refer to [5], for the fundamentals in combinatorics.
Coloring and domination in graphs are two well explored areas of research in graph theory. Blending these notions, the dominator coloring of graphs was introduced in the literature, and following this, several variants of domination related coloring patterns have been defined and studied.
The minimum number of colors used in a proper vertex coloring of a graph \(G\) is called the chromatic number of \(G\), denoted by \(\chi(G)\), and any coloring of \(V(G)\) with \(\chi\) colors is called a \(\chi\)-coloring of \(G\). In a graph \(G\), if a vertex \(v \in V(G)\) is adjacent to all vertices \(u \in A\), for some \(A \subseteq V(G)\) or \(A =\{v\}\), we say that \(v\) dominates \(A\) and \(A\) is dominated by \(v\). In this context, if \(v \notin A\), we say that \(v\) properly dominates \(A\) (ref. [7,11]).
Over the years, algebraic graph theory has become an intriguing field of research, wherein the automorphism group of graphs as well as graphs constructed based on different algebraic structures are exclusively studied (c.f. [6,9]). Melding these aspects, an algebraic intersection graph, called the invariant intersection graph of a graph, was constructed based on the automorphism group of graphs, in [10], and from which special class, called the \(n\)-inordinate invariant intersection graph \(\Lambda_{K_n}\), was identified in [12] as the graph with \(V(\Lambda_{K_n}) \cong S_n\) and any two distinct vertices \(v_{\pi}, v_{\pi^\prime} \in V(\Lambda_{K_n})\) corresponding to the permutations \(\pi, \ \pi^\prime \in S_n\) are adjacent in \(\Lambda_{K_n}\) when \(\mathop{\mathrm{fix}}(\pi) \cap \mathop{\mathrm{fix}}(\pi^\prime) \neq \emptyset\), where \(S_n\) is the symmetric group, and for any \(\pi \in S_n\), \(\mathop{\mathrm{fix}}(\pi)\) is the set \(\{x \in S: \pi(x) = x\}\).
An illustration of \(n\)-inordinate invariant intersection graphs is given in Figure 1. Note that the identity permutation is denoted by \(\pi_0\) and the vertex corresponding to a permutation \(\pi \in S_n\) is denoted by \(v_{\pi} \in V(\Lambda_{K_n})\), throughout the study.
In [12], the structural properties of the \(n\)-inordinate invariant intersection graphs \(\Lambda_{K_n}\) and their complements, \(n\)-inordinate invariant non-intersection graphs, denoted by \(\overline{\Lambda}_{K_n}\), were investigated and it was found that \(\Lambda_{K_n} \cong \, \Lambda^\ast_{K_n} \cup \, \rho(n)K_1\), where \(\rho(i)\); \(i \in \mathbb{N}\), is the number of derangements of \(i\) elements and \(\Lambda^\ast_{K_n}\) is the non-trivial component of \(\Lambda_{K_n}\) with diameter 2, having \(n!-\rho(n)\) vertices.
Following the study in [12], different proper vertex colorings of the graphs \(\Lambda_{K_n}\) and \(\overline{\Lambda}_{K_n}\) were discussed in [8]. In this article, we study the variants of dominator coloring of graphs, for the \(n\)-inordinate invariant intersection graphs and their complements.
As \(\Lambda_{K_n}\) has isolated vertices and \(\Lambda^\ast_{K_n}\) has a universal vertex, the study of most of the domination related coloring schemes of these graphs reduce to their chromatic coloring, and a similar situation arises in the case of their complements \(\overline{\Lambda}_{K_n}\), and \(\overline{\Lambda^\ast}_{K_n}\), respectively. Hence, our primary focus of study is on the coloring patterns of the connected graphs \(\Lambda^\ast_{K_n} -v_{\pi_0}\), for \(n \geq 4\), and \(\overline{\Lambda^\ast}_{K_n} -v_{\pi_0}\), for \(n \geq 3\), denoted by \(\Lambda^{\ast\ast}_{K_n}\) and \(\overline{\Lambda^{\ast\ast}}_{K_n}\), respectively.
Note that \(\omega(\Lambda^{\ast\ast}_{K_n}) = \chi (\Lambda^{\ast\ast}_{K_n}) = (n-1)!-1\) and \(\omega(\overline{\Lambda^{\ast\ast}}_{K_n}) = \chi (\overline{\Lambda^{\ast\ast}}_{K_n}) = n\), as it has been proven in [12] that \(\omega(\Lambda_{K_n}) = \chi (\Lambda_{K_n}) = (n-1)!\) and \(\omega(\overline{\Lambda}_{K_n}) = \chi (\overline{\Lambda}_{K_n}) = n+\rho(n); \, n \ge 3\). Also, as the chromatic numbers associated with all the colorings that we consider in our study are minimisation parameters, we do not mention them with the definition of the coloring.
In this section, we examine the variants of dominator colorings of the graphs \(\Lambda_{K_n}\), \(\Lambda^{\ast}_{K_n}\), \(\Lambda^{\ast\ast}_{K_n}\) \(\overline{\Lambda}_{K_n}\), \(\overline{\Lambda^{\ast}}_{K_n}\),and \(\overline{\Lambda^{\ast\ast}}_{K_n}\), and for this, we use the notations \(V_i = \{v_\pi : i \in \mathop{\mathrm{fix}}(\pi)\}\); for \(1 \leq i \leq n\), and \(V_i^k = \{v_\pi \in V_i : |\mathop{\mathrm{fix}}(\pi)|=k \}; \, 1 \le i \le n\); \(1 \le k \le n-2\), throughout the article.
A dominator coloring of a graph \(G\) is a proper vertex coloring of \(G\) such that every vertex dominates at least one color class; possibly its own, and the dominator chromatic number of \(G\) is denoted by \(\chi_{d}(G)\).
A total dominator coloring (resp. double total dominator coloring) of a graph \(G\) is a dominator coloring of \(G\) such that every vertex properly dominates at least one color class (resp. two color classes) and the total dominator chromatic number (resp. double total dominator chromatic number) of \(G\) is denoted by \(\chi_{td}(G)\) (resp. \(\chi_{dtd}(G)\)).
Theorem 2.1. For \(n \ge 4\),
(i) \(\chi_d(\Lambda^{\ast\ast}_{K_n}) = \chi_{td}(\Lambda^{\ast\ast}_{K_n}) = (n-1)!\).
(ii) \(\chi_{dtd}(\Lambda^{\ast\ast}_{K_n}) = (n-1)!+1\).
Proof. (i) In \(\Lambda^{\ast\ast}_{K_n}\), the vertices of \(V^1_i\), for any \(1 \leq i \leq n\), are adjacent only to the vertices in the corresponding \(V_i\). Hence, in any dominator coloring of \(\Lambda^{\ast\ast}_{K_n}\), these vertices can dominate a color class if and only if a color is assigned exclusively for the vertices in that \(V_i\). As each \(V_i; \, 1 \leq i \leq n\), induces a clique in \(\Lambda^{\ast\ast}_{K_n}\), such exclusive color can be given to exactly one vertex and in any \(\chi\)-coloring of \(\Lambda^{\ast\ast}_{K_n}\), this cannot be an exclusive color. Hence, \(\chi_d(\Lambda^{\ast\ast}_{K_n}) \geq (n-1)!\).
As it can be seen that for any two vertices \(v_{\pi^\ast}, v_{\pi^\prime} \in V(\Lambda^{\ast\ast}_{K_n})\) with \(\mathop{\mathrm{fix}}(\pi^\ast) \subseteq \mathop{\mathrm{fix}}(\pi^\prime)\), \(N(v_{\pi^\ast}) \subseteq N(v_{\pi^\prime})\), where \(N(v_{\pi^{\ast\ast}}) = \{v_{\pi^{\prime\prime}} \in V(\Lambda^{\ast\ast}_{K_n}) : v_{\pi^{\ast\ast}} v_{\pi^{\prime\prime}} \in E(\Lambda^{\ast\ast}_{K_n})\}\), for any \(v_{\pi^{\ast\ast}} \in V(\Lambda^{\ast\ast}_{K_n})\), we get the required dominator coloring pattern by validating if all the vertices of \(V_i^{1}; \, 1 \le i \le n\), dominate the required number of color classes.
Define a coloring \(c : V(\Lambda^{\ast\ast}_{K_n}) \to \{c_1,c_2,\ldots, c_{(n-1)!}\}\) as follows. As \(\omega(\Lambda^{\ast\ast}_{K_n})=\chi(\Lambda^{\ast\ast}_{K_n})=(n-1)!-1\), first assign the colors \(c_1,c_2,\ldots, c_{(n-1)!-1}\) to the vertices of \(V_1\) such that \(c(v_{\pi_1}) = c_1\), \(c(v_{\pi_2}) = c_2\), \(c(v_{\pi_3}) = c_3\), where \(\pi_1, \pi_2, \pi_3 \in S_n\) have \(\mathop{\mathrm{fix}}(\pi_1) = (1)(2)\ldots(n-2)\), \(\mathop{\mathrm{fix}}(\pi_2) = (1)(2)\) and \(\mathop{\mathrm{fix}}(\pi_3) = (1)(2)\ldots(n-3)(n)\). Following this, color the vertices \(v_{\pi^{\prime}} \in V_i – \bigcup\limits_{j=1}^{i-1}V_j\), for each \(2 \leq i \leq n\), in order, where the vertices of each \(V_i\); \(2 \leq i \leq n\), are colored with \((n-1)!-1\) colors based on the previously colored vertices in the cliques \(V_j; \, 1 \le j \le i-1\), such that \(c(v_{\pi_4}) = c_1\), \(c(v_{\pi_5}) = c_2\), and \(c(v_{\pi_6}) = c_3\), where \(\pi_4, \pi_5, \pi_6 \in S_n\) have \(\mathop{\mathrm{fix}}(\pi_4) = (n-1)(n)\), \(\mathop{\mathrm{fix}}(\pi_5) = (2)(3)\ldots(n-1)\) and \(\mathop{\mathrm{fix}}(\pi_6) = (n-2)(n-1)\).
The existence of the above mentioned \(\chi\)-coloring \(c\) of \(\Lambda^{\ast\ast}_{K_n}\) is guaranteed,
as the color assigned to any vertex \(v_\pi
\in V_i^{n-2}\) is assigned either exactly to one other vertex in
\(V_{i_1}^2 \cap V_{i_2}^2\), or at
most two vertices; that is, one from \(V_{i_1}^1\) and \(V_{i_2}^1\), where \(1 \le i \ne i_1 \ne i_2 \le n\), and \(i_1,i_2 \notin
\mathop{\mathrm{fix}}(\pi)\), in any \(\chi\)-coloring of \(\Lambda^{\ast\ast}_{K_n}\). This is owing
to the structure of the graph that demands each color class to contain
exactly one vertex from each \(V_i; \, 1 \le i
\le n\) and if any color is assigned to \(v_\pi \in V_i^{n-2}\) with \(i_1, i_2 \notin\mathop{\mathrm{fix}}(\pi)\)
and to a vertex of \(V_{i_1}^1\) and
\(V_{i_2}^1\), we swap one of the \(\rho(n-2)\) colors assigned to the vertices
in \(V_{i_1}^2 \cap V_{i_2}^2\) to
these two vertices, as it does not alter any of the properties of the
considered \(\chi\)-coloring of \(\Lambda^{\ast\ast}_{K_n}\).
Now, in order to make this \(\chi\)-coloring \(c\), a dominator coloring of \(\Lambda^{\ast\ast}_{K_n}\), we assign \(c(v_{\pi_4}) = c_{(n-1)!}\), which makes
all the vertices in \(\bigcup\limits_{i=1}^{n-2}V_i\) dominate
the color class \(\{v_{\pi_1}\}\) and
the vertices in \(\bigcup\limits_{i=n-1}^{n}V_i\) dominate
the color class \(\{v_{\pi_4}\}\).
Also, as it can be seen that all the vertices in \(V(\Lambda^{\ast\ast}_{K_n}) – \{v_{\pi_1},
v_{\pi_4}\}\) properly dominate either the color class \(\{v_{\pi_1}\}\) or \(\{v_{\pi_3}\}\), the vertex \(v_{\pi_1}\) properly dominates the color
class \(\{v_{\pi_2},v_{\pi_5}\}\), and
the vertex \(v_{\pi_4}\) properly
dominates the color class \(\{v_{\pi_3},v_{\pi_6}\}\), in this
dominator coloring \(c\) of \(\Lambda^{\ast\ast}_{K_n}\) with \((n-1)!\) colors, we have \(\chi_d(\Lambda^{\ast\ast}_{K_n}) =
\chi_{td}(\Lambda^{\ast\ast}_{K_n}) = (n-1)!\).
(ii) In the dominator coloring \(c\) of \(\Lambda^{\ast\ast}_{K_n}\) mentioned above, no vertex in \(V_i^1\) dominates two color classes and using the similar arguments mentioned in (i), it can be deduced that \(\chi_{dtd}(\Lambda^{\ast\ast}_{K_n}) \ge (n-1)!+1\). From the dominator coloring \(c\) of \(\Lambda^{\ast\ast}_{K_n}\), we obtain a double total dominator coloring \(c\) of \(\Lambda^{\ast\ast}_{K_n}\) by assigning \(c(v_{\pi_5})=c_{(n-1)!+1}\), which makes every vertex of the graph properly dominate at least two color classes; thereby completing the proof. ◻
Theorem 2.2. For \(n \ge 4\),
(i) \(\chi_d(\overline{\Lambda^{\ast\ast}}_{K_n}) = \chi_{td}(\overline{\Lambda^{\ast\ast}}_{K_n}) = 2(n-1)\).
(ii) \(\chi_{dtd}(\overline{\Lambda^{\ast\ast}}_{K_n}) = 2n-1\).
Proof. Consider the coloring \(c : V(\overline{\Lambda^{\ast\ast}}_{K_n}) \to \{ c_s : 1 \le s \le 2(n-1)\}\) such that for any vertex \(v_\pi \in V(\overline{\Lambda^{\ast\ast}}_{K_n})\), \[c(v_{\pi})= \begin{cases} c_i,& v_{\pi} \in V_i^1, 1 \le i \le n;\\ c_{n-1},& v_{\pi} \in V_{n-1}^2 \cap V^2_n;\\ c_{n+i},& v_{\pi} \in \bigcup\limits_{i=1}^{n-2}\bigcup\limits_{k=2}^{n-2}V_i^k – \bigcup\limits_{j=1}^{i-1} V_j^k.\\ \end{cases}\]
It is a dominator coloring of \(\overline{\Lambda^{\ast\ast}}_{K_n}\) as every vertex that corresponds to a permutation fixing \(k\)-elements dominates at least \(n-k-1\) color classes with respect to this coloring \(c\) of \(\overline{\Lambda^{\ast\ast}}_{K_n}\). Hence, \(\chi_d(\overline{\Lambda^{\ast\ast}}_{K_n}) \le 2(n-1)\).
In \(\overline{\Lambda^{\ast\ast}}_{K_n}\), a vertex \(v_\pi \in V_i; \, 1 \le i \le n\), dominates a color class if and only if none of the vertices in that color class are in the same \(V_i\). Consider a vertex \(v_\pi \in V^{n-2}_i\), for some \(1 \le i \le n\), such that \(t_1, t_2 \notin \mathop{\mathrm{fix}}(\pi)\), where \(1 \le t_1 \ne t_2 \le n\). Therefore, this vertex \(v_\pi\) can dominate a color class if and only if all vertices of the color class are from \((V^2_{t_1} \cap V^2_{t_2}) \cup V^1_{t_1} \cup V^1_{t_2}\). As there are \(\binom{n}{2}\) possible pairs of such \(t_1\) and \(t_2\), we must obtain a color class that is exclusive to each \(V_i; \, 1 \le i \le n\), except one, for any such \(v_\pi \in V_i^{n-2}\) to dominate a color class. All \((n-1)!\) vertices of exactly one \(V_i; \, 1 \le i \le n\), can be colored with the same color because for every \(v_\pi \in V_i^{n-2}\) there are two \(V_j\)’s; \(1 \le i \ne j \le n\), such that they are adjacent to all the vertices of these \(V_j\)’s, and one among them can be chosen to have an exclusive color class. Also, as the \(V_i\)’s are non-disjoint, if colors are assigned to the vertices from each \(V_i\), in the end, for some \(1 \le j \ne i \le n\), \(V_i -\bigcup\limits_{i\ne j=1}^nV_j = V_i^1\). Hence, we require at least \(2n-2\) colors to obtain a dominator coloring of \(\overline{\Lambda^{\ast\ast}}_{K_n}\). Therefore, \(\chi_d(\overline{\Lambda^{\ast\ast}}_{K_n}) = 2(n-1)\). This dominator coloring \(c\) of \(\overline{\Lambda^{\ast\ast}}_{K_n}\) is also its total dominator coloring as every vertex in \(V_i\) properly dominates a color class assigned the color \(c_{i^\prime}\), \(1 \le i \ne i^\prime \le n\), and hence, it follows that \(\chi_{td}(\overline{\Lambda^{\ast\ast}}_{K_n}) = 2(n-1)\).
In any \(\chi_{d}\)-coloring of \(\overline{\Lambda^{\ast\ast}}_{K_n}\), it can be seen that every vertex \(v_{\pi}\) properly dominates at least \(n-k-1\) color classes, where \(k = |\mathop{\mathrm{fix}}(\pi)|\) and all but one vertex in \(\bigcup\limits_{i=1}^nV_i^{n-2}\) properly dominate at least two color classes. Therefore, it can be deduced that in an optimal double total dominator coloring, all \(V^1_i; \, 1 \le i \le n\), have to be assigned unique colors and hence \(\chi_{dtd}(\overline{\Lambda^{\ast\ast}}_{K_n}) = 2n-1\). ◻
Corollary 2.3. For \(n \ge 4\),
(i) \(\chi_{dtd}(\Lambda^{\ast\ast}_{K_n})= \chi_{d}(\Lambda^{\ast\ast}_{K_n})+1\).
(ii) \(\chi_{dtd}(\overline{\Lambda^{\ast\ast}}_{K_n}) = \chi_{d}(\overline{\Lambda^{\ast\ast}}_{K_n}) +1\).
A global dominator coloring (resp. total global dominator coloring) of a graph \(G\) is a proper coloring of \(G\) such that every vertex of \(G\) dominates (resp. properly dominates) as well as anti-dominates at least one color class, where a vertex \(v \in V(G)\) is said to anti-dominate a set \(A \subset V(G)\) if \(uv \notin E(G)\), for all \(u \in A\), such that \(v \notin A\). The global dominator chromatic number (resp. total global dominator chromatic number) of \(G\) is denoted by \(\chi_{gd}(G)\) (resp. \(\chi_{tgd}(G)\)).
Theorem 2.4. For \(n \ge 4\),
(i) \(\chi_{gd}(\Lambda^{\ast\ast}_{K_n}) = (n-1)!+(n-3)\).
(ii) \(\chi_{tgd}(\Lambda^{\ast\ast}_{K_n}) = (n-1)!+(n-2)\).
(iii) \(\chi_{gd}(\overline{\Lambda^{\ast\ast}}_{K_n}) = \chi_{tgd}(\overline{\Lambda^{\ast\ast}}_{K_n}) = 2n\).
Proof. (i) Any vertex \(v_{\pi} \in V_i^{n-2}\) is not adjacent to \(2\rho(n-1)\) vertices of \(V_{i^\prime}^1\) and \(\rho(n-2)\) vertices of \(V_{i^\prime}^2\), such that \(1 \le i \ne i^\prime \le n\) and \(i^\prime \notin \mathop{\mathrm{fix}}(\pi)\), in \(\Lambda^{\ast\ast}_{K_n}\). Therefore, if a vertex \(v_{\pi} \in V_i^{n-2}\) has to anti-dominate any color class with respect to some proper coloring of \(\Lambda^{\ast\ast}_{K_n}\), such a color class must contain only the vertices of \(V_{i_1}^1 \cup V^1_{i_2} \cup (V^2_{i_1} \cap V^2_{i_2})\), where \(1 \le i_1 \ne i_2 \le n\), and \(i_1,i_2 \notin \mathop{\mathrm{fix}}(\pi)\). As there are \(\binom{n}{2}\) possible pairs of such \(i_1\) and \(i_2\), we must obtain a color class that is exclusive to each \(V_i; \, 1 \le i \le n\), except one, for any such \(v_\pi \in V_i^{n-2}\) to anti-dominate a color class. Hence, \(\chi_{gd}(\Lambda^{\ast\ast}_{K_n}) \ge \chi(\Lambda^{\ast\ast}_{K_n})+(n-2)\).
There exists a \(\chi\)-coloring of \(\Lambda^{\ast\ast}_{K_n}\), say \(c^\ast\), in which some color \(c_t; \,1 \le t \le (n-1)!-1\), is assigned to \(n\) vertices of \(V_i^1\); that is, one from each \(V_i^1\), as every color class in any \(\chi\)-coloring of \(\Lambda^{\ast\ast}_{K_n}\) must contain one vertex from each \(V_i; \, 1 \le i \le n\), and let \(v_{\pi_i} \in V_i^1; \, 1 \le i \le n\), be \(n\) vertices such that for all \(1 \le i \le n\), \(c^\ast(v_{\pi_i}) = c_t\), for some \(1 \le t \le (n-1)!-1\). The existence the coloring \(c^\ast\) is guaranteed owing to the nature of the color classes in any \(\chi\)-coloring of \(\Lambda^{\ast\ast}_{K_n}\) and the fact that \(V_i\)’s are non-disjoint.
We make such a \(\chi\)-coloring \(c^\ast\) of \(\Lambda^{\ast\ast}_{K_n}\), a global dominator coloring of \(\Lambda^{\ast\ast}_{K_n}\), by assigning the color \(c_{(n-1)!-1+i}\) to the vertex \(v_{\pi_i} \in V_i^1; \, 1 \le i \le n-2\). Now, only one vertex in \(V_{n-1}^1\) and one vertex in \(V_n^1\) have the color \(c_t\), and as mentioned in Theorem 2.1, we swap the color of the vertices \(v_{\pi_{n-1}}\) and \(v_{\pi_n}\) with the color of a vertex, say \(v_{\pi^\prime}\), in \(V_{n-1}^2 \cap V_{n}^2\). Here, every vertex in \(V_i; \, 1 \le i \le n-2\), dominates the color class \(\{v_{\pi_i}\}\) and the vertices of \(V_{n-1} \cup V_n\) dominate the color class \(\{v_{\pi^\prime}\}\). Also, any vertex \(v_\pi \in V(\Lambda^{\ast\ast}_{K_n}) – \{v_{(1)(2)\ldots(n-2)}\}\) anti-dominates the color class \(\{v_{\pi_{i^\prime}}\}\), \(1 \le i^\prime \le n\) such that \(i \notin \mathop{\mathrm{fix}}(\pi)\) and the vertex \(v_{(1)(2)\ldots(n-2)}\) anti-dominates the color class \(\{v_{\pi^\prime}\}\); thereby, yielding \(\chi_{gd}(\Lambda^{\ast\ast}_{K_n}) = (n-1)!+n-3\).
(ii) In the above mentioned global dominator coloring \(c^\ast\) of \(\Lambda^{\ast\ast}_{K_n}\), all the vertices of \(V(\Lambda^{\ast\ast}_{K_n})\), except the ones in \(V_i^1\) assigned the colors \(c_{(n-1)!-1+i}\), for \(1 \le i \le n-2\), and the vertex \(v_{\pi^\prime}\), does not properly dominate any color class. Therefore, it can be seen from (i) that we require at least \(\chi_{gd}(\Lambda^{\ast\ast}_{K_n}) +1\) colors, in any total global dominator coloring of \(\Lambda^{\ast\ast}_{K_n}\).
To obtain a total global dominator coloring of \(\Lambda^{\ast\ast}_{K_n}\) with \(\chi_{gd}(\Lambda^{\ast\ast}_{K_n}) +1\) colors, consider the coloring \(c^\ast\) defined above and assign the color \(c_{(n-1)!+n-2}\) to the vertex \(v_{(1)(2)\ldots(n-2)}\), which makes the vertices \(v_{\pi_i}; \, 1 \le i \le n-2\), dominate the color class \(\{v_{(1)(2)\ldots(n-2)}\}\). As mentioned in Theorem 2.1, any color, say \(c_r\), for some \(1 \le r \le (n-1)!-1\) and \(r \ne t\), assigned to the vertex \(v_{(1)(2)\ldots(n-2)}\) is assigned either exactly to one other vertex of the form \(v_{(n-1)(n)}\) or at most two vertices of the form \(v_{(n-1)}\) and \(v_{(n)}\), in any proper coloring of \(\Lambda^{\ast\ast}_{K_n}\). Hence, as the vertex \(v_{(1)(2)\ldots(n-2)}\) is assigned a new color by \(c^\ast\), the vertex now \(v_{\pi^\prime}\) properly dominates the color class of the color \(c_r\) which was earlier assigned to the vertex \(v_{(1)(2)\ldots(n-2)}\). Therefore, we obtain an optimal total global dominator coloring of \(\Lambda^{\ast\ast}_{K_n}\) with \((n-1)!+(n-2)\) colors.
(iii) By Theorem 2.2, it can be seen that in any \(\chi_d\)-coloring of \(\overline{\Lambda^{\ast\ast}}_{K_n}\), any vertex \(v_{\pi}\) anti-dominates at most \(k-1\) color classes, where \(k = |\mathop{\mathrm{fix}}(\pi)|\). Therefore, we require additional colors for the vertices \(V_i^1; \, 1 \le i \le n\), to anti-dominate some color class. For any vertex in \(V_i^1; \, 1 \le i \le n\), to anti-dominate a color class, the color must exclusively be assigned to the vertices to which it is not adjacent to; that is, only to the vertices of that particular \(V_i\). Therefore, to minimise the number of such additional colors, we assign the color \(c_{2n-1}\) to the vertex \(v_{\pi}\), such that \(|\mathop{\mathrm{fix}}(\pi)| = n-2\). If \(t_1, t_2 \notin \mathop{\mathrm{fix}}(\pi)\), then the vertices of \(V_{t_1}^1\) and \(V_{t_2}^1\); for some \(1 \le t_1 \le t_2 \le n\), still do not anti-dominate any color class. Hence, a vertex \(v_{\pi^\prime}\) such that \(\{t_1, t_2\} \subseteq \mathop{\mathrm{fix}}(\pi^\prime)\), is assigned the color \(c_{2n}\) to obtain a global dominator coloring of \(\overline{\Lambda^{\ast\ast}}_{K_n}\) with \(2n\) colors. Note that the above mentioned coloring is also a total global dominator coloring of \(\overline{\Lambda^{\ast\ast}}_{K_n}\), as every vertex of the graph properly dominates a color class. Also, as the minimality of the parameter follows from the structure of \(\overline{\Lambda^{\ast\ast}}_{K_n}\) and the global dominator coloring protocol, \(\chi_{gd}(\overline{\Lambda^{\ast\ast}}_{K_n}) = \chi_{tgd}(\overline{\Lambda^{\ast\ast}}_{K_n}) = 2n\). ◻
A proper coloring \(c\) of a graph \(G\) is said to be a rainbow dominator coloring of \(G\) if \(c\) is a dominator coloring of \(G\) such that for every \(u,v \in V(G)\), there exists a \(u-v\) path in which no two internal vertices have the same color and the rainbow dominator chromatic number of \(G\) is denoted by \(\chi_{rd}(G)\). A power dominator coloring of a graph \(G\) is a proper vertex coloring of \(G\) such that every vertex power dominates at least one color class; possibly its own, and the power dominator chromatic number of \(G\) is denoted by \(\chi_{pd}(G)\). A vertex \(v \in V(G)\) is said to power dominate the vertices in \(M(v) \subseteq V(G)\), which is constructed as follows.
(i) \(M(v) = N[v]\).
(ii) Consider a vertex \(w \notin M(v)\) and add it to \(M(v)\) if there exists a \(u \in N(w) \cap M(v)\) such that all \(v_1 \in N(u)-\{w\}\) are already in \(M(v)\).
(iii) Repeat Step (ii) until no vertex could be added to \(M(v)\).
Proposition 2.5. For any \(n \geq 4\),
(i) \(\chi_{rd}(\Lambda^{\ast\ast}_{K_n}) = \chi_{pd}(\Lambda^{\ast\ast}_{K_n}) = \chi_{d}(\Lambda^{\ast\ast}_{K_n}).\)
(ii) \(\chi_{rd}(\overline{\Lambda^{\ast\ast}}_{K_n}) =\chi_{pd}(\overline{\Lambda^{\ast\ast}}_{K_n}) =\chi_{d}(\overline{\Lambda^{\ast\ast}}_{K_n})\).
Proof. As the graph \(\Lambda^{\ast\ast}_{K_n}\) has diameter 2, all \(u-v\) path of length 2 between any two vertices of \(\Lambda^{\ast\ast}_{K_n}\), whose only internal vertex has a distinct color. Hence, \(\chi_{rd}(\Lambda^{\ast\ast}_{K_n}) = \chi_{d}(\Lambda^{\ast\ast}_{K_n})\). In \(\overline{\Lambda^{\ast\ast}}_{K_n}\), any two non-adjacent vertices \(v_{\pi_1}\) and \(v_{\pi_2}\) correspond to permutations such that \(\mathop{\mathrm{fix}}(\pi) \cap \mathop{\mathrm{fix}}(\pi_1) \ne \emptyset\). Here, if \(1 \le |\mathop{\mathrm{fix}}(\pi_1) \cup \mathop{\mathrm{fix}}(\pi_2)| \le n-2\), then there is a path of length 2 between the vertices \(v_{\pi_1}\) and \(v_{\pi_2}\) in \(\overline{\Lambda^{\ast\ast}}_{K_n}\) and its internal vertex is uniquely colored, in any proper coloring of \(\overline{\Lambda^{\ast\ast}}_{K_n}\). If \(|\mathop{\mathrm{fix}}(\pi_1) \cup \mathop{\mathrm{fix}}(\pi_2)| = n\), then the non-adjacent vertices do not have a common neighbour and we have a path \(v_{\pi_1}-v_{\pi_1^\prime}-v_{\pi_2^\prime}-v_{\pi_2}\), where \(v_{\pi_1^\prime} \in V_i^1\) and \(v_{\pi_2^\prime} \in V_{i^\prime}^1\), where \(1 \le i \ne i^\prime \le n\), such that \(i \notin \mathop{\mathrm{fix}}(\pi_1)\) and \(i^\prime \notin \mathop{\mathrm{fix}}(\pi_2)\). As \(|\mathop{\mathrm{fix}}(\pi)| \le n-2\), for any \(\pi \in S_n\), there exists at least two vertices in \(\bigcup\limits_{i=1}^nV_i^1\) to which any vertex of \(\overline{\Lambda^{\ast\ast}}_{K_n}\) is adjacent to. As this path is of length 3, and both internal vertices \(v_{\pi_1^\prime}v_{\pi_2^\prime}\) are colored with distinct colors, in any proper coloring of \(\overline{\Lambda^{\ast\ast}}_{K_n}\), \(\chi_{rd}(\overline{\Lambda^{\ast\ast}}_{K_n}) =\chi_{d}(\overline{\Lambda^{\ast\ast}}_{K_n})\).
Also, the idea of a vertex power dominating a color class reduces to the vertex dominating the color class in the graphs \(\Lambda^{\ast\ast}_{K_n}\) and \(\overline{\Lambda^{\ast\ast}}_{K_n}\), for \(n \ge 4\), as there is no vertex \(w \notin N[v]\) having a unique neighbour which is not a neighbour of \(v\), for any \(v\) in \(\Lambda^{\ast\ast}_{K_n}\) or \(\overline{\Lambda^{\ast\ast}}_{K_n}\). This is because, corresponding to every \(k\)-element fix, there are \(\rho(n-k)\) permutations and hence, \(\rho(n-k)\) vertices corresponding to the same \(k\)-element fix in the graphs \(\Lambda^{\ast\ast}_{K_n}\) and \(\overline{\Lambda^{\ast\ast}}_{K_n}\). The adjacencies and non-adjacencies between two vertices corresponding to any pair of permutations with distinct \(k\)-element fixes induce the same relation on all of the \(\rho(n-k)\) vertices; thereby yielding \(\chi_{pd}(\Lambda^{\ast\ast}_{K_n}) = \chi_{d}(\Lambda^{\ast\ast}_{K_n})\) and \(\chi_{pd}(\overline{\Lambda^{\ast\ast}}_{K_n}) =\chi_{d}(\overline{\Lambda^{\ast\ast}}_{K_n})\). ◻
A majority dominator coloring of a graph \(G\) is a proper vertex coloring of \(G\) in which each vertex of the graph dominates at least half of one color class and the majority dominator chromatic number of \(G\) is denoted by \(\chi_{md}(G)\).
Theorem 2.6. For any \(n \geq 4\),
(i) \(\chi_{md}(\Lambda^{\ast\ast}_{K_n}) = \chi(\Lambda^{\ast\ast}_{K_n})\).
(ii) \(\chi_{md}(\overline{\Lambda^{\ast\ast}}_{K_n}) = \chi(\overline{\Lambda^{\ast\ast}}_{K_n})\).
Proof. (i) Consider a \(\chi\)-coloring of \(\Lambda^{\ast\ast}_{K_n}\), where the colors \(c_i;\, 1 \le i \le (n-1)!-1\), are assigned to the vertices of \(V_1\), as it induces a clique in \(\Lambda^{\ast\ast}_{K_n}\). Following this, consider the vertices \(V_i – \bigl( \bigcup\limits_{j=1}^{i-1}V_j \bigr)\), for each \(2 \leq i \le n-2\), in order. Assign distinct colors to \(v_{\pi^{\prime}} \in V_i^1; \, 2 \le i \le n\), such that \(c(v_{\pi^{\prime}}) = c(v_{\pi})\), where \(v_{\pi} \in V^1_1\) and each of the remaining vertices of \(V^k_i; \, 2 \le i \le n\) and \(2 \le k \le n-2\), with distinct colors based on its previously colored vertices. In this coloring, \(\{v_{(1)(2)\ldots(n-2)}, v_{(n-1)(n)}\}\) is the least cardinality of a color class and every vertex of \(\Lambda^{\ast\ast}_{K_n}\) is adjacent to exactly one of these vertices. Hence, every vertex of \(\Lambda^{\ast\ast}_{K_n}\) dominates half of this color class and we obtain \(\chi_{md}(\Lambda^{\ast\ast}_{K_n}) = \chi(\Lambda^{\ast\ast}_{K_n}) = (n-1)!-1\).
(ii) Consider a chromatic coloring \(c\) of \(\overline{\Lambda}_{K_n}\), in which the color \(c_i\) is assigned to the vertices of \(V_i -\bigcup\limits_{j=1}^{i-1}V_j\), for each \(1 \le i \le n\). In this coloring, the number of vertices assigned the color \(c_i\) is \(\rho(n-1)+\sum\limits_{k=1}^{n-2}\binom{n-i}{k-i-1}\rho(n-k)\) and it decreases from \((n-1)!\) to \(\rho(n-1)\) as the value of \(i\) increases from \(1\) to \(n\). Also, in this coloring, every vertex \(v_{\pi} \in V(\overline{\Lambda}_{K_n})-V_n\) dominates the color class \(\{v_{\pi^\prime} : c(v_{\pi}) = c_n\}\). Hence, we must prove that every vertex in \(V_n\) dominates at least half of some color class, to prove the result. To prove this, it is enough to prove that a vertex \(v_{\pi_1} \in V^{n-2}_n – (V_{1} \cap V_2)\), dominates at least half of \(V_1\) or \(V_2\). Therefore, consider the vertex \(v_{\pi_1} \in V(\overline{\Lambda^{\ast\ast}}_{K_n})\), where \(\pi_1 = (3)(4)\ldots(n)\). This is adjacent to exactly \(\rho(n-1)+\rho(n-2)\) vertices of \(V_1\) and \(\rho(n-1)\) vertices of \(V_2\). As \(\rho(n-1)+\rho(n-2) \ge \frac{(n-1)!}{2}\), for all \(n\ge 3\), the vertex \(v_{\pi_1}\) is adjacent to more than half of the vertices of \(V_1\) and hence we obtain a majority dominator coloring of \(\overline{\Lambda}_{K_n}\) with \(n\) colors. ◻
Proposition 2.7. For \(n \geq 3\),
(i) \(\chi_{d}(\Lambda^\ast_{K_n}) = \chi_{td}(\Lambda^{\ast}_{K_n}) = \chi_{rd}(\Lambda^{\ast}_{K_n}) = \chi_{pd}(\Lambda^{\ast}_{K_n}) = \chi_{md}(\Lambda^{\ast}_{K_n}) = \chi(\Lambda^\ast_{K_n})\).
(ii) \(\chi_{dtd}(\Lambda^{\ast}_{K_n}) = (n-1)!+1\).
(iii) \(\chi_{d}(\Lambda_{K_n}) = \chi_{gd}(\Lambda_{K_n}) = \chi_{pd}(\Lambda_{K_n}) = \chi_{md}(\Lambda_{K_n}) = (n-1)!+\rho(n)\).
Proof. As \(\Lambda^\ast_{K_n}\) has a universal vertex \(v_{\pi_0}\), every vertex of \(\Lambda^\ast_{K_n}\) properly dominate a color class, with respect to any of its \(\chi\)-coloring and they also power dominate the color class \(\{v_{\pi_0}\}\). Owing to the existence of \(v_{\pi_0}\), any \(\chi\)-coloring of \(\Lambda^\ast_{K_n}\) is its rainbow dominator coloring, and the double total dominator coloring of \(\Lambda^\ast_{K_n}\) can ve viewed as the total dominator coloring of \(\Lambda^{\ast\ast}_{K_n}\), which implies that (ii) is immediate from Theorem 2.1.
As \(\Lambda_{K_n} = \Lambda^\ast_{K_n} \cup \rho(n)K_1\), in any variant of dominator coloring of \(\Lambda_{K_n}\) all these \(\rho(n)\) isolated vertices are assigned unique colors, for them to dominate their color class. Hence, we obtain the required values of the above mentioned variants of dominator chromatic numbers of the graphs \(\Lambda^{\ast}_{K_n}\) and \(\Lambda_{K_n}\). ◻
Proposition 2.8. For \(n \ge 3\),
(i) \(\chi_{d}(\overline{\Lambda^\ast}_{K_n}) = \chi_{gd}(\overline{\Lambda^\ast}_{K_n}) = \chi_{pd}(\overline{\Lambda^\ast}_{K_n}) = 2n-1\).
(ii) \(\chi_{md}(\overline{\Lambda^\ast}_{K_n}) = n+1\).
(iii) \(\chi_{d}({\overline\Lambda}_{K_n}) = \chi_{td}({\overline\Lambda}_{K_n}) = \chi_{dtd}({\overline\Lambda}_{K_n}) = \chi_{rd}({\overline\Lambda}_{K_n}) = \chi_{pd}({\overline\Lambda}_{K_n}) = \chi_{md}({\overline\Lambda}_{K_n}) = n+\rho(n)\).
Proof. The proofs of (i) and (ii) are immediate from the fact that the graph \(\overline{\Lambda^\ast}_{K_n} = \overline{\Lambda^{\ast\ast}}_{K_n} \cup v_{\pi_0}\), where \(v_{\pi_0}\) is an isolated vertex and hence in any variant of dominator coloring of \(\overline{\Lambda^\ast}_{K_n}\), the vertex \(v_{\pi_0}\) is given a unique color to dominate itself. Also, \({\overline\Lambda}_{K_n}\) is a graph with diameter 2, as there are \(\rho(n)\) universal vertices in it. Hence, in any proper coloring of \({\overline\Lambda}_{K_n}\), all these \(\rho(n)\) universal vertices are assigned distinct colors apart from the existing \(n\) colors that were used to color the vertices of \({\overline{\Lambda^{\ast\ast}}}_{K_n}\), and as \(\rho(n) \geq 2\), for all \(n \geq 3\), the result follows. ◻
A vertex \(v\) in a graph \(G\) is said to strongly dominate a set \(A \subseteq V(G)\) if \(v\) dominates \(A\) and \(deg(v) \geq deg(u)\), for all \(u \in A\). A strong dominator coloring of a graph \(G\) is a proper vertex coloring of \(G\) such that every vertex strongly dominates at least one color class and the strong dominator chromatic number of \(G\) is denoted by \(\chi_{sd}(G)\).
Theorem 2.9. For \(n \ge 4\),
(i) \(\chi_{sd}(\Lambda^{\ast\ast}_{K_n}) = (n-1)!+(n-2)\).
(ii) \(\chi_{sd}(\Lambda^{\ast}_{K_n}) = (n-1)!+(n-1)\).
(iii) \(\chi_{sd}(\Lambda_{K_n}) = (n-1)!+(n-1)+\rho(n)\).
Proof. From a \(\chi\)-coloring of \(\Lambda^{\ast\ast}_{K_n}\), we obtain a strong dominator coloring of \(\Lambda^{\ast\ast}_{K_n}\) by assigning a unique color \(c_{(n-1)!-1+i}; \, 1 \le i \le n\), which is not repeated anywhere to exactly one vertex of \(V_i^1;\) for each \(1 \le i \le n\), so that every vertex of the graph strongly dominates a color class. Hence, \(\chi_{sd}(\Lambda^{\ast\ast}_{K_n}) \le (n-1)!+(n-2)\).
In a strong dominator coloring of a graph, as every vertex has to dominate a color class where this color class must contain only the vertices having degree equal to or less than the degree of the vertex considered, the vertices of the least degree in \(\Lambda^{\ast\ast}_{K_n}\), which are in \(V_i^1\) must form a color class, so as to minimise the number of colors used in a strong dominator coloring of \(\Lambda^{\ast\ast}_{K_n}\). As \(\bigcup\limits_{i=1}^nV_i = nK_{\rho(n)}\), and if a vertex of \(V^1_i; \, 1 \le i \le n\), has to dominate a color class, all vertices of that color class must be in the corresponding \(V_i\), the vertices of the least degree forms \(n\) color classes, so that they are strongly dominated by all the other vertices. Assigning unique colors to \((n-1)\) \(V_i^1\)’s, makes the vertices in the \(n\)-th \(V_i^1\) automatically get a unique color, and therefore, \(\chi_{sd}(\Lambda^{\ast\ast}_{K_n}) \ge (n-1)!+(n-2)\).
As it is immediate that the strong dominator coloring of \(\Lambda^{\ast\ast}_{K_n}\) can be extended to \(\Lambda^{\ast}_{K_n}\), and \(\Lambda_{K_n}\) by assigning a unique colors to the vertex \(v_{\pi_0}\), and to the isolated vertices in \(\Lambda_{K_n}\), the result follows. ◻
Theorem 2.10. For \(n \ge 4\),
(i) \[\chi_{sd}(\overline{\Lambda^{\ast\ast}}_{K_n}) = \begin{cases} n +\binom{n}{\frac{n}{2}}+\sum\limits_{k=\lfloor \frac{n}{2}\rfloor+1}^{n-2}\binom{n}{k}\rho(n-k), & \mbox{when $n$ is even};\\ n +\sum\limits_{k=\lfloor \frac{n}{2}\rfloor+1}^{n-2}\binom{n}{k}\rho(n-k), & \mbox{when $n$ is odd}. \end{cases}\] .
(ii) \(\chi_{sd}(\overline{\Lambda^{\ast}}_{K_n}) = \chi_{sd}(\overline{\Lambda^{\ast\ast}}_{K_n})+1\).
(iii) \(\chi_{sd}(\overline{\Lambda}_{K_n}) = \chi_{sd}(\overline{\Lambda^{\ast}}_{K_n})+\rho(n).\)
Proof. In \(\overline{\Lambda^{\ast\ast}}_{K_n}\), every vertex of \(\bigcup\limits_{i=1}^{n}V_i^k; \, \lfloor \frac{n}{2}\rfloor+1 \le k \le n-2\), is adjacent to only the vertices of degree higher than theirs. Therefore, in any strong dominator coloring of \(\overline{\Lambda^{\ast\ast}}_{K_n}\), all these vertices must be assigned unique colors. Every vertex of \(\bigcup\limits_{i=1}^{n}V_i^k; \, 1 \le k \le \lceil \frac{n}{2}\rceil-1\), is adjacent to at least one of the vertices of \(\bigcup\limits_{i=1}^{n}V_i^k; \, \lfloor \frac{n}{2}\rfloor+1 \le k \le n-2\), which are uniquely colored and hence, all the vertices of \(\bigcup\limits_{i=1}^{n}V_i^k; \, 1 \le k \le \lceil \frac{n}{2}\rceil-1\), strongly dominate at least one color class. Therefore, these vertices in \(\bigcup\limits_{i=1}^{n}V_i^k; \, 1 \le k \le \lceil \frac{n}{2}\rceil-1\), are properly colored using \(n\) colors, apart from the ones assigned to the vertices of \(\bigcup\limits_{i=1}^{n} \bigcup\limits_{k=1}^{\lfloor \frac{n}{2}\rfloor+1}V_i^k\). If \(n\) is odd, we are done.
If \(n\) is even, the vertices of \(\bigcup\limits_{i=1}^{n}V_i^{\frac{n}{2}}\) remains to be colored, at this point. Each vertex \(v_{\pi} \in \bigcup\limits_{i=1}^{n}V_i^{\frac{n}{2}}\) is adjacent to \(\rho(\frac{n}{2})\) vertices of \(\bigcup\limits_{i=1}^{n}V_i^{\frac{n}{2}}\), which are of the same degree and to the vertices in \(\bigcup\limits_{i=1}^{n}V_i^k; \, 1 \le k \le \frac{n}{2}-1\), which have degree higher than that of \(v_{\pi}\). The subgraph of \(\overline{\Lambda^{\ast\ast}}_{K_n}\) induced by \(\bigcup\limits_{i=1}^{n}V_i^{\frac{n}{2}}\) is \(\binom{n}{\frac{n}{2}}K_{\rho(\frac{n}{2}), \rho(\frac{n}{2})}\), where \(\rho(\frac{n}{2})\) vertices correspond to permutations having a particular \(\frac{n}{2}\)-element fix. Therefore, for every vertex \(v_{\pi} \in \bigcup\limits_{i=1}^{n}V_i^{\frac{n}{2}}\) to strongly dominate a color class, unique colors must be assigned to at least one of these \(\rho(\frac{n}{2})\) vertices that correspond to permutations with a distinct \(\frac{n}{2}\)-element fix. Hence, \(\chi_{sd}(\overline{\Lambda^{\ast\ast}}_{K_n}) = n +\binom{n}{\frac{n}{2}}+\sum\limits_{k=\lfloor \frac{n}{2}\rfloor+1}^{n-2}\binom{n}{k}\rho(n-k)\), when \(n\) is even.
Using a similar arguments in Theorem 2.9, the above mentioned \(\chi_{sd}\)-coloring of \(\overline{\Lambda^{\ast\ast}}_{K_n}\) can be extended as the \(\chi_{sd}\)-coloring of \(\overline{\Lambda^{\ast}}_{K_n}\), and \(\overline{\Lambda}_{K_n}\), by giving unique colors to \(v_{\pi_0}\), and the \(\rho(n)\) universal vertices of \(\overline{\Lambda}_{K_n}\); completing the proof. ◻
A subset \(S \subseteq V(G)\) in a graph \(G\) is called semi-strong if \(|N(v) \cap S| \le 1\), for all \(v \in V(G)\). Partitioning \(V(G)\) into semi-strong subsets is called a semi-strong coloring of \(G\) and a dominator semi-strong color partition of \(G\) is a semi-strong coloring of \(G\) in which every vertex \(v \in V(G)\) dominates at least one color class. The minimum order of such a partition is called the dominator semi-strong color partition number of \(G\), denoted by \(\chi_{ssd}(G)\).
Proposition 2.11. For \(n \in \mathbb{N}\),
(i) \(\chi_{ssd}(\Lambda^{\ast\ast}_{K_n}) = \chi_{ssd}(\overline{\Lambda^{\ast\ast}}_{K_n}) = n! – \rho(n)-1\).
(ii) \(\chi_{ssd}(\Lambda^{\ast}_{K_n}) = \chi_{ssd}(\overline{\Lambda^{\ast}}_{K_n}) = n!-\rho(n)\).
(iii) \(\chi_{ssd}(\overline{\Lambda}_{K_n}) =\chi_{ssd}(\Lambda_{K_n}) = n!\).
Proof. Assigning unique colors to each vertex of any graph is trivially a semi-strong dominator coloring of the graph. Conversely, we claim that any semi-strong subset of \(V(\Lambda^{\ast\ast}_{K_n})\) as well as \(V(\overline{\Lambda^{\ast\ast}}_{K_n})\), is a singleton. If possible, let \(S^\prime =\{v_{\pi_1}, v_{\pi_2} : \mathop{\mathrm{fix}}(\pi_1) \cap \mathop{\mathrm{fix}}(\pi_2) \ne \emptyset\}\) be a semi-strong subset of \(V(\Lambda^{\ast\ast}_{K_n})\). Clearly, here \(\mathop{\mathrm{fix}}(\pi_1) \ne \mathop{\mathrm{fix}}(\pi_2)\) because, if \(\mathop{\mathrm{fix}}(\pi_1) = \mathop{\mathrm{fix}}(\pi_2)\), we get \(N(v_{\pi_1}) = N(v_{\pi_2}) \ne \emptyset\). Therefore, assume \(\mathop{\mathrm{fix}}(\pi_1) \subset \mathop{\mathrm{fix}}(\pi_2)\) and hence \(|\mathop{\mathrm{fix}}(\pi_2)| \ge 2\). As there exists \(\rho(n-|\mathop{\mathrm{fix}}(\pi_1)|)-1\) vertices of the graph \(\Lambda^{\ast\ast}_{K_n}\) corresponding to permutations having the same fix as \(\mathop{\mathrm{fix}}(\pi_1)\) and all of them will be adjacent to both the vertices of \(S^\prime\), it yields a contradiction.
Consider a subset \(S^\ast = \{v_{\pi_1}, v_{\pi_2} : \mathop{\mathrm{fix}}(\pi_1) \cap \mathop{\mathrm{fix}}(\pi_2) = \emptyset\}\) of \(V({\Lambda}^{\ast\ast}_{K_n})\). In \({\Lambda}^{\ast\ast}_{K_n}\), as there exists at least one vertex \(v_{\pi_3}\) such that \(\mathop{\mathrm{fix}}(\pi_3) \cap \mathop{\mathrm{fix}}(\pi_1) \ne \emptyset\) and \(\mathop{\mathrm{fix}}(\pi_3) \cap \mathop{\mathrm{fix}}(\pi_2) \ne \emptyset\), owing to the closure property of \(S_n\); \(S^\ast\) cannot be semi-strong. Therefore, any semi-strong subset of \(V(\Lambda^{\ast\ast}_{K_n})\) is a singleton and \(\chi_{ssd}(\Lambda^{\ast\ast}_{K_n}) = n! – \rho(n)-1\). Using the same argument, as we can prove that any semi-strong subset of \(V(\overline{\Lambda^{\ast\ast}}_{K_n})\) is also a singleton, (i) follows.
Both the graphs \(\Lambda^{\ast}_{K_n}\) and \(\overline{\Lambda}_{K_n}\) have universal vertices, and hence this leads to the assignment of unique colors to all vertices of these graphs to abide by the dominator semi-strong coloring protocol of graphs. Also, as every isolated vertex of any graph is assigned a unique color in any dominator coloring, and as \(\overline{\Lambda}_{K_n} \cong \Lambda^\ast_{K_n} \cup \rho(n)K_1\) and \(\overline{\Lambda^\ast}_{K_n} \cong \overline{\Lambda^{\ast\ast}}_{K_n} \cup v_{\pi_0}\), the result is immediate. ◻
A proper coloring of a graph \(G\) in which the cardinalities of the color classes differ by at most one is called an equitable coloring of \(G\) and the equitable chromatic number of \(G\) is denoted by \(\chi_{e}(G)\). An equitable coloring of \(G\) in which every vertex \(v \in V(G)\) dominates at least one color class is called an equitable dominator coloring of \(G\) and the equitable dominator chromatic number of \(G\) is denoted by \(\chi_{ed}(G)\) (see [2,3]). As the equitable dominator coloring of graphs is closely related to their equitable coloring, we use the following result obtained in [8].
Theorem 2.12. [8] The equitable chromatic numbers of the graphs \(\Lambda^\ast_{K_n}\) and \(\overline{\Lambda}_{K_n}\) are \(\lceil \frac{n!-\rho(n)-1}{2}\rceil+1\) and \(\lceil \frac{n!-\rho(n)}{2}\rceil+\rho(n)\), respectively.
Theorem 2.13. For \(n \in \mathbb{N}\),
(i) \(\chi_{ed}(\Lambda^{\ast\ast}_{K_n}) = \lceil \frac{n!-\rho(n)-3}{2}\rceil+2\).
(ii) \(\chi_{ed}(\Lambda^{\ast}_{K_n}) = \chi_{e}(\Lambda^{\ast}_{K_n})\).
(iii) \(\chi_{ed}(\Lambda_{K_n}) = \chi_{ed}(\Lambda^{\ast}_{K_n}) + \rho(n)\).
Proof. In any \(\chi_{d}\)-coloring \(c\) of \(\Lambda^{\ast\ast}_{K_n}\), we know that there are at least two singleton color classes (see Theorem 2.1). Therefore, in any equitable dominator coloring of \(\Lambda^{\ast\ast}_{K_n}\), the color classes must have cardinality either 1 or 2. To reduce the number of colors, we minimise the number of color classes that are singletons by assigning unique colors to the vertices \(v_{\pi},v_{\pi^\prime} \in V(\Lambda^{\ast\ast}_{K_n})\), where \(|\mathop{\mathrm{fix}}(\pi) \cup \mathop{\mathrm{fix}}(\pi^\prime)| = n\) and \(\mathop{\mathrm{fix}}(\pi) \cap \mathop{\mathrm{fix}}(\pi^\prime) = \emptyset\). Therefore, the remaining \(n! – \rho(n)-3\) vertices of \(\Lambda^{\ast\ast}_{K_n}\) are partitioned into independent sets of cardinality 2. This partition can be viewed as the equitable coloring of \(\Lambda^{\ast}_{K_n}\) given in the proof of Theorem 2.12 (ref. [8]), just by removing the vertices \(v_\pi, v_{\pi^\prime}\) and \(v_{\pi_0}\). Hence, \(\chi_{ed}(\Lambda^{\ast\ast}_{K_n}) = \lceil \frac{n!-\rho(n)-3}{2}\rceil+2\).
In any proper coloring of \(\Lambda^{\ast}_{K_n}\), the vertex \(v_{\pi_0}\) is assigned a unique color, where any vertex dominates this color class. Also, as the remaining vertices are partitioned equitably in any equitable coloring of \(\Lambda^{\ast}_{K_n}\), any \(\chi_e\)-coloring of \(\Lambda^{\ast}_{K_n}\) becomes an equitable dominator coloring of \(\Lambda^{\ast}_{K_n}\). The same equitable dominator coloring of \(\Lambda^{\ast}_{K_n}\) when extended to the graph \(\Lambda_{K_n}\), where the \(\rho(n)\) universal vertices are assigned distinct colors to dominate themselves becomes an equitable dominator coloring of \(\Lambda_{K_n}\). The minimality of these parameters are also ensured by the minimality of \(\chi_{e}(\Lambda^{\ast}_{K_n})\); thereby yielding the required result. ◻
Theorem 2.14. For \(n \in \mathbb{N}\),
(i) \(\chi_{ed}(\overline{\Lambda^{\ast}}_{K_n}) =\lceil \frac{n!-\rho(n)-1}{2}\rceil+1\).
(ii) \(\chi_{ed}(\overline{\Lambda}_{K_n}) = \chi_{e}(\overline{\Lambda}_{K_n})\).
Proof. The graph \(\overline{\Lambda}_{K_n}\) has \(\rho(n)\) universal vertices and hence any \(\chi_e\)-coloring of \(\overline{\Lambda}_{K_n}\) is its \(\chi_{ed}\)-coloring. As the graph \(\overline{\Lambda^{\ast}}_{K_n}\) has exactly one isolated vertex \(v_{\pi_0}\), a unique color is assigned to it in any dominator coloring of \(\overline{\Lambda^{\ast}}_{K_n}\). Therefore, in any equitable dominator coloring of \(\overline{\Lambda^{\ast}}_{K_n}\), each color class must have either one or two vertices. That is, the remaining \(n!-\rho(n)-1\) vertices of \(\overline{\Lambda^{\ast}}_{K_n}\) are partitioned into independent sets of cardinality 1 or 2, in any equitable dominator coloring of \(\overline{\Lambda^{\ast}}_{K_n}\). As the same kind of partitioning of \(V(\overline{\Lambda}_{K_n})\) is obtained to determine its equitable coloring pattern in Theorem 2.12, we determine the \(\chi_{ed}\)-coloring of \(\overline{\Lambda^{\ast}}_{K_n}\) based on the \(\chi_{e}\)-coloring of \(\overline{\Lambda}_{K_n}\) given in the proof of Theorem 2.12 in [8].
Consider the equitable chromatic partition of \(V(\overline{\Lambda}_{K_n})\) without the the \(\rho(n)\) universal vertices and make \(v_{\pi_0}\) a singleton. Then, the other vertex which was assigned the same color as \(v_{\pi_0}\) in the \(\chi_e\)-coloring of \(V(\overline{\Lambda}_{K_n})\), either remains a singleton or it can be given the same color as some other vertex, which is a singleton in the \(\chi_e\)-coloring of \(\overline{\Lambda}_{K_n}\) (For more details, see [8]). This is possible because \(S_n\) is a group, and there always exists at least one unique \(k\)-element fix which is disjoint with the any given \(k^\prime\)-element fix, where \(1 \le k \le k^\prime \le n-2\). This gives an optimal equitable dominator coloring of \(\overline{\Lambda^\ast}_{K_n}\), as there are at most two singletons, which cannot be paired with any other vertex of \(\overline{\Lambda}_{K_n}\). ◻
Based on the structure of \(\overline{\Lambda^{\ast\ast}}_{K_n}\), it can be seen that its dominator coloring pattern is according to the assignment of colors to the \(\rho(n-1)\) vertices in each \(V_i^1; \, 1 \le i \le n\). As there does not exist a generalisable pattern for \(\rho(i)\), owing to its dependency on the integer partitioning, which by itself is an unsolved problem (For details, refer to [1]), determining an equitable partition of these values is highly challenging. In view of this, determining \(\chi_{ed}({\overline{\Lambda^{\ast\ast}}_{K_n}})\) becomes highly arduous and therefore, remains an open problem, at this point of study.
| S.No. | Ch. No. | \(\Lambda_{K_{n}}\) | \(\Lambda^\ast_{K_{n}}\) | \(\Lambda^\ast \ast_{K_{n}}\) | \(\overline{\Lambda}_{K_{n}}\) | \(\overline{\Lambda^\ast}_{K_{n}}\) | \(\overline{\Lambda^{\ast \ast}}_{K_{n}}\) |
| 1 | \(\chi_d\) | \((n-1)!\) \(+\rho(n)\) | \((n-1)!\) | \((n-1)!\) | \(n+\rho(n)\) | \(2n-1\) | \(2(n-1)\) |
|
2 |
\(\chi_td\) | Cannot Admit | \((n-1)!\) | \((n-1)!+1\) | \(n+\rho(n)\) | Cannot Admit | \(2(n-1)\) |
|
3 |
\(\chi_dtd\) | Cannot Admit | \((n-1)!+1\) | \((n-1)!+2\) | \(n+\rho(n)\) | Cannot Admit | \(2n-1\) |
|
4 |
\(\chi_gd\) | \((n-1)!\) \(+\rho(n)\) | Cannot Admit | \((n-1)!+(n-3)\) | Cannot Admit | \(2n-1\) | \(2n\) |
|
5 |
\(\chi_tgd\) | Cannot Admit | Cannot Admit | \((n-1)!+(n-2)\) | Cannot Admit | Cannot Admit | \(2n\) |
|
6 |
\(\chi_rd\) | Not Defined | \((n-1)!\) | \((n-1)!\) | \(n+\rho(n)\) | Not Defined | \(2(n-1)\) |
|
7 |
\(\chi_pd\) | \((n-1)!\) \(+\rho(n)\) | \((n-1)!\) | \((n-1)!\) | \(n+\rho(n)\) | \(n+1\) | \(2(n-1)\) |
|
8 |
\(\chi_md\) | \((n-1)!\) \(+\rho(n)\) | \((n-1)!\) | \((n-1)!-1\) | \(n+\rho(n)\) | \(n+1\) | \(n\) |
|
9 |
\(\chi_sd\) | \((n-1)!+\) \((n-1)\) \(+\rho(n)\) | \((n-1)!\) \(+(n-1)\) | \((n-1)!\) \(+(n-2)\) | \(1+\rho(n)+n +\binom{n}{\frac{n}{2}}+\sum\limits_{k=\lceil\frac{n}{2}\rceil}^{n-2}\binom{n}{k}\rho(n-k)\) | \(1+n +\binom{n}{\frac{n}{2}}+\sum\limits_{k=\lceil\frac{n}{2}\rceil}^{n-2}\binom{n}{k}\rho(n-k)\) | \(n +\binom{n}{\frac{n}{2}}+\sum\limits_{k=\lceil\frac{n}{2}\rceil}^{n-2}\binom{n}{k}\rho(n-k)\) |
|
10 |
\(\chi_ssd\) | \(n!-\rho(n)\) | \(n!-\rho(n)\) | \(n!-\rho(n)-1\) | \(n!\) | \(n!-\rho(n)-1\) | \(n!-\rho(n)-1\) |
|
11 |
\(\chi_ed\) | \(\lceil \frac{n!-\rho(n)-1}{2}\rceil\) \(+\rho(n)+1\) | \(\lceil \frac{n!-\rho(n)-1}{2}\rceil\) \(+1\) | \(\lceil \frac{n!-\rho(n)-3}{2}\rceil\) \(+2\) | \(\lceil \frac{n!-\rho(n)}{2}\rceil\) \(+\rho(n)\) | \(\lceil \frac{n!-\rho(n)-1}{2}\rceil+1\) | \(2(n-1)\le \chi_{ed}(\overline{\Lambda^{\ast\ast}}_{K_n}) \le\) \(\lceil \frac{n!-\rho(n)-n\rho(n-1)}{\rho(n-1)}\rceil\)}+\(n\) |
In this article, we have exclusively investigated different dominator coloring schemes for the \(n\)-inordinate invariant intersection graphs and their derived graphs; a summary of which is given in Table 1. We have obtained the coloring patterns and determined the graph invariant associated with each of the dominator coloring considered. As this investigation gives rise to six structures associated with the \(n\)-inordinate invariant intersection graphs, it yields a vast scope for future study; which includes the investigation of other coloring and domination-related parameters, the spectral properties, algebraic properties, etc. of these graphs.