Dominator colorings of n-inordinate invariant intersection graphs

S. Madhumitha1, S. Naduvath1
1Department of Mathematics Christ University, Bangalore, India

Abstract

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.

Keywords: invariant intersection graphs, n-inordinate invariant intersection graphs, coloring, domination, dominator colorings

1. Introduction

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 χ(G), and any coloring of V(G) with χ colors is called a χ-coloring of G. In a graph G, if a vertex vV(G) is adjacent to all vertices uA, for some AV(G) or A={v}, we say that v dominates A and A is dominated by v. In this context, if vA, 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 ΛKn, was identified in [12] as the graph with V(ΛKn)Sn and any two distinct vertices vπ,vπV(ΛKn) corresponding to the permutations π, πSn are adjacent in ΛKn when fix(π)fix(π), where Sn is the symmetric group, and for any πSn, fix(π) is the set {xS:π(x)=x}.

An illustration of n-inordinate invariant intersection graphs is given in Figure 1. Note that the identity permutation is denoted by π0 and the vertex corresponding to a permutation πSn is denoted by vπV(ΛKn), throughout the study.

Figure 1 The 4-inordinate invariant intersection graph

In [12], the structural properties of the n-inordinate invariant intersection graphs ΛKn and their complements, n-inordinate invariant non-intersection graphs, denoted by Λ¯Kn, were investigated and it was found that ΛKnΛKnρ(n)K1, where ρ(i); iN, is the number of derangements of i elements and ΛKn is the non-trivial component of ΛKn with diameter 2, having n!ρ(n) vertices.

Following the study in [12], different proper vertex colorings of the graphs ΛKn and Λ¯Kn 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 ΛKn has isolated vertices and ΛKn 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 Λ¯Kn, and Λ¯Kn, respectively. Hence, our primary focus of study is on the coloring patterns of the connected graphs ΛKnvπ0, for n4, and Λ¯Knvπ0, for n3, denoted by ΛKn and Λ¯Kn, respectively.

Note that ω(ΛKn)=χ(ΛKn)=(n1)!1 and ω(Λ¯Kn)=χ(Λ¯Kn)=n, as it has been proven in [12] that ω(ΛKn)=χ(ΛKn)=(n1)! and ω(Λ¯Kn)=χ(Λ¯Kn)=n+ρ(n);n3. 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.

2. Variants of dominator colorings of n-inordinate invariant intersection graphs

In this section, we examine the variants of dominator colorings of the graphs ΛKn, ΛKn, ΛKn Λ¯Kn, Λ¯Kn,and Λ¯Kn, and for this, we use the notations Vi={vπ:ifix(π)}; for 1in, and Vik={vπVi:|fix(π)|=k};1in; 1kn2, 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 χ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 χtd(G) (resp. χdtd(G)).

Theorem 2.1. For n4,

(i) χd(ΛKn)=χtd(ΛKn)=(n1)!.

(ii) χdtd(ΛKn)=(n1)!+1.

Proof. (i) In ΛKn, the vertices of Vi1, for any 1in, are adjacent only to the vertices in the corresponding Vi. Hence, in any dominator coloring of ΛKn, these vertices can dominate a color class if and only if a color is assigned exclusively for the vertices in that Vi. As each Vi;1in, induces a clique in ΛKn, such exclusive color can be given to exactly one vertex and in any χ-coloring of ΛKn, this cannot be an exclusive color. Hence, χd(ΛKn)(n1)!.

As it can be seen that for any two vertices vπ,vπV(ΛKn) with fix(π)fix(π), N(vπ)N(vπ), where N(vπ)={vπV(ΛKn):vπvπE(ΛKn)}, for any vπV(ΛKn), we get the required dominator coloring pattern by validating if all the vertices of Vi1;1in, dominate the required number of color classes.

