Groups with maximum vertex degree commuting graphs

Abstract

Let G be a finite non-abelian group and Z(G) be its center. We associate a commuting graph $\Gamma (G)$ to G, whose vertex set is $G\setminus Z(G)$ and two distinct vertices are adjacent if they commute. In this paper we prove that the set of all non-abelian groups whose commuting graph has maximum vertex degree bounded above by a fixed $k \in {\mathbb {N}}$ is finite. Also, we characterize all groups for which the associated commuting graphs have maximum vertex degree at most 4.

1 Introduction

Let G be a finite non-abelian group and Z(G) be its center. The commuting graph of G, denoted by $\Gamma (G)$, is the graph whose vertex set is $G\setminus Z(G)$ and two distinct vertices x and y are joined by an edge if $xy=yx$. The idea of commuting graphs can be traced back to the works of Brauer and Fowler in [6] and Fischer in [10] and Kegel and Gruenberg in [12]. The commuting graph has been studied in several contexts, for example, see [1, 7, 16,17,18]. Also, it would be interesting to compare our results with Bates et al. [2,3,4,5] where they consider the commuting involution graph for sporadic, Coxeter, symmetric and special linear groups respectively. We now state one of our main result of this paper:

Theorem 1.1

Let $\mathcal{S}\mathcal{F}(k)$ be a set of all finite non-abelian groups G whose commuting graph $\Gamma (G)$ has maximum vertex degree $<k$, then the set $\mathcal{S}\mathcal{F}(k)$ is finite for each $k \in {\mathbb {N}}$.

The study of maximum vertex degree of $\Gamma (G)$ can be thought of as a special case of star freeness of $\Gamma (G)$ which we will now define. The complete bipartite graph $\textrm{K}_{1,k}$ is said to be a k-star graph. The graph $\Gamma (G)$ is k-star free if the k-star graph is not an induced subgraph of $\Gamma (G)$. Suppose $\Gamma (G)$ has a vertex g of degree k. Let $g_1,g_2,\dots ,g_k$ be the neighbors of g in $\Gamma (G)$. We observe that the vertices $g,g_1,\dots ,g_k$ form a k-star (not necessarily induced) in $\Gamma (G)$ that’s connect to the maximum vertex degree. One motivation to study k-star free graphs comes from the claw-free graphs (for $k=3$), which is one of the most extensively studied objects among k-stars. For example, see [8, 9, 11] just to name a few. Classifying the groups satisfying a certain condition on the associated graphs have always been an interesting problem, for example, in [15], groups with triangle-free commuting conjugacy class graphs are classified. Also, in connection with star freeness, Xuanlong et al. studied star-free non-cyclic graphs of finite groups. They classified all finite non-cyclic groups whose non-cyclic graphs are k-star free for $3 \le k \le 6$ (see [14]).

In general, classifying commuting graphs which are k-star free is hard. So this motivates us to embark on the classification of maximum vertex degree commuting graphs with the hope that the actual k-star freeness could be achieved. Now, a natural question that arises in this context is that for what groups G does $\Gamma (G)$ has maximum vertex degree k? In an attempt to answer this question, we prove the following necessary and sufficient conditions (for $2\le k\le 4$):

Theorem 1.2

The commuting graph $\Gamma (G)$ has maximum vertex degree $<5$ if and only if G is isomorphic to one of the following groups: $S_3$, $D_{10}$, $A_4$, $\textrm{GA}(1,5)$, $A_5$; $D_8$, $Q_8$; $D_{12}$, $C_3\rtimes C_4$, $\textrm{SL}(2,3)$; $(C_4\times C_2)\rtimes C_2$, $C_4\rtimes C_4$, $C_8\rtimes C_2$, $D_8\times C_2$, $Q_8\times C_2$ and $D_8\circ _{C_2}C_4$, where $C_n$ denotes the cyclic group of order n and $D_8\circ _{C_2}C_4$ denotes the central product of $D_8$ and $C_4$ over $C_2$.

As a corollary, we have the following result:

Corollary 1.3

The commuting graph $\Gamma (G)$ has maximum vertex degree $<4$ if and only if G is isomorphic to one of the following groups: $S_3$, $D_{10}$, $A_4$, $\textrm{GA}(1,5)$, $A_5$; $D_8$, $Q_8$; $D_{12}$, $C_3\rtimes C_4$, $\textrm{SL}(2,3)$; $(C_4\times C_2)\rtimes C_2$, $C_4\rtimes C_4$, $C_8\rtimes C_2$, $D_8\times C_2$, $Q_8\times C_2$ and $D_8\circ _{C_2}C_4$, where $C_n$ denotes the cyclic group of order n.

