The non-commuting, non-generating graph
of a nilpotent group

A number of graphs have been defined on the set of elements of a group, aiming to capture some aspect of the group structure in graph-theoretic terms. Prominent among these is the commuting graph, in which two elements are joined by an edge if and only if they commute. This graph is trivially connected with diameter at most $2$, since the identity is connected to all other vertices. However, if we remove the central elements of the group, then the commuting graph is no longer obviously connected, and indeed it fails to be connected for some groups. Giudici and Parker [8] showed that, even if it is connected, its diameter may be unbounded. On the other hand, Morgan and Parker [13] showed that if a group has trivial centre, then any connected component of its commuting graph has diameter at most $10$.

The commuting graph of a group $G$ fits into a hierarchy of graphs as follows. Each graph now has vertex set $G\setminus\{1\}$, and the rules for adjacency of vertices $x$ and $y$ are as follows:

• •

  the power graph: one of $x$ and $y$ is a power of the other;

• •

  the enhanced power graph: $x$ and $y$ are powers of some element $z$;

• •

  the commuting graph: $[x,y]=1$;

• •

  the non-generating graph: $\langle x,y\rangle\neq G$;

• •

  the complete graph: all pairs are adjacent.

Observe that each graph is a spanning subgraph of the next (except for the third and fourth when $G$ is $2$-generated and abelian). This allows us to refine questions about connectedness, and ask, for instance, whether the difference between consecutive graphs in the hierarchy is connected (often with specified vertices removed). For example, the difference between the complete and non-generating graphs of $G$ is the generating graph $\Gamma(G)$, where $x$ and $y$ are adjacent if and only if $\langle x,y\rangle=G$. For convenience, we will write $\Gamma^{+}(G)$ to denote the subgraph of $\Gamma(G)$ induced by its non-isolated vertices.

The most basic question is whether the difference between consecutive graphs has any edges at all, for $|G|>2$. Finite groups whose power graph and enhanced power graph are equal, or whose enhanced power graph and commuting graph are equal, were determined by Aalipour et al. [1]. The commuting graph and the non-generating graph of a non-abelian group are equal if and only if the group is minimal non-abelian, i.e., every proper subgroup of the group is abelian. Finally, $\Gamma(G)$ has no edges if and only if $G$ is not $2$-generated.

More complicated questions regarding connectedness have also been asked and resolved in the case of $\Gamma(G)$. For example, Breuer, Guralnick and Kantor [5, Theorem 1.2] proved that if $G$ is a non-abelian finite simple group, then $\Gamma(G)$ is extremely “dense”, in the sense that it is connected with diameter $2$. More recently, Burness, Guralnick and Harper [6, Corollary 6] generalised this result: if $G$ is a finite group, then $\Gamma(G)$ either has an isolated vertex or is connected with diameter at most $2$.

The structure of $\Gamma(G)$ is less predictable, however, when isolated vertices are involved. For example, Crestani and Lucchini [7, Theorem 1.3] showed that although $\Gamma^{+}(G)$ is connected when $G$ is a $2$-generated direct power of $\mathrm{SL}(2,2^{p})$, with $p$ an odd prime, $G$ can be chosen so that the diameter of $\Gamma^{+}(G)$ is arbitrarily large. On the other hand, Lucchini [11, Corollary 4] proved that if $G$ is finite and nilpotent, then $\Gamma^{+}(G)$ is connected with diameter at most $2$.

This motivates the present paper, which considers the non-commuting, non-generating graph $\Xi(G)$ of a group $G$, i.e., the difference between the non-generating graph and the commuting graph of $G$. In this case, we remove all vertices corresponding to central elements of $G$, as otherwise these would always be isolated. Thus $\Xi(G)$ is the graph whose vertices are $G\setminus Z(G)$, with vertices $x$ and $y$ adjacent if and only if $[x,y]\neq 1$ and $\langle x,y\rangle\neq G$. In addition, we write $\Xi^{+}(G)$ to denote the subgraph of $\Xi(G)$ induced by its non-isolated vertices.

