Conjugate Graph and Conjugacy Class Graph related to Direct Product
of Dihedral Groups
CHINMAYEE KUMAR, KUNTALA PATRA
Department of Mathematics,
Gauhati University,
Guwahati, Assam 781014,
INDIA
Abstract: - Let be a non-abelian group. The conjugate graph of is a graph whose vertices are the non-
central elements of and two vertices are adjacent if they belong to the same conjugacy class. The conjugacy
class graph of is a graph whose vertices are the non-central conjugacy classes of and two vertices are
adjacent if is greater than one. In this paper, we explore the structures of these graphs for the
groups for odd and even values of and . The chromatic number and independence number of the
conjugate graphs, their line graphs and complement graphs are found. We discuss various graph parameters like
the existence of Eulerian and Hamiltonian cycles, planarity, connectedness, chromatic number, clique number,
independence number, and diameter of the conjugacy class graphs of these groups.
Key-Words: - Conjugate graph, conjugacy class graph, line graph, complement graph, direct product, non-
abelian group, dihedral group.
Received: September 22, 2023. Revised: April 21, 2024. Accepted: June 22, 2024. Published: July 19, 2024.
1 Introduction
Algebraic graph theory is an interesting subject
concerned with the interplay between algebra and
graph theory where algebraic tools are applied to
yield useful insights of graph theoretic facts. This
area of graph theory contributes to the study of
properties of graphs by translating them into
algebraic structures and the results and methods of
algebra are applied to deduce theorems about the
graphs. Also, many algebraic structures can be
studied by translating them into graphs and using
the properties of graphs. One such branch of
algebraic graph theory involves the study of
symmetry and regularity of graphs by using group
theory. This paper contributes to the understanding
of the intersection between graph theory and group
theory, specifically in the context of non-abelian
groups.
In 1990, a new graph called the conjugacy
class graph, denoted by , related to conjugacy
classes of non-abelian groups was introduced, [1].
The conjugacy class graph of a non-abelian group
, denoted by , is a graph whose vertices are
the non-central conjugacy classes of and two
distinct vertices are adjacent if the greatest
common divisor of the sizes of the vertices (orders
of the conjugacy classes) is greater than one.
Motivated by the structure of conjugacy classes,
another graph called conjugate graph, denoted by
, of a non-abelian group was defined, [2]. The
vertices of this graph are the non-central elements
of the group and two vertices are adjacent if they
belong to the same conjugacy class. It was found
that if is a finite non-abelian simple group
satisfying Thompson's conjecture and
, then , where is a finite non-abelian
group. Many research articles have been published
thereafter related to conjugate graphs of finite p-
groups [3], regularity of graph related to conjugacy
classes [4], graph properties of conjugate graphs
and conjugacy class graphs of metacyclic 2-groups
of order at most 32 [5], the conjugate graphs and
generalized conjugacy class graphs of metacyclic
3-groups and metacyclic 5-group [6], and the non-
conjugate graph associated with finite groups and
the resolving polynomial for generalized
quaternion groups, [7].
In this paper, we explore the conjugacy classes
related to direct products of dihedral groups and
discuss various graph parameters of the conjugate
graphs and conjugacy class graphs of these groups.
Graph parameters like chromatic number and
regularity of graphs are crucial concept in graph
theory that has numerous applications in various
fields like computer science, operation research,
network topology, cryptography, and game theory
WSEAS TRANSACTIONS on MATHEMATICS
DOI: 10.37394/23206.2024.23.48
Chinmayee Kumar, Kuntala Patra
E-ISSN: 2224-2880
458
Volume 23, 2024
while the independence number of a graph serve as
a useful tool in real world optimization problems.
This paper is divided into five sections. The
first section is the introductory section where we
give a brief definition of conjugacy classes,
conjugate graph, and conjugacy class graph and an
overview of the previously published works on this
topic. In the second section, we state some
preliminary definitions and results that have been
referred to for our study. The third section involves
detailed proof of our findings. In section 4, we
summarize the key findings of our work, and
discuss the methodology used and possible
applications of the results presented here. Finally,
in section 5, we have mentioned some of the
potential areas for further research in this topic.
Throughout the paper, the graphs referred to are
undirected and simple graphs.
2 Basic Definitions and Results
In this section we state some basic definitions and
results which have been referred to for establishing
our main results.
Definition 2.1: Conjugate elements and
Conjugacy class
Two elements of a group are said to be
conjugate if there exists an element such
that . The set of all elements conjugate
to is called the conjugacy class of and is
denoted by . The conjugacy relation is an
equivalence relation that partitions into disjoint
equivalence classes, called the conjugacy classes.
Definition 2.2: Connected graph
A graph is said to be connected if there exists a
path between any two distinct vertices in the graph;
otherwise is said to be disconnected.
Definition 2.3: Planar Graph
A planar graph is a graph that can be embedded in
the plane, i.e., it can be drawn in such a way that no
edges cross each other.
Definition 2.4: Diameter of a graph
The diameter of a connected graph is the maximum
distance between any two vertices in the graph.
Definition 2.5: Chromatic number of a graph
The chromatic number of a graph , denoted by
, is the smallest number of colors required to
color the vertices of so that no two adjacent
vertices share the same color.
Definition 2.6: Clique and Clique number of a
graph
A clique of a graph is a complete induced
subgraph of and the number of vertices in the
largest clique of is called the clique number of .
Definition 2.7: Independence number of a graph
The independence number of a graph is the
maximum number of vertices from the vertex set of
the graph such that no two vertices are adjacent.
Definition 2.8: Eulerian and Hamiltonian graph
A connected graph is said to be Eulerian if it
contains an eulerian circuit, i.e., it contains a trail
that visits every edge exactly once and starts and
ends on the same vertex. A Hamiltonian circuit in a
connected graph is defined as a closed walk that
traverses every vertex of exactly once.
Definition 2.9: Regular graph
A graph is said to be regular if all its vertices have
the same degree. A graph is said to be
regular if the degree of each vertex in is.
Definition 2.10: Line graph
Given a graph , the line graph of is a
graph whose vertices are the edges of , with two
vertices of adjacent whenever the
corresponding edges of are adjacent. Thus, the
line graph represents the adjacencies between
the edges of .
Definition 2.11: Direct product of two groups
For two groups and , the direct product
is defined as,
Two elements and are conjugate
in if and only if and are conjugate in
and and are conjugate in . Thus, each
conjugacy class in is the cartesian product of
a conjugacy class in and a conjugacy class in .
Proposition 2.1: A graph is said to be a planar
graph if and only if it contains no subgraph
isomorphic to or , [8].
Proposition 2.2: A connected graph is eulerian if
and only if every vertex has even degree, [8].
Proposition 2.3: A simple graph is hamiltonian
if the degree of every vertex in is atleast
, where
is the number of vertices in , [8].
WSEAS TRANSACTIONS on MATHEMATICS
DOI: 10.37394/23206.2024.23.48
Chinmayee Kumar, Kuntala Patra
E-ISSN: 2224-2880
459
Volume 23, 2024
Proposition 2.4: The line graph of the
complete graph has the following properties:
G has
vertices.
G is regular of degree .
Every two non-adjacent points are
mutually adjacent to exactly four points.
Every two adjacent points are mutually
adjacent to exactly points, [9].
3 Main Results
Before proceeding to our main findings, we first
list the conjugacy classes of . The dihedral group
of order is the group of symmetries
of a regular -sided polygon which consists of
reflections and rotations. If denotes any one of
the -reflections and denote the rotation about
the center through an angle
, then the group
presentation of is given by:
We have two cases here:
Case 1: When is odd, then
Case 2: When is even, then
The distinct elements of are:
This paper is an extension of [10] where we
studied the nature and properties of the elements of
dihedral group and their conjugacy class size and it
was found that if denotes the number of
conjugacy classes of , then,
When is odd, the conjugacy classes of are
When is even, the conjugacy classes of are
The following results are thus obtained.
Theorem 1: The independence number of the
conjugate graph of is given as:
Proof: Conjugate graphs are disconnected and
union of complete graphs. So, the number of
components gives the independence number of the
conjugate graphs.
Case 1: Both are odd.
Then there are
conjugacy classes in
. Since the conjugate graphs do not
contain the centre, there are
components in the conjugate graph of
which is also the independence number of the
graph.
Case 2: Both are even.
Then there are
conjugacy classes
in . The centre of (for even value
of ) has order 2 and so there are
components in the conjugate
graph of .
Case 3: is even and odd.
In this case there are
conjugacy
classes in . The centre of has order 2
and the centre of has order 1. So, there are
components in the conjugate
graph of .
WSEAS TRANSACTIONS on MATHEMATICS
DOI: 10.37394/23206.2024.23.48
Chinmayee Kumar, Kuntala Patra
E-ISSN: 2224-2880
460
Volume 23, 2024
Theorem 2: The chromatic number of
is given by:
Proof: The conjugate graphs being disconnected
and union of complete graphs, so the component of
the conjugate graph with the highest number of
vertices gives the chromatic number of the graph.
We have 3 cases:
Case 1: Both are odd.
There are
conjugacy classes in
and orders of the conjugacy classes are
and . Since , the
conjugacy class with order is the largest.
Case 2: Both are even.
There are
conjugacy classes in
and orders of the conjugacy classes are
and
. Since , the largest
conjugacy class is of order
.
Case 3: odd, even.
There are
conjugacy classes in
and orders of the conjugacy classes are
and
. Here, and .
So, the conjugacy class of highest order is of order
.
Since each conjugacy class constitutes a
component in the conjugate graph, the largest
component in each case has order ,
and
respectively.
Example 1: Consider .
Conjugacy classes of are
The 9 conjugacy classes of are ,
, ,
,
,
By definition, there are components
in with orders and
Clearly, Independence number of
and Chromatic number of .
Theorem 3: The chromatic number of
is the number of components in
.
Proof: Let the number of components of
be . Each component forms a point (or
vertex) as a set of non-adjacent vertices in
. The disconnected components in
together form a complete graph of
vertices in
. Therefore, is the
minimum number of colors required to color the
vertices of
and so chromatic number
= = number of components of .
Theorem 4: The independence number of
is given by:
Proof: Each component in forms a
point (or vertex) as a set of non-adjacent vertices in
. The vertices in
are
such that each vertex is a set of non-adjacent
vertices which are adjacent to every other vertex.
Clearly, the point (vertex) with the highest number
of non-adjacent vertices in
gives the
independence number of
, which is
nothing but the component in with
maximum number of vertices. Hence, the result
follows from Theorem 2.
Theorem 5: The chromatic number of the line
graphs of are given by:
Proof: The conjugate graphs are disconnected
unions of complete graphs, so their line graphs are
again disconnected but unions of regular graphs.
WSEAS TRANSACTIONS on MATHEMATICS
DOI: 10.37394/23206.2024.23.48
Chinmayee Kumar, Kuntala Patra
E-ISSN: 2224-2880
461
Volume 23, 2024
The largest component in the line graph
correspond to the largest component in the
conjugate graph. Since the largest component in the
conjugate graphs have sizes ,
and
, so the
largest component in the line graph comprises of a
regular graph of
vertices of degree
,
vertices of degree
,
vertices of degree
respectively for the
three cases. Since the chromatic number is at most
one greater than maximum degree, so,
Also, the line graph corresponding to a
complete graph of order is such that every two
adjacent points are mutually adjacent to exactly
points. So, the minimum chromatic number
for a line graph corresponding to a complete graph
is at least . Hence the result.
Theorem 6: The conjugacy class graph of
is a connected graph.
Proof: The conjugacy class graphs are such that
each vertex represents a set of vertices with same
order and adjacent to each other. The adjacency
between any two pair of vertices indicates that
every point in a vertex is adjacent to each point in
the other vertex and so on. Conjugacy classes of
same order, say , are represented by a vertex
indexed .
We have 3 cases here:
Case 1: If both are odd, the vertices with
cardinality and are adjacent to all the
vertices. The graph structures are either of the
following two (Figure 1) depending on whether
or :
Fig. 1: when both are odd
Case 2: If both are even, the graph is
complete (Figure 4) or the vertices are adjacent to
either of the set of vertices
or for
different values of and (Figure 2).
(a)
(b)
Fig. 2: when both are even
Case 3: When is odd and is even, all the
vertices are either adjacent to the vertices
or
. The graph structures are similar to
the above structures discussed above.
Hence for every value of and ,
is connected.
Example 2: Consider
Since, there are 9 conjugacy classes in
and conjugacy class graph do not contain the
centre, so there are vertices in
. The orders of the conjugacy classes are
and hence the vertices will be
represented by . The graph is
shown in Figure 3.
Fig. 3:
WSEAS TRANSACTIONS on MATHEMATICS
DOI: 10.37394/23206.2024.23.48
Chinmayee Kumar, Kuntala Patra
E-ISSN: 2224-2880
462
Volume 23, 2024
Theorem 7: The diameter of is .
Proof: By definition, diameter is the maximum
distance between any two vertices in a graph,
where distance is the shortest path between any two
vertices. As seen in the previous theorem, for each
case, there exists at least two vertices that are either
adjacent to every other vertex in or
connected by a path of length and hence diameter
of is .
Theorem 8: is both Eulerian and
Hamiltonian for even values of
.
Proof: For even values of , there are conjugacy
classes of order ,
conjugacy classes of
order , conjugacy classes of order
in .
The number of conjugacy classes of being
,
there will be
conjugacy classes in
. So, the number of vertices in is
.
There are vertices of order ,
vertices of order , vertices
of order , vertices of order , vertices of
order
, vertices of order
, vertices of order
.
Since
are both even, all the vertices are
adjacent to each other, i.e., the graph is a complete
graph. Also,
being an odd
number, order of each vertex is even and equal.
Hence the graph is both Hamiltonian and Eulerian.
Example 3:
Fig. 4: (for even values of
)
Theorem 9: The clique number of
is given by:
(i) Both are odd.
(ii) Both are even.
(iii) odd, even.
Proof: Case 1: Both are odd.
The vertices with orders form a
complete subgraph for the subcases
and , which is also the maximal
subgraph for both the cases. Hence the clique
number for is the total number of
vertices of order which is
Case 2: Both are even.
We have 3 subcases here:
Subcase (i): Both
are even.
In the previous theorem, we have already proved
that the conjugacy class graph is a complete graph
which gives the clique number as
.
Subcase (ii): One of
is even and the other one
odd.
WSEAS TRANSACTIONS on MATHEMATICS
DOI: 10.37394/23206.2024.23.48
Chinmayee Kumar, Kuntala Patra
E-ISSN: 2224-2880
463
Volume 23, 2024
The vertices
form a
complete maximal subgraph of
which gives the clique number as
.
Subcase (iii): Both
are odd.
If
, then we have one complete
subgraph comprising of the vertices
which is also the maximal
subgraph of . If
, then
comprises of two complete
subgraphs with vertices and
. For both the cases, the
complete subgraph with vertices
forms the maximal complete subgraph. Hence the
result.
Case 3: even, odd.
We have 2 subcases here:
Subcase (i):
is odd.
The vertices form a maximal
complete subgraph and so the clique number is the
total number of vertices of order which
is
.
Subcase (ii):
is even.
The vertices with orders
form a
maximal complete subgraph and hence the clique
number is
.
Theorem 10: is non-planar for all
values of .
Proof: As seen in the previous theorem, for all the
cases, the clique number is at least ,
i.e, all the graphs contain a graph. Hence,
is non-planar for all values of .
Theorem 11: The chromatic number of
is given by:
(i) Both are odd.
(ii) Both are even.
(iii) odd and even.
Proof: We have three cases:
Case 1: Both are odd.
Orders of the conjugacy classes will be as follows:
,
, , ,
,
,
Clearly, the chromatic number is at least
. Since there are at least
two vertices of order and one vertex of order
and the vertices being non-adjacent to all
vertices, the chromatic number is
.
Case 2: Both are even.
There are vertices of order
vertices of order, vertices
of order , vertices of order , vertices of
order
, vertices of order
and vertices of
order
.
If
are both even, the graph is a complete graph
and so there is nothing to prove.
If one of
is even and the other odd, the
chromatic number is at least
. There are at least four vertices of
order and these vertices being non-adjacent to the
four vertices of order
, the chromatic number of
is same as the chromatic number of
WSEAS TRANSACTIONS on MATHEMATICS
DOI: 10.37394/23206.2024.23.48
Chinmayee Kumar, Kuntala Patra
E-ISSN: 2224-2880
464
Volume 23, 2024
the maximal complete subgraph of
which is
.
For odd values of both
, the maximal complete
subgraph of will be
formed by the vertices
. Since there are at least four
vertices of order , one vertex of order , two
vertices of order each, and considering the
non-adjacency of and with
,
the chromatic number is at most
.
Case 3: even, odd.
Orders of the conjugacy classes will be as follows:
,
,
, , ,
,
,
,
,
.
Clearly, for even values of
, the chromatic
number is same as the clique number which is
.
For odd values of
, the maximal complete
subgraph of will be
formed by the vertices
Since there are at least three
vertices of order , one vertex of order , two
vertices of order , one vertex of order , and
considering the non-adjacency of and with
, the chromatic number is at most
.
Theorem 12: The independence number of
is such that .
Proof: We have three cases here:
Case 1: Both are odd.
Since both are odd, the graph structure will be
either of the two types depending on whether
or . In the first case,
the vertices , and (or ) form an
independent set. While in the second case, the
vertices (or ) and (or any one of
) form an independent set.
Case 2: Both are even.
We have 3 subcases here:
Subcase (i): Both
and
are even.
In this case, all the vertices will have even order
and so of the orders of any two vertices will be
atleast . Hence, we get a complete graph
which gives the independence
number as .
Subcase (ii): One of
and
is odd and the other
even.
Suppose
is odd. In that case, the vertices
and
(or any one of
form an
independent set.
Subcase (iii): Both
and
are odd.
In this case we will have two different graph
structures depending on whether
or
. So, the independence number is at
most formed by the vertices (or ),
and
.
Case 3: is odd and is even.
We have 2 subcases here:
Subcase (i):
is even.
In this case, all the vertices have even order except
for the vertex. So, any one of the vertices
together with the vertex form an
independent set if
. If
, then the vertex together with the vertex
(or ) form an independent set.
Subcase (ii):
is odd.
The graph structures for this case are similar to the
graph structures discussed in Case 2 Subcase (iii)
and hence the independence number is at most .
4 Conclusion
In this paper, various graph parameters of
conjugate graphs and conjugacy class graphs
related to direct products of dihedral groups are
obtained. The chromatic number and independence
number of the conjugate graphs of and
the complement of the conjugate graphs and their
line graphs are computed with the help of
conjugacy classes of . The conjugacy class
graphs are found to be nonplanar connected graphs
WSEAS TRANSACTIONS on MATHEMATICS
DOI: 10.37394/23206.2024.23.48
Chinmayee Kumar, Kuntala Patra
E-ISSN: 2224-2880
465
Volume 23, 2024
with diameter . The chromatic number and clique
number of these graphs are found and a bound for
the independence number is obtained. The
conjugacy class graphs of are found to be
both Eulerian and Hamiltonian for certain values of
and .
To summarize, the conjugacy class graphs
related to the direct product of dihedral groups are
constructed using the size of conjugacy classes of
dihedral groups, which allowed us to obtain
different parameters of the concerned graphs.
The method followed herein to obtain these
results can be extended to any non-abelian group
for which the conjugacy classes can be found,
manually or with the help of a computer.
Work is in progress to compute the conjugacy
classes related to the direct product of symmetric
and alternating groups and thereby obtain the graph
structures for these groups.
5 Future Study
The generalized conjugacy class graphs of dihedral
groups and generalized quaternion groups and their
related direct product graphs can be found. Also,
the partition dimension of conjugacy class graphs
related to the above-mentioned groups will be an
interesting topic of further research, and bounds for
partition dimension can be established, if it exists.
References:
[1] E. A. Bertram, M. Herzog, A. Mann, On a
graph related to conjugacy classes of groups,
Bull. London Math. Soc., Vol.22, No.6, 1990,
pp.569-575.
[2] A. Erfanian and B. Tolue, Conjugate Graphs
of finite groups, Discrete Mathematics,
Algorithms and Applications, Vol.4, No.2,
2012, pp. 1250035.
[3] Zulkarnain, N. H. Sarmin, A. H. B. M. Noor,
On the conjugate graphs of finite p-groups,
Malaysian Journal of Fundamental and
Applied Sciences, Vol. 13, No.2, 2017, pp.
100-102.
[4] M. Bianchi, M. Herzog, E. Pacifici, G.
Saffirio, On the regularity of a graph related
to conjugacy classes of groups, European
Journal of Combinatorics, Vol.13, No.7,
2012, pp.1402-1407,
https://doi.org/10.1016/j.ejc.2012.03.005.
[5] N. H. Sarmin, N. H. Bilhikmah, S. M. S.
Omer, A. H. B. M. Noor, The Conjugacy
classes, Conjugate graph and Conjugacy
class graph of some finite Metacyclic 2-
groups, Menemui Matematik (Discovering
Mathematics), Vol.38, No.1, 2016, pp.1-12.
[6] S. N. A. Zamri, N. H. Sarmin, M. A. El-
Sanfaz, The conjugate and generalized
conjugacy class graphs for metacyclic 3-
groups and metacyclic 5-groups, AIP
Conference Proceedings, Vol.1830, No.1,
2017, pp.07001,
https://doi.org/10.1063/1.4980964.
[7] H. Alolaiyan, A. Yousaf, M. Ameer and A.
Razaq, Non-Conjugate Graphs Associated
with Finite Groups, IEEE Access, Vol.7,
2019, pp.122849-122853. doi:
10.1109/ACCESS.2019.2938083.
[8] Narsingh Deo, Graph Theory with
Applications to Engineering and Computer
Science, Prentice-Hall, India, 1979.
[9] Frank Harary, Graph Theory, Narosa
Publishing House, 2001.
[10] C. Kumar, K. Patra K, Conjugacy Class
Graph of Some Non-Abelian Groups,
Contemporary Mathematics, Vol.5, No.1,
2024, pp.430-445,
https://doi.org/10.37256/cm.5120243875.
Contribution of Individual Authors to the
Creation of a Scientific Article (Ghostwriting
Policy)
On behalf of all the authors, the corresponding
author states that the manuscript is an original work
of the authors and all authors made a significant
contribution to this paper.
Sources of Funding for Research Presented in a
Scientific Article or Scientific Article Itself
The authors declare that there is no conflict of
interest.
Conflict of Interest
No funding was received for conducting this study.
This manuscript has not been submitted for
publication elsewhere and has not been published
in any other journal.
Creative Commons Attribution License 4.0
(Attribution 4.0 International, CC BY 4.0)
This article is published under the terms of the
Creative Commons Attribution License 4.0
https://creativecommons.org/licenses/by/4.0/deed.e
n_US
WSEAS TRANSACTIONS on MATHEMATICS
DOI: 10.37394/23206.2024.23.48
Chinmayee Kumar, Kuntala Patra
E-ISSN: 2224-2880
466
Volume 23, 2024