Remark 1.4

From the above theorem and its corollary we have the following surprising fact: The commuting graph $\Gamma (G)$ has maximum vertex degree $<5$ if and only if it has maximum vertex degree $<4$. We observe that, this fact already follows from Lemmas 4.2, 4.10 and 4.11.

Also, we get the complete classification of groups whose commuting graph $\Gamma (G)$ has maximum vertex degree $<3$:

Corollary 1.5

The commuting graph $\Gamma (G)$ has maximum vertex degree at most 2 if and only if G is isomorphic to one of the following groups: $S_3$, $A_4$, $D_8$ and $Q_8$. This result can be readily verified using the following diagram.

Fig. 1

Commuting graphs

2 Preliminaries

In this section, we fix some notations and terminologies which will be used throughout this paper. Unless otherwise specified, we will always assume that G is a non-abelian finite group. The set of all non-central elements in G will be denoted by $\mathcal{N}\mathcal{C}(G)$. For a subset $A \subset G$, we denote the centralizer of A in G by $C_{G}(A)$. If $A = \{x\}$, we write $C_{G}(x)$ in short.

Lemma 2.1

Let G be a group and x be an element of $\mathcal{N}\mathcal{C}(G)$ such that $|C_G(x)|\ge (k+1) + |Z(G)|$, then $\Gamma (G)$ has k-star as its subgraph. In particular, $\Gamma (G)$ has maximum vertex degree $<k$ if and only if $|C_G(x)| \le k+ |Z(G)|$ for all $x \in \mathcal{N}\mathcal{C}(G)$.

Proof

From the given condition, $C_G(x)$ contains at least k non-central elements, say $\{a_1,\ldots ,a_{k}\}$, that are different from x. Then it is clear that the vertices $\{x,a_1,\ldots ,a_{k}\}$ gives rise to a k-star subgraph in $\Gamma (G)$. $\square$

Proposition 2.2

Let G be a finite group of order n with the trivial center. If $|C_G(x)| = m$ for all $x (\ne e) \in G$, then G is trivial.

Proof

By class equation, we have, $n = 1 + k\frac{n}{m}$ for some $k \in {\mathbb {Z}}_{+}$. Simplifying this we get $n = \frac{m}{m-k} \in \mathbb {N.}$ Since m|n, $n = mt = \frac{m}{m-k} \in {\mathbb {N}}$ for some $t \in {\mathbb {N}}$. This implies that $t(m-k) = 1$. Note that $t \in {\mathbb {N}}$ so $t = m-k = 1$. This shows that $m = n=1$ and the proof follows. $\square$

Proposition 2.3

Suppose G is a finite group such that $\Gamma (G)$ has maximum vertex degree $<k$ then the center $|Z(G)|< k$.

Proof

Let $x\in \mathcal{N}\mathcal{C}(G)$. By Lemma 2.1, we have $|C_G(x)|-|Z(G)|\le k$ as $\Gamma (G)$ has maximum vertex degree $<k$. Now, we have $|C_G(x)| > |Z(G)|$ and also, we have |Z(G)| divides $|C_G(x)|$, therefore $|C_G(x)|=|Z(G)|t$ for some $t\, (\ne 1)\in {\mathbb {N}}$. Thus $|Z(G)|(t-1)\le k$. Hence the result. $\square$

Let us recall a classical result by E. Landau (1903) which will be used in the proof of the following theorem.

Theorem 2.4

[13] For a given natural number n there are only finitely many finite groups, up to isomorphism, having n conjugacy classes.

3 Proof of Theorem 1.1

Let G be a group such that $\Gamma (G)$ has maximum vertex degree $<k$. By Lemma  2.1, we have $|C_G(x)| \le k + |Z(G)|$ for all $x \in \mathcal{N}\mathcal{C}(G)$. In view of Proposition 2.3, we have $|C_G(x)| < 2k$ for all $x \in \mathcal{N}\mathcal{C}(G)$. First, we claim that the number of distinct centralizer sizes in G is bounded. Let ${\mathcal {S}}=\{n_1,n_2,\dots ,n_m\}$ be the set of distinct sizes of centralizers in G, given any such set we claim that m is bounded by a fixed constant. Let the class equation of G be

