Conjugacy Graphs

Abstract

Let $\mathrm{\Gamma }$ be a finite group and let $X$ be a subset of $\mathrm{\Gamma }$ such that $X^{-1}=X$ and $1\notin X$. The conjugacy graph $\text{Con}(\mathrm{\Gamma };X)$ has vertex set $\mathrm{\Gamma }$ and two vertices $g,h\in \mathrm{\Gamma }$ are adjacent in $\text{Con}(\mathrm{\Gamma };X)$ if and only if there exists $x\in X$ with $g=xh{x}^{-1}$. The components of a conjugacy graph partition the vertices into conjugacy classes (with respect to $X$) of the group. Sufficient conditions for a conjugacy graph to have either vertex-transitive or arc-transitive components are provided. It is also shown that every Cayley graph is the component of some conjugacy graph.