We will focus in this paper on the case where $G$ is a (not necessarily finite) nilpotent group, and describe the possible diameters of the connected components of $\Xi(G)$. As the unique nontrivial connected component of the generating graph of a finite $2$-generated nilpotent group $G$ is always extremely dense, one may expect that the same is not necessarily true for $\Xi(G)$, which is a proper subgraph of the complement of this generating graph. However, the first of our main theorems shows that this is actually the case for any nilpotent group.

We will in fact prove that the conclusion of this theorem holds whenever $G$ is a group with every maximal subgroup normal. This is a weaker condition than nilpotency, as illustrated by the infinite $2$-generated $3$-group constructed by Gupta and Sidki [10]. Indeed, every maximal subgroup of this group is normal [17, Theorem 4.3]; however, the group has no finite presentation [19], and is therefore not nilpotent. For further discussion of groups with every maximal subgroup normal, see, for example [14, 15].

It is clear that, for an arbitrary group $G$, the graph $\Xi(G)$ is empty if and only if $G$ is abelian. As mentioned above, $\Xi(G)$ has vertices but no edges if and only if $G$ is minimal non-abelian. Since a non-central element of a group is centralised by at most one maximal subgroup, a minimal non-abelian group is necessarily $2$-generated.

The finite minimal non-abelian groups were classified by Miller and Moreno [12] in 1903 (see also [18]). In particular, any such group is either a $p$-group, for some prime $p$, or a non-nilpotent group whose order is divisible by exactly two primes. A concise description of the finite minimal non-abelian $p$-groups is given in [21, Theorem 2.4]. On the other hand, a classification of infinite minimal non-abelian groups is not complete. Well-known examples are the Tarski monsters, which are simple groups where every proper nontrivial subgroup is cyclic of fixed prime order $p$. Ol’shanskiĭ [16] proved that a Tarski monster exists for each prime $p>10^{75}$.

The relationship between $G$ and $\Xi(G)$ is less clear when $\Xi(G)$ has edges. The remaining two main theorems of this paper provide a detailed overview of this relationship in the case where $G$ is a finite nilpotent group. We let $\Phi(G)$ denote the Frattini subgroup of $G$.

Using Magma [4], we can show that the groups numbered $(16,7)$, $(243,3)$ and $(32,6)$ in the Small Groups Library [3] are groups of the smallest order satisfying (iii)(a), (b) and (c), respectively.

Note that the group $P$ in case (iii)(b) of the above theorem may be minimal non-abelian.

The structure of this paper is as follows. In §2, we prove several preliminary results about the graph $\Xi(G)$. Next, in §3, we derive useful properties of groups that contain a normal maximal subgroup. This section concludes with a proof of Theorem 1.1. We then prove Theorem 1.2 in §4. Finally, in §5, we investigate the structure of $\Xi(G)$ when $G$ is a direct product of groups, and in particular prove Theorem 1.3.

We now prove several elementary but useful results about the non-commuting, non-generating graph of an arbitrary group $G$. Note that if $x$ and $y$ are vertices of a graph, then we write $d(x,y)$ to denote the distance in the graph between $x$ and $y$.

In order to deduce additional properties of $\Xi(G)$, we will briefly consider the non-commuting graph of $G$. This graph has vertex set $G\setminus Z(G)$, with two vertices adjacent if and only if they do not commute. Thus the graph is the complement of the commuting graph (with central elements removed). Abdollahi, Akbari and Maimani proved the following result, using similar arguments to those in the proof of Proposition 2.1 above, as well as the fact that the union of two proper subgroups of $G$ is a proper subset of $G$.

We are now able to derive two useful corollaries involving $\Xi(G)$.

Next, notice that if $G$ is not $2$-generated, then $\Xi(G)$ is equal to the non-commuting graph of $G$. We therefore obtain the following corollary of Proposition 2.2.

Hence to prove our main theorems, we need only consider non-abelian $2$-generated groups that are not minimal non-abelian.

The final result in this section generalises the observation that every vertex of $\Xi(G)$ is isolated if and only if $G$ is minimal non-abelian.

Note that if $G$ is finitely generated but not $2$-generated, then each element of $G$ lies in more than one maximal subgroup.

In this section, we derive some of the most important tools that we will use to prove our main theorems. We will conclude the section with a proof of Theorem 1.1.