$$\begin{aligned} |G| = \Big (\underbrace{\frac{|G|}{n_1} + \cdots + \frac{|G|}{n_1}}_{r_1}\Big ) +\Big (\underbrace{\frac{|G|}{n_2} + \cdots + \frac{|G|}{n_2}}_{r_2}\Big ) + \cdots + \Big (\underbrace{\frac{|G|}{n_m} + \cdots + \frac{|G|}{n_m}}_{r_m}\Big ). \end{aligned}$$

Therefore we have

$$\begin{aligned} 1 = \Big (\underbrace{\frac{1}{n_1} + \cdots + \frac{1}{n_1}}_{r_1}\Big ) + \Big (\underbrace{\frac{1}{n_2} + \cdots + \frac{1}{n_2}}_{r_2}\Big ) + \cdots + \Big (\underbrace{\frac{1}{n_m} + \cdots + \frac{1}{n_m}}_{r_m}\Big ), \end{aligned}$$

It is given that $n_i< 2k$ for all $1 \le i \le m$ and hence $\frac{1}{n_i}> \frac{1}{2k}$ for all $1 \le i \le m$. We have

$$\begin{aligned}1 = \frac{r_1}{n_1}+\frac{r_2}{n_2}+\cdots +\frac{r_m}{n_m}> \frac{r_1+r_2+\cdots +r_m}{2k} \ge \frac{m}{2k}.\end{aligned}$$

Hence for a fixed k, m cannot be arbitrarily large and we assume this number is bounded by $s=2k$. This shows that the cardinality of the set

$$\begin{aligned} {\mathcal {C}}(k) = \{\{n_1,n_2,\ldots ,n_m\} \mid n_1<n_2<\cdots <n_m \}, \end{aligned}$$

is finite as the set ${\mathcal {S}}$ can be identified with a subset of $[1,2k]^s$, where $n_1,n_2,\ldots ,n_m$ are the distinct sizes of the centralizers of G. Again, by Proposition 2.3, we have $|Z(G)|< k$ as $\Gamma (G)$ has maximum vertex degree $<k$. Thus the claim.

Let ${\textbf{n}} = \{n_1,n_2,\dots ,n_m\}$ be a set of positive integers satisfying $n_1<n_2<\cdots <n_m$ for some m. We will show that there are finitely many groups G for which ${\textbf{n}} \in {\mathcal {C}}(k)$ . Let ${\mathcal {G}}({\textbf{n}})$ denote the set of all groups for which ${\textbf{n}} \in {\mathcal {C}}(k)$ and let $G \in {\mathcal {G}}({\textbf{n}})$. Let ${\mathcal {S}}({\textbf{n}})$ be the set of all positive integer solutions to the following equation

$$\begin{aligned} 1 = \frac{x_1}{n_1} + \frac{x_2}{n_2} + \cdots + \frac{x_m}{n_m}. \end{aligned}$$

The above discussion shows that every $G \in {\mathcal {G}}({\textbf{n}})$ gives rise to a solution of the above equation. Hence we have a well-defined map $\chi : {\mathcal {G}}({\textbf{n}}) \rightarrow {\mathcal {S}}({\textbf{n}})$. Clearly, ${\mathcal {S}}({\textbf{n}})$ is finite as each $n_i$ cannot be arbitrarily large for all $1\le i\le m$.

Let $\{r_1,r_2,\dots ,r_m\} \in {\mathcal {S}}({\textbf{n}})$ and consider $l = \sum _{i=1}^{m} r_i$. Then, by Theorem 2.4, the set of all finite groups with l number of conjugacy classes is finite. Therefore for each $\{r_1,r_2,\dots ,r_m\} \in {\mathcal {S}}(\textbf{n})$ has finitely many pre-images (can be empty also). i.e., all the fibers of the map $\chi$ are finite which proves that the set ${\mathcal {G}}({\textbf {n}})$ is finite.

This completes the proof. $\square$

4 Star free commuting graphs

In this section, we give a complete classification of groups G whose commuting graphs $\Gamma (G)$ has maximum vertex degree is k for $1\le k \le 4$. The classification is given by considering the following two cases separately.

4.1 Trivial center case

In this case, by Lemma 2.1 we have, $\Gamma (G)$ has maximum vertex degree $<5$ if and only if $|C_G(x)| \le 6$ for all $x \,(\ne e) \in G$. We shall deal case by case.