Define a coloring c:V(ΛKn){c1,c2,,c(n1)!} as follows. As ω(ΛKn)=χ(ΛKn)=(n1)!1, first assign the colors c1,c2,,c(n1)!1 to the vertices of V1 such that c(vπ1)=c1, c(vπ2)=c2, c(vπ3)=c3, where π1,π2,π3Sn have fix(π1)=(1)(2)(n2), fix(π2)=(1)(2) and fix(π3)=(1)(2)(n3)(n). Following this, color the vertices vπVij=1i1Vj, for each 2in, in order, where the vertices of each Vi; 2in, are colored with (n1)!1 colors based on the previously colored vertices in the cliques Vj;1ji1, such that c(vπ4)=c1, c(vπ5)=c2, and c(vπ6)=c3, where π4,π5,π6Sn have fix(π4)=(n1)(n), fix(π5)=(2)(3)(n1) and fix(π6)=(n2)(n1).

The existence of the above mentioned χ-coloring c of ΛKn is guaranteed, as the color assigned to any vertex vπVin2 is assigned either exactly to one other vertex in Vi12Vi22, or at most two vertices; that is, one from Vi11 and Vi21, where 1ii1i2n, and i1,i2fix(π), in any χ-coloring of ΛKn. This is owing to the structure of the graph that demands each color class to contain exactly one vertex from each Vi;1in and if any color is assigned to vπVin2 with i1,i2fix(π) and to a vertex of Vi11 and Vi21, we swap one of the ρ(n2) colors assigned to the vertices in Vi12Vi22 to these two vertices, as it does not alter any of the properties of the considered χ-coloring of ΛKn.
Now, in order to make this χ-coloring c, a dominator coloring of ΛKn, we assign c(vπ4)=c(n1)!, which makes all the vertices in i=1n2Vi dominate the color class {vπ1} and the vertices in i=n1nVi dominate the color class {vπ4}. Also, as it can be seen that all the vertices in V(ΛKn){vπ1,vπ4} properly dominate either the color class {vπ1} or {vπ3}, the vertex vπ1 properly dominates the color class {vπ2,vπ5}, and the vertex vπ4 properly dominates the color class {vπ3,vπ6}, in this dominator coloring c of ΛKn with (n1)! colors, we have χd(ΛKn)=χtd(ΛKn)=(n1)!.

(ii) In the dominator coloring c of ΛKn mentioned above, no vertex in Vi1 dominates two color classes and using the similar arguments mentioned in (i), it can be deduced that χdtd(ΛKn)(n1)!+1. From the dominator coloring c of ΛKn, we obtain a double total dominator coloring c of ΛKn by assigning c(vπ5)=c(n1)!+1, which makes every vertex of the graph properly dominate at least two color classes; thereby completing the proof. ◻

Theorem 2.2. For n4,

(i) χd(Λ¯Kn)=χtd(Λ¯Kn)=2(n1).

(ii) χdtd(Λ¯Kn)=2n1.