Our next result, together with Proposition 2.6, allows us to better characterise isolated vertices of $\Xi(G)$ in the case where every maximal subgroup of $G$ is normal.

Our next result provides upper bounds (and in some cases exact values) for distances between certain non-isolated vertices of $\Xi(G)$, and in fact between any two non-isolated vertices when every maximal subgroup of $G$ is normal.

We are now able to prove a more general version of Theorem 1.1.

Theorem 1.1 now follows immediately.

In this section, we determine the diameters of the connected components of $\Xi(G)$ when $G$ is a finite $p$-group, with $p$ a prime, and in particular prove Theorem 1.2. Corollary 2.4 implies that it suffices to consider the case where $G$ is non-abelian and $2$-generated. We therefore begin by deducing information about non-abelian, finite, $2$-generated $p$-groups.

The “equality” statement in part (iii) of the following lemma is well known (for example, see [21, Lemma 2.3]).

We are now able to prove our second main theorem.

In this section, we explore the structure of the non-commuting, non-generating graph of a direct product of groups. In particular, we conclude with a proof of Theorem 1.3.

Let $G$ and $H$ be arbitrary groups, with $g_{1},g_{2}\in G$ and $h_{1},h_{2}\in H$. Observe that if $[g_{1},g_{2}]\neq 1$ or $[h_{1},h_{2}]\neq 1$, then the elements $(g_{1},h_{1})$ and $(g_{2},h_{2})$ of $G\times H$ do not commute and are therefore non-central. In particular, these elements are vertices of $\Xi(G\times H)$. Additionally, if $\langle g_{1},g_{2}\rangle\neq G$ or $\langle h_{1},h_{2}\rangle\neq H$, then $\langle(g_{1},h_{1}),(g_{2},h_{2})\rangle\neq G\times H$. Therefore, relatively weak conditions are required for two vertices of $\Xi(G\times H)$ to be adjacent. We utilise this fact to prove the following two results.

The above result shows that the non-commuting, non-generating graph behaves very differently to the generating graph in the context of $2$-generated direct powers of non-abelian groups. Indeed, as mentioned in §1, Crestani and Lucchini proved that there is no upper bound for the diameter of $\Gamma^{+}(G)$, for $G$ such a direct power.

In the following proposition and its proof, we use the symbol $d$ to denote distances in both $\Xi(G)$ and $\Xi(G\times H)$. In each case, it will be clear which graph contains the relevant vertices. Additionally, if $x$ and $y$ are vertices of a graph that lie in distinct connected components, then we write $d(x,y)=\infty$.

It is easy to show, using Burnside’s Basis Theorem, that the direct product of a finite $d_{1}$-generated $p$-group and a finite $d_{2}$-generated $p$-group is $(d_{1}+d_{2})$-generated. Thus no non-abelian $2$-generated finite $p$-group can be expressed as a nontrivial direct product. It will follow from Theorem 1.3 that if $H$ is a finite cyclic group and $G$ is a finite nilpotent group such that $\Xi(G)$ is connected, then $\mathrm{diam}(\Xi(G\times H))\neq\mathrm{diam}(\Xi(G))$ if and only if $\mathrm{diam}(\Xi(G\times H))=3$ and $|G|$ and $|H|$ have a common prime divisor. However, this is not always the case if $G$ is not nilpotent. For example, the non-commuting, non-generating graph of the symmetric group $S_{4}$ is connected with diameter $3$, as is the graph $\Xi(S_{4}\times C_{3})$. On the other hand, $\mathrm{diam}(\Xi(S_{4}\times C_{2}))=2$ (note that $S_{4}\times C_{2}$ is $2$-generated).

We now wish to determine which vertices of $\Xi(G\times H)$ are isolated. Proposition 2.6 suggests that a classification of the maximal subgroups of $G\times H$ will aid us in this task. The next result, which is a consequence of Goursat’s Lemma [9, §11–12], gives such a classification.

In what follows, we assume the convention that if $H$ is an infinite group, then each positive integer divides $|H|$.

We are now able to describe the isolated vertices of $\Xi(G\times H)$.