Remark 4.1

Let G be a group with trivial center. If $|C_G(x)| = 2, 3, 4, 5\text { or } 6$ for all $x(\ne e)\in G,$ then by Proposition 2.2, G is the trivial group and hence $\Gamma (G)$ has maximum vertex degree $<5$. Thus, we don’t need to consider these cases.

Therefore we remain with the following cases:

$$\begin{aligned} |C_G(x)|&= 2 \text { or } 3 \, \forall \, x \, (\ne e)\, \in G.\end{aligned}$$

(4.1)

$$\begin{aligned} |C_G(x)|&= 2 \text { or } 4 \, \forall \, x \, (\ne e)\, \in G.\end{aligned}$$

(4.2)

$$\begin{aligned} |C_G(x)|&= 2 \text { or } 5 \, \forall \, x \, (\ne e)\, \in G.\end{aligned}$$

(4.3)

$$\begin{aligned} |C_G(x)|&= 2 \text { or } 6 \, \forall \, x \, (\ne e)\, \in G.\end{aligned}$$

(4.4)

$$\begin{aligned} |C_G(x)|&= 3 \text { or } 4 \, \forall \, x \, (\ne e)\, \in G.\end{aligned}$$

(4.5)

$$\begin{aligned} |C_G(x)|&= 3 \text { or } 5 \, \forall \, x \, (\ne e)\, \in G.\end{aligned}$$

(4.6)

$$\begin{aligned} |C_G(x)|&= 3 \text { or } 6 \, \forall \, x \, (\ne e)\, \in G.\end{aligned}$$

(4.7)

$$\begin{aligned} |C_G(x)|&= 4 \text { or } 5 \, \forall \, x \, (\ne e)\, \in G.\end{aligned}$$

(4.8)

$$\begin{aligned} |C_G(x)|&= 4 \text { or } 6 \, \forall \, x \, (\ne e)\, \in G.\end{aligned}$$

(4.9)

$$\begin{aligned} |C_G(x)|&= 5 \text { or } 6 \, \forall \, x \, (\ne e)\, \in G.\end{aligned}$$

(4.10)

$$\begin{aligned} |C_G(x)|&= 2 \text { or } 3 \text { or } 4 \, \forall \, x \, (\ne e)\, \in G.\end{aligned}$$

(4.11)

$$\begin{aligned} |C_G(x)|&= 2 \text { or } 3 \text { or } 5 \, \forall \, x \, (\ne e)\, \in G.\end{aligned}$$

(4.12)

$$\begin{aligned} |C_G(x)|&= 2 \text { or } 3 \text { or } 6 \, \forall \, x \, (\ne e)\, \in G.\end{aligned}$$

(4.13)

$$\begin{aligned} |C_G(x)|&= 2 \text { or } 4 \text { or } 5 \, \forall \, x \, (\ne e)\, \in G.\end{aligned}$$

(4.14)

$$\begin{aligned} |C_G(x)|&= 2 \text { or } 4 \text { or } 6 \, \forall \, x \, (\ne e)\, \in G.\end{aligned}$$

(4.15)

$$\begin{aligned} |C_G(x)|&= 2 \text { or } 5 \text { or } 6 \, \forall \, x \, (\ne e)\, \in G.\end{aligned}$$

(4.16)

$$\begin{aligned} |C_G(x)|&= 3 \text { or } 4 \text { or } 5 \, \forall \, x \, (\ne e)\, \in G.\end{aligned}$$

(4.17)

$$\begin{aligned} |C_G(x)|&= 3 \text { or } 4 \text { or } 6 \, \forall \, x \, (\ne e)\, \in G.\end{aligned}$$

(4.18)

$$\begin{aligned} |C_G(x)|&= 3 \text { or } 5 \text { or } 6 \, \forall \, x \, (\ne e)\, \in G.\end{aligned}$$

(4.19)

$$\begin{aligned} |C_G(x)|&= 4 \text { or } 5 \text { or } 6 \, \forall \, x \, (\ne e)\, \in G.\end{aligned}$$

(4.20)

$$\begin{aligned} |C_G(x)|&= 2 \text { or } 3 \text { or } 4 \text { or } 5\, \forall \, x \, (\ne e)\, \in G.\end{aligned}$$

(4.21)

$$\begin{aligned} |C_G(x)|&= 2 \text { or } 3 \text { or } 4 \text { or } 6\, \forall \, x \, (\ne e)\, \in G.\end{aligned}$$

