A special type of algebraic intersection graph called the -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 -inordinate invariant intersection graphs and their complements, -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 is called the chromatic
number of , denoted by , and any coloring of with colors is called a -coloring of . In a graph , if a vertex is adjacent to all vertices
, for some or , we say that dominates and is dominated by . In this context, if , we say that properly dominates (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 -inordinate
invariant intersection graph, was identified in [12] as the graph with and any two
distinct vertices corresponding to the permutations are adjacent in
when , where is the symmetric group, and
for any , is the set
.
An illustration of -inordinate
invariant intersection graphs is given in Figure 1. Note
that the identity permutation is denoted by and the vertex corresponding to a
permutation is denoted
by ,
throughout the study.
Figure 1 The 4-inordinate invariant intersection graph
In [12], the structural
properties of the -inordinate
invariant intersection graphs and their complements,
-inordinate invariant
non-intersection graphs, denoted by , were
investigated and it was found that , where ;
, is the number of
derangements of elements and
is the
non-trivial component of with diameter 2, having
vertices.
Following the study in [12], different proper vertex colorings of the
graphs and were discussed
in [8]. In this article, we
study the variants of dominator coloring of graphs, for the -inordinate invariant intersection
graphs and their complements.
As has isolated
vertices and 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 , and ,
respectively. Hence, our primary focus of study is on the coloring
patterns of the connected graphs , for , and ,
for , denoted by and ,
respectively.
Note that and , as it has been
proven in [12] that and . 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 -inordinate invariant intersection
graphs
In this section, we examine the variants of dominator colorings of
the graphs , , , ,and , and
for this, we use the notations ; for , and ; , throughout the
article.
A dominator coloring of a graph is a proper vertex coloring of such that every vertex dominates at
least one color class; possibly its own, and the dominator chromatic
number of is denoted by
.
A total dominator coloring (resp. double total dominator
coloring) of a graph is a
dominator coloring of 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 is denoted by (resp. ).
Theorem 2.1. For ,
(i).
(ii).
Proof. (i) In , the vertices of
, for any , are adjacent only to the
vertices in the corresponding .
Hence, in any dominator coloring of , these vertices
can dominate a color class if and only if a color is assigned
exclusively for the vertices in that . As each , induces a clique
in , such
exclusive color can be given to exactly one vertex and in any -coloring of , this cannot be
an exclusive color. Hence, .
As it can be seen that for any two vertices with , , where , for
any , we get the required dominator
coloring pattern by validating if all the vertices of , dominate the
required number of color classes.
Define a coloring
as follows. As ,
first assign the colors to the vertices of such that , , , where have , and
. Following this, color the vertices , for each , in order, where the
vertices of each ; , are colored with colors based on the previously
colored vertices in the cliques , such that , , and , where have ,
and .
The existence of the above mentioned -coloring of is guaranteed,
as the color assigned to any vertex is assigned either exactly to one other vertex in
, or at
most two vertices; that is, one from and , where , and , in any -coloring of . This is owing
to the structure of the graph that demands each color class to contain
exactly one vertex from each and if any color is assigned to with
and to a vertex of and
, we swap one of the colors assigned to the vertices
in to
these two vertices, as it does not alter any of the properties of the
considered -coloring of .
Now, in order to make this -coloring , a dominator coloring of , we assign , which makes
all the vertices in dominate
the color class and
the vertices in dominate
the color class .
Also, as it can be seen that all the vertices in properly dominate either the color class or , the vertex properly dominates the color
class , and
the vertex properly
dominates the color class , in this
dominator coloring of with colors, we have .
(ii) In the dominator coloring
of
mentioned above, no vertex in
dominates two color classes and using the similar arguments mentioned in
(i), it can be deduced that . From the dominator coloring of , we obtain a
double total dominator coloring
of by
assigning , which makes
every vertex of the graph properly dominate at least two color classes;
thereby completing the proof.
Theorem 2.2. For ,
(i).
(ii).
Proof. Consider the coloring such that for any vertex ,
It is a dominator coloring of as
every vertex that corresponds to a permutation fixing -elements dominates at least color classes with respect to this
coloring of .
Hence, .
In , a
vertex , dominates a color class if and only if none of the vertices
in that color class are in the same . Consider a vertex , for some , such that , where . Therefore, this vertex can dominate a color class if and
only if all vertices of the color class are from . As there are possible pairs of such and , we must obtain a color class that is
exclusive to each , except one, for any such to dominate a color class. All vertices of exactly one , can be colored
with the same color because for every there are two ’s; , such that they are adjacent to all the vertices
of these ’s, and one among them
can be chosen to have an exclusive color class. Also, as the ’s are non-disjoint, if colors are
assigned to the vertices from each , in the end, for some , . Hence, we require at least colors to obtain a dominator
coloring of .
Therefore, . This dominator coloring of is
also its total dominator coloring as every vertex in properly dominates a color class
assigned the color ,
, and
hence, it follows that .
In any -coloring of
, it
can be seen that every vertex properly dominates at least color classes, where and all
but one vertex in properly
dominate at least two color classes. Therefore, it can be deduced that
in an optimal double total dominator coloring, all , have to be
assigned unique colors and hence .
Corollary 2.3. For ,
(i).
(ii).
A global dominator coloring (resp. total global
dominator coloring) of a graph is a proper coloring of such that every vertex of dominates (resp. properly dominates) as
well as anti-dominates at least one color class, where a vertex is said to
anti-dominate a set if ,
for all , such that . The global dominator
chromatic number (resp. total global dominator chromatic
number) of is denoted by
(resp. ).
Theorem 2.4. For ,
(i).
(ii).
(iii).
Proof. (i) Any vertex is not adjacent to vertices of and vertices of , such that and , in . Therefore, if a
vertex has to
anti-dominate any color class with respect to some proper coloring of
, such a
color class must contain only the vertices of , where , and . As there are possible pairs of such and , we must obtain a color class that is
exclusive to each , except one, for any such to anti-dominate a color class. Hence, .
There exists a -coloring of
, say , in which some color , is assigned
to vertices of ; that is, one from each , as every color class in any -coloring of must contain one
vertex from each , and let , be
vertices such that for all , , for some . The existence the coloring is guaranteed owing to the nature
of the color classes in any -coloring of and the fact
that ’s are non-disjoint.
We make such a -coloring
of , a global
dominator coloring of , by assigning
the color to the
vertex . Now, only one vertex in and one vertex in have the color , and as mentioned in Theorem 2.1, we swap the color of the
vertices and with the color of a vertex, say
, in . Here, every
vertex in ,
dominates the color class and the vertices of dominate the color class
. Also, any
vertex anti-dominates the color class
, such that and
the vertex
anti-dominates the color class ; thereby, yielding
.
(ii) In the above mentioned global dominator coloring of , all the
vertices of , except the
ones in assigned the colors
, for , and the vertex , does not properly
dominate any color class. Therefore, it can be seen from (i) that we
require at least
colors, in any total global dominator coloring of .
To obtain a total global dominator coloring of with
colors, consider the coloring defined above and assign the color
to the vertex , which makes the
vertices , dominate the color class . As mentioned
in Theorem 2.1, any color, say , for some and , assigned to the vertex is assigned either
exactly to one other vertex of the form or at most two vertices of
the form and , in any proper coloring of . Hence, as the
vertex is
assigned a new color by , the
vertex now properly
dominates the color class of the color which was earlier assigned to the
vertex .
Therefore, we obtain an optimal total global dominator coloring of with colors.
(iii) By Theorem 2.2, it can be seen that in any
-coloring of , any
vertex anti-dominates at
most color classes, where .
Therefore, we require additional colors for the vertices , to anti-dominate
some color class. For any vertex in , 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 . Therefore, to minimise the number of
such additional colors, we assign the color to the vertex , such that . If
, then the vertices of and ; for some , still do not
anti-dominate any color class. Hence, a vertex such that , is assigned the color to obtain a global dominator
coloring of with
colors. Note that the above
mentioned coloring is also a total global dominator coloring of , as
every vertex of the graph properly dominates a color class. Also, as the
minimality of the parameter follows from the structure of and
the global dominator coloring protocol, .
A proper coloring of a graph
is said to be a rainbow
dominator coloring of if
is a dominator coloring of such that for every , there exists a path in which no two internal
vertices have the same color and the rainbow dominator chromatic
number of is denoted by
. A power dominator
coloring of a graph is a
proper vertex coloring of such
that every vertex power dominates at least one color class; possibly its
own, and the power dominator chromatic number of is denoted by . A vertex is said to power
dominate the vertices in , which is constructed as follows.
(i) .
(ii) Consider a vertex and add it to if
there exists a
such that all
are already in .
(iii) Repeat Step (ii) until no vertex could be added to .
Proposition 2.5. For any ,
(i)
(ii).
Proof. As the graph has diameter 2,
all path of length 2 between
any two vertices of , whose only
internal vertex has a distinct color. Hence, . In , any
two non-adjacent vertices
and correspond to
permutations such that . Here, if , then there is a path of
length 2 between the vertices and in and
its internal vertex is uniquely colored, in any proper coloring of . If
, then the non-adjacent
vertices do not have a common neighbour and we have a path ,
where
and , where , such that and . As , for
any , there exists at
least two vertices in to which any
vertex of is
adjacent to. As this path is of length 3, and both internal vertices
are colored with distinct colors, in any proper coloring of ,
.
Also, the idea of a vertex power dominating a color class reduces to
the vertex dominating the color class in the graphs and , for
, as there is no vertex
having a unique
neighbour which is not a neighbour of , for any in or . This
is because, corresponding to every -element fix, there are permutations and hence, vertices corresponding to the
same -element fix in the graphs
and . The
adjacencies and non-adjacencies between two vertices corresponding to
any pair of permutations with distinct -element fixes induce the same relation
on all of the vertices;
thereby yielding and .
A majority dominator coloring of a graph is a proper vertex coloring of in which each vertex of the graph
dominates at least half of one color class and the majority
dominator chromatic number of is denoted by .
Theorem 2.6. For any ,
(i).
(ii).
Proof. (i) Consider a -coloring of , where the
colors ,
are assigned to the vertices of , as it induces a clique in . Following this,
consider the vertices , for each , in order. Assign
distinct colors to , such that , where
and each of the
remaining vertices of and ,
with distinct colors based on its previously colored vertices. In this
coloring, is the least cardinality of a color class and
every vertex of is adjacent to
exactly one of these vertices. Hence, every vertex of dominates half
of this color class and we obtain .
(ii) Consider a chromatic coloring of , in which the
color is assigned to the
vertices of , for each . In this coloring, the
number of vertices assigned the color is
and it decreases from to
as the value of increases from to . Also, in this coloring, every vertex
dominates the color class .
Hence, we must prove that every vertex in dominates at least half of some color
class, to prove the result. To prove this, it is enough to prove that a
vertex , dominates at least half of or . Therefore, consider the vertex , where . This is adjacent
to exactly
vertices of and vertices of . As ,
for all , the vertex is adjacent to more than half
of the vertices of and hence we
obtain a majority dominator coloring of with colors.
Proposition 2.7. For ,
(i).
(ii).
(iii).
Proof. As has a universal vertex
, every vertex of properly dominate a
color class, with respect to any of its -coloring and they also power
dominate the color class . Owing to the existence of
, any -coloring of is its rainbow
dominator coloring, and the double total dominator coloring of can ve viewed as the
total dominator coloring of , which implies
that (ii) is immediate from Theorem 2.1.
As , in any variant of dominator coloring of all these 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 and .
Proposition 2.8. For ,
(i).
(ii).
(iii).
Proof. The proofs of (i) and (ii) are immediate from the
fact that the graph , where is an isolated vertex and hence
in any variant of dominator coloring of , the vertex
is given a unique color
to dominate itself. Also, is a graph with
diameter 2, as there are
universal vertices in it. Hence, in any proper coloring of , all these universal vertices are assigned
distinct colors apart from the existing colors that were used to color the
vertices of ,
and as , for all
, the result follows.
A vertex in a graph is said to strongly dominate a
set if dominates and , for all . A strong dominator coloring of a graph is a proper vertex coloring of such that every vertex strongly
dominates at least one color class and the strong dominator
chromatic number of is
denoted by .
Theorem 2.9. For ,
(i).
(ii).
(iii).
Proof. From a -coloring of , we obtain a
strong dominator coloring of by assigning a
unique color , which is not repeated anywhere to exactly one vertex of
for each , so that every vertex of
the graph strongly dominates a color class. Hence, .
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 , which are in
must form a color class, so
as to minimise the number of colors used in a strong dominator coloring
of . As
, and if a vertex of , has to dominate
a color class, all vertices of that color class must be in the
corresponding , the vertices of
the least degree forms color
classes, so that they are strongly dominated by all the other vertices.
Assigning unique colors to ’s, makes the vertices in the
-th automatically get a unique color,
and therefore, .
As it is immediate that the strong dominator coloring of can be extended
to , and by assigning a unique
colors to the vertex , and
to the isolated vertices in , the result follows.
Theorem 2.10. For ,
(i) .
(ii).
(iii)
Proof. In ,
every vertex of , is adjacent to only the
vertices of degree higher than theirs. Therefore, in any strong
dominator coloring of , all
these vertices must be assigned unique colors. Every vertex of , is adjacent to at least one of the
vertices of , which are
uniquely colored and hence, all the vertices of , strongly dominate at least one
color class. Therefore, these vertices in , are properly colored using colors, apart from the ones assigned to
the vertices of . If
is odd, we are done.
If is even, the vertices of
remains to be colored, at this point. Each vertex is adjacent to vertices of ,
which are of the same degree and to the vertices in , which have degree higher than that of . The subgraph of
induced by
is , where vertices correspond to
permutations having a particular -element fix. Therefore, for
every vertex to strongly dominate
a color class, unique colors must be assigned to at least one of these
vertices that
correspond to permutations with a distinct -element fix. Hence, , when is even.
Using a similar arguments in Theorem 2.9,
the above mentioned -coloring of can
be extended as the -coloring of , and
, by giving
unique colors to , and the
universal vertices of ; completing the
proof.
A subset in a
graph is called
semi-strong if , for all .
Partitioning into semi-strong
subsets is called a semi-strong coloring of and a dominator semi-strong color
partition of is a
semi-strong coloring of in which
every vertex dominates
at least one color class. The minimum order of such a partition is
called the dominator semi-strong color partition number of
, denoted by .
Proposition 2.11. For ,
(i).
(ii).
(iii).
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 as well as
,
is a singleton. If possible, let be a semi-strong
subset of . Clearly,
here because, if , we get . Therefore, assume and hence . As
there exists
vertices of the graph corresponding to
permutations having the same fix as and all of
them will be adjacent to both the vertices of , it yields a contradiction.
Consider a subset of . In , as there
exists at least one vertex such that and , owing to the
closure property of ; cannot be semi-strong. Therefore,
any semi-strong subset of is a
singleton and . Using the same argument, as we can prove that any
semi-strong subset of is
also a singleton, (i) follows.
Both the graphs and 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 and , the result
is immediate.
A proper coloring of a graph
in which the cardinalities of the color classes differ by at most one is
called an equitable coloring of and the equitable chromatic
number of is denoted by
. An equitable coloring
of in which every vertex dominates at least one color
class is called an equitable dominator coloring of and the equitable dominator
chromatic number of is
denoted by (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
and are
and , respectively.
Theorem 2.13. For ,
(i).
(ii).
(iii).
Proof. In any -coloring of , we know that
there are at least two singleton color classes (see Theorem 2.1). Therefore, in any equitable
dominator coloring of , 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 , where and . Therefore, the
remaining vertices
of are
partitioned into independent sets of cardinality 2. This partition can
be viewed as the equitable coloring of given in the proof
of Theorem 2.12 (ref. [8]), just by removing the vertices and . Hence, .
In any proper coloring of , the vertex 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 , any -coloring of becomes an equitable
dominator coloring of . The same equitable
dominator coloring of when extended to the
graph , where the
universal vertices are
assigned distinct colors to dominate themselves becomes an equitable
dominator coloring of . The minimality of these
parameters are also ensured by the minimality of ; thereby
yielding the required result.
Theorem 2.14. For ,
(i).
(ii).
Proof. The graph has universal vertices and hence any
-coloring of is its -coloring. As the graph has
exactly one isolated vertex , a unique color is assigned to
it in any dominator coloring of .
Therefore, in any equitable dominator coloring of , each
color class must have either one or two vertices. That is, the remaining
vertices of are
partitioned into independent sets of cardinality 1 or 2, in any
equitable dominator coloring of . As the
same kind of partitioning of is obtained
to determine its equitable coloring pattern in Theorem 2.12, we determine the -coloring of based on
the -coloring of given in the
proof of Theorem 2.12 in [8].
Consider the equitable chromatic partition of without the
the universal vertices and
make a singleton. Then,
the other vertex which was assigned the same color as in the -coloring of , either
remains a singleton or it can be given the same color as some other
vertex, which is a singleton in the -coloring of (For more
details, see [8]). This is
possible because is a group,
and there always exists at least one unique -element fix which is disjoint with the
any given -element fix,
where .
This gives an optimal equitable dominator coloring of , as there
are at most two singletons, which cannot be paired with any other vertex
of .
Based on the structure of , it
can be seen that its dominator coloring pattern is according to the
assignment of colors to the vertices in each . As there does
not exist a generalisable pattern for , 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
becomes highly arduous and therefore, remains an open problem, at this
point of study.
Table 1 Variants of dominator coloring parameters of the -inordinate invariant intersection graphs and their derived graphs
S.No.
Ch. No.
1
2
Cannot Admit
Cannot Admit
3
Cannot Admit
Cannot Admit
4
Cannot Admit
Cannot Admit
5
Cannot Admit
Cannot Admit
Cannot Admit
Cannot Admit
6
Not Defined
Not Defined
7
8
9
10
11
}+
3. Conclusion
In this article, we have exclusively investigated different dominator
coloring schemes for the -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 -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:
G. E. Andrews and K. Eriksson. Integer Partitions. Cambridge University Press, England, 2004.
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.
P. S. George, S. Madhumitha, and S. Naduvath. Equitable dominator coloring of helm related graphs. Journal of Interconnection Networks, To Appear, 2025.
I. N. Herstein. Topics in Algebra. John Wiley & Sons, New Jersey, 2006.
C. L. Liu. Introduction to Combinatorial Mathematics. McGraw-Hill Inc., New York, 1968.
S. Madhumitha and S. Naduvath. k-dominator coloring of graphs. Mathematica, To Appear, 2024.
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.
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.
S. Madhumitha and S. Naduvath. Invariant intersection graph of a graph. Journal of Discrete Mathematical Sciences and Cryptography, To Appear, 2024.
S. Madhumitha and S. Naduvath. Variants of dominator coloring of graphs: a creative review. Communicated, 2024.
S. Madhumitha, S. Naduvath, and V. S. Prebhath. n-inordinate invariant intersection graphs and their derived graphs. Communicated, 2024.
D. B. West. Introduction to Graph Theory. Prentice Hall of India, New Delhi, 2001.