Proof. Consider the coloring c:V(Λ¯Kn){cs:1s2(n1)} such that for any vertex vπV(Λ¯Kn), c(vπ)={ci,vπVi1,1in;cn1,vπVn12Vn2;cn+i,vπi=1n2k=2n2Vikj=1i1Vjk.

It is a dominator coloring of Λ¯Kn as every vertex that corresponds to a permutation fixing k-elements dominates at least nk1 color classes with respect to this coloring c of Λ¯Kn. Hence, χd(Λ¯Kn)2(n1).

In Λ¯Kn, a vertex vπVi;1in, dominates a color class if and only if none of the vertices in that color class are in the same Vi. Consider a vertex vπVin2, for some 1in, such that t1,t2fix(π), where 1t1t2n. Therefore, this vertex vπ can dominate a color class if and only if all vertices of the color class are from (Vt12Vt22)Vt11Vt21. As there are (n2) possible pairs of such t1 and t2, we must obtain a color class that is exclusive to each Vi;1in, except one, for any such vπVin2 to dominate a color class. All (n1)! vertices of exactly one Vi;1in, can be colored with the same color because for every vπVin2 there are two Vj’s; 1ijn, such that they are adjacent to all the vertices of these Vj’s, and one among them can be chosen to have an exclusive color class. Also, as the Vi’s are non-disjoint, if colors are assigned to the vertices from each Vi, in the end, for some 1jin, Viij=1nVj=Vi1. Hence, we require at least 2n2 colors to obtain a dominator coloring of Λ¯Kn. Therefore, χd(Λ¯Kn)=2(n1). This dominator coloring c of Λ¯Kn is also its total dominator coloring as every vertex in Vi properly dominates a color class assigned the color ci, 1iin, and hence, it follows that χtd(Λ¯Kn)=2(n1).

In any χd-coloring of Λ¯Kn, it can be seen that every vertex vπ properly dominates at least nk1 color classes, where k=|fix(π)| and all but one vertex in i=1nVin2 properly dominate at least two color classes. Therefore, it can be deduced that in an optimal double total dominator coloring, all Vi1;1in, have to be assigned unique colors and hence χdtd(Λ¯Kn)=2n1◻

Corollary 2.3. For n4,

(i) χdtd(ΛKn)=χd(ΛKn)+1.

(ii) χdtd(Λ¯Kn)=χd(Λ¯Kn)+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 vV(G) is said to anti-dominate a set AV(G) if uvE(G), for all uA, such that vA. The global dominator chromatic number (resp. total global dominator chromatic number) of G is denoted by χgd(G) (resp. χtgd(G)).

Theorem 2.4. For n4,

(i) χgd(ΛKn)=(n1)!+(n3).

(ii) χtgd(ΛKn)=(n1)!+(n2).

(iii) χgd(Λ¯Kn)=χtgd(Λ¯Kn)=2n.

Proof. (i) Any vertex vπVin2 is not adjacent to 2ρ(n1) vertices of Vi1 and ρ(n2) vertices of Vi2, such that 1iin and ifix(π), in ΛKn. Therefore, if a vertex vπVin2 has to anti-dominate any color class with respect to some proper coloring of ΛKn, such a color class must contain only the vertices of Vi11Vi21(Vi12Vi22), where 1i1i2n, and i1,i2fix(π). As there are (n2) possible pairs of such i1 and i2, we must obtain a color class that is exclusive to each Vi;1in, except one, for any such vπVin2 to anti-dominate a color class. Hence, χgd(ΛKn)χ(ΛKn)+(n2).

There exists a χ-coloring of ΛKn, say c, in which some color ct;1t(n1)!1, is assigned to n vertices of Vi1; that is, one from each Vi1, as every color class in any χ-coloring of ΛKn must contain one vertex from each Vi;1in, and let vπiVi1;1in, be n vertices such that for all 1in, c(vπi)=ct, for some 1t(n1)!1. The existence the coloring c is guaranteed owing to the nature of the color classes in any χ-coloring of ΛKn and the fact that Vi’s are non-disjoint.

We make such a χ-coloring c of ΛKn, a global dominator coloring of ΛKn, by assigning the color c(n1)!1+i to the vertex vπiVi1;1in2. Now, only one vertex in Vn11 and one vertex in Vn1 have the color ct, and as mentioned in Theorem 2.1, we swap the color of the vertices vπn1 and vπn with the color of a vertex, say vπ, in Vn12Vn2. Here, every vertex in Vi;1in2, dominates the color class {vπi} and the vertices of Vn1Vn dominate the color class {vπ}. Also, any vertex vπV(ΛKn){v(1)(2)(n2)} anti-dominates the color class {vπi}, 1in such that ifix(π) and the vertex v(1)(2)(n2) anti-dominates the color class {vπ}; thereby, yielding χgd(ΛKn)=(n1)!+n3.

(ii) In the above mentioned global dominator coloring c of ΛKn, all the vertices of V(ΛKn), except the ones in Vi1 assigned the colors c(n1)!1+i, for 1in2, and the vertex vπ, does not properly dominate any color class. Therefore, it can be seen from (i) that we require at least χgd(ΛKn)+1 colors, in any total global dominator coloring of ΛKn.

To obtain a total global dominator coloring of ΛKn with χgd(ΛKn)+1 colors, consider the coloring c defined above and assign the color c(n1)!+n2 to the vertex v(1)(2)(n2), which makes the vertices vπi;1in2, dominate the color class {v(1)(2)(n2)}. As mentioned in Theorem 2.1, any color, say cr, for some 1r(n1)!1 and rt, assigned to the vertex v(1)(2)(n2) is assigned either exactly to one other vertex of the form v(n1)(n) or at most two vertices of the form v(n1) and v(n), in any proper coloring of ΛKn. Hence, as the vertex v(1)(2)(n2) is assigned a new color by c, the vertex now vπ properly dominates the color class of the color cr which was earlier assigned to the vertex v(1)(2)(n2). Therefore, we obtain an optimal total global dominator coloring of ΛKn with (n1)!+(n2) colors.

(iii) By Theorem 2.2, it can be seen that in any χd-coloring of Λ¯Kn, any vertex vπ anti-dominates at most k1 color classes, where k=|fix(π)|. Therefore, we require additional colors for the vertices Vi1;1in, to anti-dominate some color class. For any vertex in Vi1;1in, 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 Vi. Therefore, to minimise the number of such additional colors, we assign the color c2n1 to the vertex vπ, such that |fix(π)|=n2. If t1,t2fix(π), then the vertices of Vt11 and Vt21; for some 1t1t2n, still do not anti-dominate any color class. Hence, a vertex vπ such that {t1,t2}fix(π), is assigned the color c2n to obtain a global dominator coloring of Λ¯Kn with 2n colors. Note that the above mentioned coloring is also a total global dominator coloring of Λ¯Kn, as every vertex of the graph properly dominates a color class. Also, as the minimality of the parameter follows from the structure of Λ¯Kn and the global dominator coloring protocol, χgd(Λ¯Kn)=χtgd(Λ¯Kn)=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,vV(G), there exists a uv path in which no two internal vertices have the same color and the rainbow dominator chromatic number of G is denoted by χ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 χpd(G). A vertex vV(G) is said to power dominate the vertices in M(v)V(G), which is constructed as follows.

(i) M(v)=N[v].

(ii) Consider a vertex wM(v) and add it to M(v) if there exists a uN(w)M(v) such that all v1N(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 n4,

(i) χrd(ΛKn)=χpd(ΛKn)=χd(ΛKn).

(ii) χrd(Λ¯Kn)=χpd(Λ¯Kn)=χd(Λ¯Kn).

Proof. As the graph ΛKn has diameter 2, all uv path of length 2 between any two vertices of ΛKn, whose only internal vertex has a distinct color. Hence, χrd(ΛKn)=χd(ΛKn). In Λ¯Kn, any two non-adjacent vertices vπ1 and vπ2 correspond to permutations such that fix(π)fix(π1). Here, if 1|fix(π1)fix(π2)|n2, then there is a path of length 2 between the vertices vπ1 and vπ2 in Λ¯Kn and its internal vertex is uniquely colored, in any proper coloring of Λ¯Kn. If |fix(π1)fix(π2)|=n, then the non-adjacent vertices do not have a common neighbour and we have a path vπ1vπ1vπ2vπ2, where vπ1Vi1 and vπ2Vi1, where 1iin, such that ifix(π1) and ifix(π2). As |fix(π)|n2, for any πSn, there exists at least two vertices in i=1nVi1 to which any vertex of Λ¯Kn is adjacent to. As this path is of length 3, and both internal vertices vπ1vπ2 are colored with distinct colors, in any proper coloring of Λ¯Kn, χrd(Λ¯Kn)=χd(Λ¯Kn).

Also, the idea of a vertex power dominating a color class reduces to the vertex dominating the color class in the graphs ΛKn and Λ¯Kn, for n4, as there is no vertex wN[v] having a unique neighbour which is not a neighbour of v, for any v in ΛKn or Λ¯Kn. This is because, corresponding to every k-element fix, there are ρ(nk) permutations and hence, ρ(nk) vertices corresponding to the same k-element fix in the graphs ΛKn and Λ¯Kn. 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 ρ(nk) vertices; thereby yielding χpd(ΛKn)=χd(ΛKn) and χpd(Λ¯Kn)=χd(Λ¯Kn)◻

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 χmd(G).

Theorem 2.6. For any n4,

(i) χmd(ΛKn)=χ(ΛKn).

(ii) χmd(Λ¯Kn)=χ(Λ¯Kn).

Proof. (i) Consider a χ-coloring of ΛKn, where the colors ci;1i(n1)!1, are assigned to the vertices of V1, as it induces a clique in ΛKn. Following this, consider the vertices Vi(j=1i1Vj), for each 2in2, in order. Assign distinct colors to vπVi1;2in, such that c(vπ)=c(vπ), where vπV11 and each of the remaining vertices of Vik;2in and 2kn2, with distinct colors based on its previously colored vertices. In this coloring, {v(1)(2)(n2),v(n1)(n)} is the least cardinality of a color class and every vertex of ΛKn is adjacent to exactly one of these vertices. Hence, every vertex of ΛKn dominates half of this color class and we obtain χmd(ΛKn)=χ(ΛKn)=(n1)!1.

(ii) Consider a chromatic coloring c of Λ¯Kn, in which the color ci is assigned to the vertices of Vij=1i1Vj, for each 1in. In this coloring, the number of vertices assigned the color ci is ρ(n1)+k=1n2(niki1)ρ(nk) and it decreases from (n1)! to ρ(n1) as the value of i increases from 1 to n. Also, in this coloring, every vertex vπV(Λ¯Kn)Vn dominates the color class {vπ:c(vπ)=cn}. Hence, we must prove that every vertex in Vn dominates at least half of some color class, to prove the result. To prove this, it is enough to prove that a vertex vπ1Vnn2(V1V2), dominates at least half of V1 or V2. Therefore, consider the vertex vπ1V(Λ¯Kn), where π1=(3)(4)(n). This is adjacent to exactly ρ(n1)+ρ(n2) vertices of V1 and ρ(n1) vertices of V2. As ρ(n1)+ρ(n2)(n1)!2, for all n3, the vertex vπ1 is adjacent to more than half of the vertices of V1 and hence we obtain a majority dominator coloring of Λ¯Kn with n colors. ◻

Proposition 2.7. For n3,

(i) χd(ΛKn)=χtd(ΛKn)=χrd(ΛKn)=χpd(ΛKn)=χmd(ΛKn)=χ(ΛKn).

(ii) χdtd(ΛKn)=(n1)!+1.

(iii) χd(ΛKn)=χgd(ΛKn)=χpd(ΛKn)=χmd(ΛKn)=(n1)!+ρ(n).

Proof. As ΛKn has a universal vertex vπ0, every vertex of ΛKn properly dominate a color class, with respect to any of its χ-coloring and they also power dominate the color class {vπ0}. Owing to the existence of vπ0, any χ-coloring of ΛKn is its rainbow dominator coloring, and the double total dominator coloring of ΛKn can ve viewed as the total dominator coloring of ΛKn, which implies that (ii) is immediate from Theorem 2.1.

As ΛKn=ΛKnρ(n)K1, in any variant of dominator coloring of ΛKn all these ρ(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 ΛKn and ΛKn◻

Proposition 2.8. For n3,

(i) χd(Λ¯Kn)=χgd(Λ¯Kn)=χpd(Λ¯Kn)=2n1.

(ii) χmd(Λ¯Kn)=n+1.

(iii) χd(Λ¯Kn)=χtd(Λ¯Kn)=χdtd(Λ¯Kn)=χrd(Λ¯Kn)=χpd(Λ¯Kn)=χmd(Λ¯Kn)=n+ρ(n).

Proof. The proofs of (i) and (ii) are immediate from the fact that the graph Λ¯Kn=Λ¯Knvπ0, where vπ0 is an isolated vertex and hence in any variant of dominator coloring of Λ¯Kn, the vertex vπ0 is given a unique color to dominate itself. Also, Λ¯Kn is a graph with diameter 2, as there are ρ(n) universal vertices in it. Hence, in any proper coloring of Λ¯Kn, all these ρ(n) universal vertices are assigned distinct colors apart from the existing n colors that were used to color the vertices of Λ¯Kn, and as ρ(n)2, for all n3, the result follows. ◻

A vertex v in a graph G is said to strongly dominate a set AV(G) if v dominates A and deg(v)deg(u), for all uA. 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 χsd(G).

Theorem 2.9. For n4,

(i) χsd(ΛKn)=(n1)!+(n2).

(ii) χsd(ΛKn)=(n1)!+(n1).

(iii) χsd(ΛKn)=(n1)!+(n1)+ρ(n).

Proof. From a χ-coloring of ΛKn, we obtain a strong dominator coloring of ΛKn by assigning a unique color c(n1)!1+i;1in, which is not repeated anywhere to exactly one vertex of Vi1; for each 1in, so that every vertex of the graph strongly dominates a color class. Hence, χsd(ΛKn)(n1)!+(n2).

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 ΛKn, which are in Vi1 must form a color class, so as to minimise the number of colors used in a strong dominator coloring of ΛKn. As i=1nVi=nKρ(n), and if a vertex of Vi1;1in, has to dominate a color class, all vertices of that color class must be in the corresponding Vi, 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 (n1) Vi1’s, makes the vertices in the n-th Vi1 automatically get a unique color, and therefore, χsd(ΛKn)(n1)!+(n2).

As it is immediate that the strong dominator coloring of ΛKn can be extended to ΛKn, and ΛKn by assigning a unique colors to the vertex vπ0, and to the isolated vertices in ΛKn, the result follows. ◻

Theorem 2.10. For n4,

(i) χsd(Λ¯Kn)={n+(nn2)+k=n2+1n2(nk)ρ(nk),when n is even;n+k=n2+1n2(nk)ρ(nk),when n is odd. .

(ii) χsd(Λ¯Kn)=χsd(Λ¯Kn)+1.

(iii) χsd(Λ¯Kn)=χsd(Λ¯Kn)+ρ(n).

Proof. In Λ¯Kn, every vertex of i=1nVik;n2+1kn2, is adjacent to only the vertices of degree higher than theirs. Therefore, in any strong dominator coloring of Λ¯Kn, all these vertices must be assigned unique colors. Every vertex of i=1nVik;1kn21, is adjacent to at least one of the vertices of i=1nVik;n2+1kn2, which are uniquely colored and hence, all the vertices of i=1nVik;1kn21, strongly dominate at least one color class. Therefore, these vertices in i=1nVik;1kn21, are properly colored using n colors, apart from the ones assigned to the vertices of i=1nk=1n2+1Vik. If n is odd, we are done.

If n is even, the vertices of i=1nVin2 remains to be colored, at this point. Each vertex vπi=1nVin2 is adjacent to ρ(n2) vertices of i=1nVin2, which are of the same degree and to the vertices in i=1nVik;1kn21, which have degree higher than that of vπ. The subgraph of Λ¯Kn induced by i=1nVin2 is (nn2)Kρ(n2),ρ(n2), where ρ(n2) vertices correspond to permutations having a particular n2-element fix. Therefore, for every vertex vπi=1nVin2 to strongly dominate a color class, unique colors must be assigned to at least one of these ρ(n2) vertices that correspond to permutations with a distinct n2-element fix. Hence, χsd(Λ¯Kn)=n+(nn2)+k=n2+1n2(nk)ρ(nk), when n is even.

Using a similar arguments in Theorem 2.9, the above mentioned χsd-coloring of Λ¯Kn can be extended as the χsd-coloring of Λ¯Kn, and Λ¯Kn, by giving unique colors to vπ0, and the ρ(n) universal vertices of Λ¯Kn; completing the proof. ◻

A subset SV(G) in a graph G is called semi-strong if |N(v)S|1, for all vV(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 vV(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 χssd(G).

Proposition 2.11. For nN,

(i) χssd(ΛKn)=χssd(Λ¯Kn)=n!ρ(n)1.

(ii) χssd(ΛKn)=χssd(Λ¯Kn)=n!ρ(n).

(iii) χssd(Λ¯Kn)=χssd(ΛKn)=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(ΛKn) as well as V(Λ¯Kn), is a singleton. If possible, let S={vπ1,vπ2:fix(π1)fix(π2)} be a semi-strong subset of V(ΛKn). Clearly, here fix(π1)fix(π2) because, if fix(π1)=fix(π2), we get N(vπ1)=N(vπ2). Therefore, assume fix(π1)fix(π2) and hence |fix(π2)|2. As there exists ρ(n|fix(π1)|)1 vertices of the graph ΛKn corresponding to permutations having the same fix as fix(π1) and all of them will be adjacent to both the vertices of S, it yields a contradiction.

Consider a subset S={vπ1,vπ2:fix(π1)fix(π2)=} of V(ΛKn). In ΛKn, as there exists at least one vertex vπ3 such that fix(π3)fix(π1) and fix(π3)fix(π2), owing to the closure property of Sn; S cannot be semi-strong. Therefore, any semi-strong subset of V(ΛKn) is a singleton and χssd(ΛKn)=n!ρ(n)1. Using the same argument, as we can prove that any semi-strong subset of V(Λ¯Kn) is also a singleton, (i) follows.

Both the graphs ΛKn and Λ¯Kn 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 Λ¯KnΛKnρ(n)K1 and Λ¯KnΛ¯Knvπ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 χe(G). An equitable coloring of G in which every vertex vV(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 χ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 ΛKn and Λ¯Kn are n!ρ(n)12+1 and n!ρ(n)2+ρ(n), respectively.

Theorem 2.13. For nN,

(i) χed(ΛKn)=n!ρ(n)32+2.

(ii) χed(ΛKn)=χe(ΛKn).

(iii) χed(ΛKn)=χed(ΛKn)+ρ(n).

Proof. In any χd-coloring c of ΛKn, we know that there are at least two singleton color classes (see Theorem 2.1). Therefore, in any equitable dominator coloring of ΛKn, 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π,vπV(ΛKn), where |fix(π)fix(π)|=n and fix(π)fix(π)=. Therefore, the remaining n!ρ(n)3 vertices of ΛKn are partitioned into independent sets of cardinality 2. This partition can be viewed as the equitable coloring of ΛKn given in the proof of Theorem 2.12 (ref. [8]), just by removing the vertices vπ,vπ and vπ0. Hence, χed(ΛKn)=n!ρ(n)32+2.

In any proper coloring of ΛKn, the vertex vπ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 ΛKn, any χe-coloring of ΛKn becomes an equitable dominator coloring of ΛKn. The same equitable dominator coloring of ΛKn when extended to the graph ΛKn, where the ρ(n) universal vertices are assigned distinct colors to dominate themselves becomes an equitable dominator coloring of ΛKn. The minimality of these parameters are also ensured by the minimality of χe(ΛKn); thereby yielding the required result. ◻

Theorem 2.14. For nN,

(i) χed(Λ¯Kn)=n!ρ(n)12+1.

(ii) χed(Λ¯Kn)=χe(Λ¯Kn).

Proof. The graph Λ¯Kn has ρ(n) universal vertices and hence any χe-coloring of Λ¯Kn is its χed-coloring. As the graph Λ¯Kn has exactly one isolated vertex vπ0, a unique color is assigned to it in any dominator coloring of Λ¯Kn. Therefore, in any equitable dominator coloring of Λ¯Kn, each color class must have either one or two vertices. That is, the remaining n!ρ(n)1 vertices of Λ¯Kn are partitioned into independent sets of cardinality 1 or 2, in any equitable dominator coloring of Λ¯Kn. As the same kind of partitioning of V(Λ¯Kn) is obtained to determine its equitable coloring pattern in Theorem 2.12, we determine the χed-coloring of Λ¯Kn based on the χe-coloring of Λ¯Kn given in the proof of Theorem 2.12 in [8].

Consider the equitable chromatic partition of V(Λ¯Kn) without the the ρ(n) universal vertices and make vπ0 a singleton. Then, the other vertex which was assigned the same color as vπ0 in the χe-coloring of V(Λ¯Kn), either remains a singleton or it can be given the same color as some other vertex, which is a singleton in the χe-coloring of Λ¯Kn (For more details, see [8]). This is possible because Sn is a group, and there always exists at least one unique k-element fix which is disjoint with the any given k-element fix, where 1kkn2. This gives an optimal equitable dominator coloring of Λ¯Kn, as there are at most two singletons, which cannot be paired with any other vertex of Λ¯Kn◻

Based on the structure of Λ¯Kn, it can be seen that its dominator coloring pattern is according to the assignment of colors to the ρ(n1) vertices in each Vi1;1in. As there does not exist a generalisable pattern for ρ(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 χed(Λ¯Kn) becomes highly arduous and therefore, remains an open problem, at this point of study.

Table 1 Variants of dominator coloring parameters of the n-inordinate invariant intersection graphs and their derived graphs
S.No. Ch. No. ΛKn ΛKn ΛKn Λ¯Kn Λ¯Kn Λ¯Kn
1 χd (n1)! +ρ(n) (n1)! (n1)! n+ρ(n) 2n1 2(n1)

2
χtd Cannot Admit (n1)! (n1)!+1 n+ρ(n) Cannot Admit 2(n1)

3
χdtd Cannot Admit (n1)!+1 (n1)!+2 n+ρ(n) Cannot Admit 2n1

4
χgd (n1)! +ρ(n) Cannot Admit (n1)!+(n3) Cannot Admit 2n1 2n

5
χtgd Cannot Admit Cannot Admit (n1)!+(n2) Cannot Admit Cannot Admit 2n

6
χrd Not Defined (n1)! (n1)! n+ρ(n) Not Defined 2(n1)

7
χpd (n1)! +ρ(n) (n1)! (n1)! n+ρ(n) n+1 2(n1)

8
χmd (n1)! +ρ(n) (n1)! (n1)!1 n+ρ(n) n+1 n

9
χsd (n1)!+ (n1) +ρ(n) (n1)! +(n1) (n1)! +(n2) 1+ρ(n)+n+(nn2)+k=n2n2(nk)ρ(nk) 1+n+(nn2)+k=n2n2(nk)ρ(nk) n+(nn2)+k=n2n2(nk)ρ(nk)

10
χssd n!ρ(n) n!ρ(n) n!ρ(n)1 n! n!ρ(n)1 n!ρ(n)1

11
χed n!ρ(n)12 +ρ(n)+1 n!ρ(n)12 +1 n!ρ(n)32 +2 n!ρ(n)2 +ρ(n) n!ρ(n)12+1 2(n1)χed(Λ¯Kn) n!ρ(n)nρ(n1)ρ(n1)}+n

3. Conclusion

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.

References:

  1. G. E. Andrews and K. Eriksson. Integer Partitions. Cambridge University Press, England, 2004.
  2. P. S. George, S. Madhumitha, and S. Naduvath. Equitable dominator coloring of graphs. arXiv preprint arXiv:2408.14374, 2024. https://doi.org/10.48550/arXiv.2408.14374.
  3. P. S. George, S. Madhumitha, and S. Naduvath. Equitable dominator coloring of helm related graphs. Journal of Interconnection Networks, To Appear, 2025.
  4. I. N. Herstein. Topics in Algebra. John Wiley & Sons, New Jersey, 2006.
  5. C. L. Liu. Introduction to Combinatorial Mathematics. McGraw-Hill Inc., New York, 1968.
  6. S. Madhumitha and S. Naduvath. Graphs defined on rings: a review. Mathematics, 11(17):3643, 2023. https://doi.org/10.3390/math11173643.
  7. S. Madhumitha and S. Naduvath. k-dominator coloring of graphs. Mathematica, To Appear, 2024.
  8. S. Madhumitha and S. Naduvath. Coloring of n-inordinate invariant intersection graphs. Journal of Combinatorial Mathematics and Combinatorial Computing, 123(369):381, 2024. https://doi.org/10.61091/jcmcc123-26.
  1. S. Madhumitha and S. Naduvath. Graphs on groups in terms of the order of elements: a review. Discrete Mathematics, Algorithms and Applications, 16(3), 2024. https://doi.org/10.1142/S1793830923300035.
  2. S. Madhumitha and S. Naduvath. Invariant intersection graph of a graph. Journal of Discrete Mathematical Sciences and Cryptography, To Appear, 2024.
  3. S. Madhumitha and S. Naduvath. Variants of dominator coloring of graphs: a creative review. Communicated, 2024.
  4. S. Madhumitha, S. Naduvath, and V. S. Prebhath. n-inordinate invariant intersection graphs and their derived graphs. Communicated, 2024.
  5. D. B. West. Introduction to Graph Theory. Prentice Hall of India, New Delhi, 2001.