(4.22)

$$\begin{aligned} |C_G(x)|&= 2 \text { or } 3 \text { or } 5 \text { or } 6\, \forall \, x \, (\ne e)\, \in G.\end{aligned}$$

(4.23)

$$\begin{aligned} |C_G(x)|&= 2 \text { or } 4 \text { or } 5 \text { or } 6\, \forall \, x \, (\ne e)\, \in G.\end{aligned}$$

(4.24)

$$\begin{aligned} |C_G(x)|&= 3 \text { or } 4 \text { or } 5 \text { or } 6\, \forall \, x \, (\ne e)\, \in G.\end{aligned}$$

(4.25)

$$\begin{aligned} |C_G(x)|&= 2 \text { or } 3 \text { or } 4 \text { or } 5 \text { or } 6\, \forall \, x \, (\ne e)\, \in G. \end{aligned}$$

(4.26)

Lemma 4.2

There is no non-abelian group G of order n with trivial center which satisfies Equations (4.2), (4.4), (4.6), (4.7), (4.9), (4.10), (4.11), (4.12), (4.13), (4.14), (4.15), (4.16), (4.18), (4.19), (4.20), (4.21), (4.22), (4.23), (4.24), (4.25), and (4.26).

Proof

The proof of this lemma follows from the class equation. Here we are going to prove for two equations to see how it works. Also, this simple (and elegant) but powerful argument has been used several times in our paper. From Equation (4.2), we have $n-1 = k_1 \frac{n}{2} + k_2 \frac{n}{4}$. Clearly, $k_1 = 1$, hence we have, $\frac{n-2}{2} = \frac{nk_2}{4}$. Therefore $n(2-k_2) = 4$ with $k_2 \in {\mathbb {N}}$. Hence $n = 4$ and this case is not possible.

From Equation (4.11), we have $n-1 = k_1\frac{n}{2}+k_2\frac{n}{3}+k_3\frac{n}{4}$. Clearly, $k_1 = 1$ so we have $\frac{n-2}{2} = k_2\frac{n}{3}+k_3\frac{n}{4}$. Note that $1 \le k_2 \le 2$. If $k_2 = 1$, then we have $\frac{n-2}{2} = \frac{n}{3}+k_3\frac{n}{4}$. Therefore $n(2-3k_3) = 12$, which is not possible as $k_3, n \in {\mathbb {N}}$. If $k_2 = 2$, then we have $\frac{n-2}{2} = 2\frac{n}{3}+k_3\frac{n}{4}$. Hence $\frac{-n-6}{6} = \frac{nk_3}{4}$, which is absurd. The remaining cases are similar. $\square$

Lemma 4.3

Let G be a finite group of order n with the trivial center and satisfies Equation (4.1), then G is isomorphic to $S_3$.

Proof

By class equation we have $n-1 = k_1\frac{n}{2} + k_2 \frac{n}{3}$ for some $k_1, k_2 \in {\mathbb {N}}$. Clearly, $k_1 = 1$ and thus we have $\frac{n}{2}-1 = k_2 \frac{n}{3}$. This implies that $n(3-2k_2) = 6$, where $n, k_2 \in {\mathbb {N}}$. Hence $n = 6$ and the result follows. $\square$

Lemma 4.4

Let G be a finite group of order n with the trivial center and satisfies Equation (4.3), then G is isomorphic to $D_{10}$.

Proof

Let G be a group of order n which satisfies the given assumptions. In this case, we have $n-1 = k_1 \frac{n}{2} + k_2 \frac{n}{5}$. Clearly, $k_1 = 1$. Thus we have $\frac{n-2}{2} = \frac{k_2 n}{5}$. Therefore $n(5-2k_2) = 10$ where $k_2 \in {\mathbb {N}}$. Hence $k_2 = 2$ and $n = 10$. Now $D_{10}$ is the only non-abelian group of order 10 along with the class equation $1+2+2+5$. Hence G is isomorphic to $D_{10}$. $\square$

Lemma 4.5

Let G be a finite group of order n with the trivial center and satisfies Equation (4.5), then G is isomorphic to $A_4$.

Proof

From Equation (4.5), we have, $n-1 = k_1\frac{n}{3}+k_2\frac{n}{4}$. Clearly, $1 \le k_1 \le 2$. If $k_1 =1$, then we have $n-1 = \frac{n}{3}+k_2\frac{n}{4}$. Thus $n(8-3k_2) = 12$, where $n, k_2 \in {\mathbb {N}}$. Therefore $k_2 = 2$ and $n=6$. Hence $G \cong S_3$ which is clearly not possible. If $k_1 =2$, then we have $n-1 = 2\frac{n}{3}+k_2\frac{n}{4}$. Thus $n(4-3k_2) = 12$ with $n, k_2 \in {\mathbb {N}}$. Therefore $k_2 = 1 \text { and } n=12$. Clearly, $D_{12}$ and $C_3\rtimes C_4$ are not satisfying the given assumptions but $A_4$ does. Hence $G \cong A_4$. $\square$

Lemma 4.6

The general affine group of order 1 over ${\mathbb {F}}_5$, denoted by $\textrm{GA}(1,5)$, is the only group that satisfies Equation (4.8).

Proof

Follows from the class equation ($20=1+4+5+5+5$). $\square$

Lemma 4.7

The alternating group $A_5$ is the only group which satisfies Equation (4.17).

Proof

Follows from the class equation ($60=1+12+12+15+20$). $\square$

4.2 Non-trivial center case

In this case, by Lemma 2.1, we have $\Gamma (G)$ has maximum vertex degree $<k$ if and only if $|C_G(x)| \le k + |Z(G)|$ for all $x \in \mathcal{N}\mathcal{C}(G)$. Again by Proposition 2.3, we have $|Z(G)|< k$. By our assumption of this section, we have $|Z(G)| \ge 2$, i.e., $2\le |Z(G)|<k$. Now we shall deal case by case for $k\le 5$.

Lemma 4.8

Let G be a group with non-trivial center such that $\Gamma (G)$ has maximum vertex degree $<3$, then $|C_G(x)|=4$ for x in $\mathcal{N}\mathcal{C}(G)$.

Proof

Let $x\in \mathcal{N}\mathcal{C}(G)$ then from Lemma  2.1, we have $|C_G(x)|-|Z(G)|\le 3$. Now we have $|Z(G)|=2$, then $|C_G(x)|=4$, as |Z(G)| divides $|C_G(x)|$ and $Z(G)<C_G(x)$. $\square$

Lemma 4.9

Let G be a finite group of order n with non-trivial center such that $\Gamma (G)$ has maximum vertex degree $<3$, then G is isomorphic to $Q_8$ or $D_8$.

Proof

By Lemma 4.8, we have $|C_G(x)| = 4$ for all $x \in \mathcal{N}\mathcal{C}(G)$. Now by class equation, $n-2 = k \frac{n}{4}$ for some $k \in {\mathbb {N}}$. This implies that $n = \frac{8}{4-k}$ for some $k \in {\mathbb {N}}$. Thus $n = 4$ or 8. Since we are interested in non-abelian groups, we have $n = 8$. Note that both $Q_8$ and $D_8$ have conjugacy class sizes 1, 1, 2, 2, 2 respectively. Now from the assumptions, it is clear that $G \cong Q_8$ or $D_8$. $\square$

Lemma 4.10

Let G be a group with non-trivial center such that $\Gamma (G)$ has maximum vertex degree $<4$, then exactly one of the following holds: $|C_G(x)|=4$ or $|C_G(x)|=6$ or $|C_G(x)|=4 \text { or } 6$ for all $x \in \mathcal{N}\mathcal{C}(G)$.

Proof

Let $x\in \mathcal{N}\mathcal{C}(G)$ then from Lemma  2.1, we have $|C_G(x)|-|Z(G)|\le 4$. There are two possibilities of the order of the center. If $|Z(G)|=2$, then we have $|C_G(x)|=4$ or $|C_G(x)|=6$ or both, as |Z(G)| divides $|C_G(x)|$ and $Z(G)<C_G(x)$. Now by similar argument if $|Z(G)|=3$ then we have $|C_G(x)|=6$. $\square$

Lemma 4.11

Let G be a group with non-trivial center such that $\Gamma (G)$ has maximum vertex degrre $<5$, then exactly one of the following holds: $|C_G(x)|=4$ or $|C_G(x)|=6$ or $|C_G(x)|=8$ or $|C_G(x)|=4 \text { or } 6$ for all $x \in \mathcal{N}\mathcal{C}(G)$.

Proof

Let $x\in \mathcal{N}\mathcal{C}(G)$ then we have $|C_G(x)|-|Z(G)|\le 5$ (by Lemma  2.1). There are three possibilities of the order of the center. If $|Z(G)|=2$, then we have $|C_G(x)|=4$ or $|C_G(x)|=6$ or both, as |Z(G)| divides $|C_G(x)|$ and $Z(G)<C_G(x)$. Now by similar argument if $|Z(G)|=3$, then we have $|C_G(x)|=6$. Again if $|Z(G)|=4$ then by a similar argument, we have $|C_G(x)|=8$. $\square$

Remark 4.12

There is no group G of order n with $|Z(G)|=2$ and $|C_G(x)|=6$ for all $x\in \mathcal{N}\mathcal{C}(G)$ such that $\Gamma (G)$ has maximum vertex degree $<5$ follows from the class equation.

Lemma 4.13

Let G be a group of order n with $|Z(G)|=2$ such that it has centralizer sizes both 4 and 6, then G is isomorphic to $D_{12}$ or $C_3\rtimes C_4$ or $\textrm{SL}(2,3)$.

Proof

The proof follows from the class equation computations (cf. Lemma 4.10 and Lemma 4.11). $\square$

Lemma 4.14

There is no group G of order n with $|Z(G)|=3$ such that $\Gamma (G)$ has maximum vertex degree $<5$.

Proof

In view of Lemma 2.1, we have $|C_G(x)|\le 8$ for all $x \in \mathcal{N}\mathcal{C}(G)$. Now we have $Z(G)<C_G(x)$ and |Z(G)| divides $|C_G(x)|$, therefore $|C_G(x)|=6$ for all $x\in \mathcal{N}\mathcal{C}(G)$. Now by using class equation, $n-3 = k \frac{n}{6}$ for some $k \in {\mathbb {N}}$. This implies that $n = \frac{18}{6-k}$ for some $k \in {\mathbb {N}}$. Then $n = 6, 9$ or 18. Since we are interested in non-abelian groups, we have $n = 6$ or 18. Clearly, $n \ne 6$ as $S_3$ has trivial center. So we remain with the non-abelian group of order 18 with order of the center is 3. As we know from the classification of finite groups of order 18 there are no such groups with this property. Hence there is no group satisfying the said property. $\square$

Lemma 4.15

Let G be a group of order n with $|Z(G)|=4$ and $|C_G(x)|=8$ for all $x\in \mathcal{N}\mathcal{C}(G)$, then G is isomorphic to $(C_4\times C_2)\rtimes C_2$ or $C_4\rtimes C_4$ or $C_8\rtimes C_2$ or $D_8\times C_2$ or $Q_8\times C_2$, or $D_8\circ _{C_2}C_4$, where $C_n$ is the cyclic group of order n and $\circ _{C_2}$ denotes the central product over $C_2$.

Proof

The result now follows from the similar computations as above using class equation (cf. Lemma 4.10 and Lemma 4.11). $\square$

4.3 Proof of Theorem 1.2

Let G be a group such that the commuting graph $\Gamma (G)$ have maximum vertex degree $<5$. On one hand, if G has trivial center then there are 5 possibilities of G follows from Lemmas 4.3, 4.4, 4.5, 4.6 and 4.7. On the other hand, if G has non-trivial center then there are 11 such possibilities of G which is the following: there are only two groups $D_8$ and $Q_8$ with center of size 2 and centralizers have order 4 for all non-central elements, respectively such that the commuting graph has maximum vertex degree $<5$ (follows from Lemma 4.9). There are only three groups $D_{12}$, $C_3\rtimes C_4$ and $\textrm{SL}(2,3)$ with the center of order 2 and centralizers have order both 4 and 6 for all non-central elements respectively such that the commuting graph has maximum vertex degree $<5$ (by Lemma  4.13). Let G be a group with $|Z(G)|=4$ and $|C_G(x)|=8$ for all $x\in \mathcal{N}\mathcal{C}(G)$, then G has order 16 and there are six of them satisfying the given assumptions and which follows from Lemma 4.15.

Conversely, if G is one of the given group in the theorem then it’s commuting graph $\Gamma (G)$ have maximum vertex degree $<5$ (cf. Figure 1 and Figure 2).

This completes the proof. $\square$

Let G be a group such that $\Gamma (G)$ has maximum vertex degree $<2$, then $\Gamma (G)$ is a disjoint union of paths of length 1 and isolated vertices.

Corollary 4.16

The only finite non-abelian groups whose commuting graphs have maximum vertex degree $<2$ are: $S_3, D_8, Q_8$.

Remark 4.17

• (1) There is no group G of order n with $|Z(G)|=3$ such that $\Gamma (G)$ has maximum vertex degree $<4$ follows from Lemma 4.14.

• (2) There is no group G of order n with $|Z(G)|=2$ and $|C_G(x)|=6$ for all $x\in \mathcal{N}\mathcal{C}(G)$ such that $\Gamma (G)$ has maximum vertex degree $<4$ follows from the class equation.

4.4 Proof of Corollary 1.3

Follows from Theorem 1.2 and Remark 4.17. $\square$

4.5 Proof of Corollary 1.5

Follows from Lemma 4.5 and Corollary 4.16 (cf. Figure 1). $\square$

Fig. 2

Commuting graphs

5 Dihedral groups and star-freeness

In this section, we give an example of a group, namely, dihedral group $D_{2n}$ of order 2n and its star-freeness. Every finite non-abelian group G belongs to $\mathcal{S}\mathcal{F}(k)$ for some k. We have $\mathcal{S}\mathcal{F}(1) \subseteq \cdots \subseteq \mathcal{S}\mathcal{F}(k) \subseteq \cdots$. We show that all these inclusions are strict (Propositions 5.2 and 5.4). Define $\mathcal{S}\mathcal{F}$ to be the limit of the above inclusions. Clearly, $\mathcal{S}\mathcal{F}$ is equal to the set of all non-abelian groups.

Definition 5.1

(Vertex degree type (k)) A group G is said to be of vertex degree type (k) if the commuting graph $\Gamma (G)$ has maximum vertex degree $<k$.

If G is a group of vertex degree type (k) then G is vertex degree type ($k+1$). In view of this simple observation, we define the star number, denoted by $\textrm{S}(G)$, to be the smallest k such that G is of vertex degree type (k).

5.1 Trivial center case

If G has trivial center then we have, $G \in \mathcal{S}\mathcal{F}(k)$ if and only if $|C_G(x)|<(k+1)+1$ for all $x \in \mathcal{N}\mathcal{C}(G)$. More precisely, the size of the largest non-central centralizer of G should be strictly less than $k+2$.

In this case, n is odd and the class equation of $D_{2n}$ is given by

$$\begin{aligned} 2n-1 = \Big (\frac{n-1}{2}\Big ) \frac{2n}{n} + \Big (1\Big ) \frac{2n}{2}. \end{aligned}$$

So the size of the largest centralizer in $D_{2n}$ is n and hence $D_{2n} \in \mathcal{S}\mathcal{F}(k)$ if and only if $k > n - 2$. We record this as:

Proposition 5.2

Assume n is odd, then $D_{2n} \in \mathcal{S}\mathcal{F}(k)$ for all $k \ge n-1$ and $S(D_{2n}) = n-1$.

Remark 5.3

Let $k_1$ and $k_2$ be two consecutive odd numbers, then $D_{2k_2} \in \mathcal{S}\mathcal{F}(k_1+1)$ and $D_{2k_2} \notin \mathcal{S}\mathcal{F}(k_1)$.

5.2 Non-trivial center case

If G has non-trivial center then we have, $G \in \mathcal{S}\mathcal{F}(k)$ if and only if $|C_G(x)|<(k+1)+|Z(G)|$ for all $x \in \mathcal{N}\mathcal{C}(G)$. More precisely, the size of the largest non-central centralizer of G should be strictly less than $k+1+|Z(G)|$.

In this case, n is even and the class equation of $D_{2n}$ is given by

$$\begin{aligned} 2n-2 = \Big (\frac{n-2}{2}\Big ) \frac{2n}{n} + \Big (2\Big ) \frac{2n}{4}. \end{aligned}$$

So the size of the largest centralizer in $D_{2n}$ is n and $|Z(G)| = 2$. Hence $D_{2n} \in \mathcal{S}\mathcal{F}(k)$ if and only if $k > n - 3$. We record this as:

Proposition 5.4

Assume n is even, then $D_{2n} \in \mathcal{S}\mathcal{F}(k)$ for all $k \ge n-2$ and $S(D_{2n}) = n-2$.

Remark 5.5

Let $k_1$ and $k_2$ be two consecutive even numbers, then $D_{2k_2} \in \mathcal{S}\mathcal{F}(k_1)$ and $D_{2k_2} \notin \mathcal{S}\mathcal{F}(k_1-1)$.