Monther R. Alfuraidan^a , Yusuf F. Zakariyaa,b

^aDepartment of Mathematics & Statistics King Fahd University of Petroleum and Minerals Dhahran 31261, Saudi Arabia

^bDepartments of Science Education, Ahmadu Bello University, Zaria, Nigeria

monther@kfupm.edu.sa, yfzakariya@abu.edu.ng

Let (Γ, ∗) be a finite group and S a possibly empty subset of Γ containing its non-self-invertible elements. In this paper, we introduce the inverse graph associated with Γ whose set of vertices coincides with Γ such that two distinct vertices u and v are adjacent if and only if either u ∗ v ∈ S or v ∗ u ∈ S. We then investigate its algebraic and combinatorial structures.

Keywords: finite group, inverse graph, non-self-invertible, planar graphs, Hamiltonian graphs

Mathematics Subject Classification : 68R10

DOI:10.5614/ejgta.2017.5.1.14

1. Introduction

Studying the algebraic structures of groups and rings based on graph combinatorial properties has caught the interests of many researchers over the last decades. Recently, graphs associated with rings seems to be more interesting and active area compare to those associated with groups. For instance, unit graphs [3], total graphs [1], zero divisor graphs [2], and co-maximal graphs [15] are few examples of graphs associated with rings. On the contrary, the main aim of this paper is to introduce inverse graph and establish some of its properties. It is hoped that this work will shed more light on the algebraic structures of groups via graphs and open doors for more researches in this approach.

There has been a close tie between graph and group theories for more than a century. Deep investigations and amazing results from group theory have been proved easily via combinatorial properties of graphs and vice versa, [4, 8]. This serves as the underlying motivation for this

Received: 12 October 2015, Revised: 2 December 2016, Accepted: 08 February 2017.

work. It was Arthur Cayley in [7] who was the first to associate graphs "Cayley graphs" to finite groups. Given a finite group Γ and a non-empty generating subset C ⊆ Γ, the Cayley graph denoted by Cay(Γ, C) is defined as follows: each vertex is an element of Γ with two vertices u, v ∈ V (Cay(Γ, C)) being adjacent if uv⁻¹ ∈ C, see [14]. The connectivity and the planarity of this graph was investigated in [10]. For an excellent survey on the Hamiltonian cycles in Cayley graphs see [17]. Aside this, several other graphs have also been associated with finite groups such as commuting graphs, intersection graphs, prime graphs, non-commuting graphs, conjugacy class graphs, etc, [5, 6, 11, 12, 18]. In order to justify our claim that the inverse graph is new, we as well illustrate by examples how it is different from some known graphs associated with groups.

2. Preliminaries

A graph G is formed by a finite non-empty set V (G) of elements called vertices together with a possibly empty set E(G) of 2−element subsets of V (G) called edges. The cardinality of V (G) is called the order of G, while the cardinality of E(G) is called the size of G. Two vertices u and v of G are adjacent if there is an edge between them i.e. {u, v} ∈ E(G). In this case, we write uv ∈ E(G). A vertex u is said to be incident to an edge if u is one of the two vertices of G that form the edge. The number of edges incident to a vertex u in G is the degree of u, denoted by deg(u). A graph G with vertices each of degree r is called an r−regular graph. Two or more edges that join the same pair of distinct vertices are called parallel edges. A loop is an edge that joins a vertex to itself. A walk of length k ≤ n in a graph G with vertex set V (G) = {v0, v1, · · · , vn} is a finite sequence

\[v_{i_0}a_{j_1}v_{i_1}a_{j_2}v_{i_2}\cdots v_{i_{k-1}}a_{j_k}v_{i_k}\]

whose terms alternate between vertices and edges such that vⁱt−¹ v^it = a^jt for 1 ≤ t ≤ k and 0 ≤ i^k ≤ n. The walk W is closed if vⁱ⁰ = v^ik , otherwise it is open. An open walk in which no vertex is repeated is called a path. A closed walk of length k ≥ 3 with neither vertex nor edge is repeated is called a cycle. A vertex v of a graph G is said to be reachable if there is a walk starting from or ending at v from every other vertex in G. If every vertex in G is reachable and G is non-empty¹ then G is connected otherwise it is disconnected.

Definition 2.1. Let (Γ, ∗) be a finite group and S = {u ∈ Γ | u 6= u ⁻¹}. We define the inverse graph GS(Γ) associated with Γ as the graph whose set of vertices coincides with Γ such that two distinct vertices u and v are adjacent if and only if either u ∗ v ∈ S or v ∗ u ∈ S.

Throughout this paper S will always denote the non-self-invertible elements of the group Γ.

Remark 2.1. It is worthwhile to observe the following:

• 1. Clearly, identity e is a trivial self-invertible element in a finite group Γ. Hence e /∈ S. Consequently, the cardinality of S is strictly less than the cardinality of Γ. In particular, if Γ contains no self-invertible element other than the identity then |S| = |Γ| − 1.
• 2. As S has always an even number of elements, then |S| = |Γ|−1 if Γ contains an odd number of elements.

¹See Definition 3.1

3. In any inverse graph deg(e) = |S|.

Example 2.1. The graphs in Figure 2.1 are the inverse graphs of the groups (Z3, +), S = {1, 2} and (Z⁵ \ {0}, ·) , S = {2, 3} under the usual addition and multiplication respectively.

Figure 1. Inverse graphs of groups integers modulo 3 and 4

3. Properties of the Inverse Graphs

In this section, we study some basic properties of inverse graphs associated with finite groups. Definition 3.1. A graph G is empty if E(G) is empty and it is trivial if |V (G)| = 1.

Proposition 3.1. For any finite group Γ, the inverse graph GS(Γ) is empty if and only if |S| = 0.

Proof. Suppose GS(Γ) is empty. Then it follows from Definition 3.1 that for any u, v ∈ Γ with u 6= v, we have u ∗ v /∈ S. Hence S is empty i.e., |S| = 0. The converse is obvious.

Remark 3.1. Proposition 3.1 characterizes the inverse graph of a finite group with all of its elements being self-invertible. In particular, the inverse graphs associated with the following groups are empty graphs:

• 1. Groups consisting of two elements.
• 2. Γ² = a b 0 c | a, b, c ∈ Z² , with usual addition of matrices.
• 3. Γ³ = Z² × Z² = {(0, 0),(0, 1),(1, 0),(1, 1)}, with usual addition of R 2 .

On the other extreme, it is natural to ask when will the inverse graph be complete? Unfortunately, such graph never exists. A graph G is said to be complete provided it is non-empty and there is an edge between every distinct pair of its vertices. In a complete graph G with |G| = n, we have deg(v) = n − 1 for any vertex v of G.

Theorem 3.1. There is no inverse graph that is complete for any finite group Γ.

Proof. Suppose on the contrary that there exists an inverse graph GS(Γ) that is complete. Then for each vertex v ∈ V (GS(Γ)), deg(v) = n − 1, where n = |Γ|.

Case I: n is even. Since deg(e) = n − 1, then by Remark 2.1-(3) we have |S| = n − 1 which is not possible as |S| is always even for any inverse graph.

Case II: n is odd. Let u 6= v ∈ Γ such that u = v −1 . Since there is an edge between every two distinct vertices, we have e = u ∗ v ∈ S which is not possible, see Remark 2.1-(1).

Theorem 3.2. For any finite group Γ with at least three elements and a non-empty subset S of non-self-invertible elements, the graph GS(Γ) has no isolated vertex.

Proof. Suppose by contradiction that there exists an isolated vertex v in GS(Γ). Then we have the following two cases.

Case I: v ∈ S. But this is not possible for if e ∗ v = v ∈ S, where e is the identity element of Γ, then v is connected to e in GS(Γ).

Case II: v /∈ S, then either v is the identity or v is a non-trivial self-invertible element of Γ. It follows from Remark 2.1-(3), that v cannot be e. Hence v is a non-trivial self-invertible. Let ω ∈ S. If v is the only non-trivial self-invertible element of Γ and as v is an isolated vertex, then ω ∗ v = e which implies ω = v −1 , a contradiction. Hence v is not the only element of Γ \ {S ∪ {e}}. Thus there exists v ⁰ 6= v ∈ Γ \ {S ∪ {e}} such that v ∗ ω = v 0 . Hence ω = v ∗ v ⁰ ∈ S i.e., there is an edge between v and v 0 , a contradiction.

Theorem 3.3. For any finite abelian group Γ with at least three elements and a non-empty subset S of non-self-invertible elements, the graph GS(Γ) is connected.

Proof. By Remark 2.1-(3) the identity e is adjacent to every element of S. We are left to show that every element of Γ \ {S ∪ {e}} is adjacent to each element of S. For this, consider the product u ∗ v where u ∈ S, v ∈ Γ \ {S ∪ {e}} and * is the operation defined on Γ. Then, (u ∗ v) ⁻¹ = u ⁻¹ ∗ v ⁻¹ = u ⁻¹ ∗ v 6= u ∗ v since u ∈ S. So u ∗ v ∈ S. Since both u and v are arbitrarily chosen we have every element of Γ \ {S ∪ {e}} to be adjacent to each element of S. Therefore, each vertex of GS(Γ) is reachable and therefore connected.

Remark 3.2. Note that the commutativity of Γ in Theorem 3.3 can not be dropped for the conclusion to hold. An example of a non-abelian group with a disconnected inverse graph is the symmetry group S³ of order 6. On the other hand, it is not true that the inverse graph of every non-abelian group is disconnected. A counterexample is the inverse graph associated with quaternion group Q8.

In a connected graph G, the distance between two vertices u, v ∈ V (G), is the length of the shortest path between u and v. It is denoted by d(u, v). Eccentricity ρ(u), of a vertex u in a connected graph G is defined as

\[\rho(u) = Max\{d(u,v) : \forall v \in V(G)\}.\]

The minimum and the maximum eccentricity in a graph are radius, rad (G), and diameter, diam(G), of G respectively.

Theorem 3.4. The diameter of a connected inverse graph is two.

Proof. Let GS(Γ) be a connected inverse graph associated with a group Γ. We consider the following vertex partition: V (GS(Γ)) = {e} ∪ S ∪ S 0 , where S is the set of all non-self-invertible elements and S 0 is the set of all non-trivial self-invertible elements (called the set of involutions). Since every element in S is adjacent to e and there is no edge between e and the elements of S 0 , we have the eccentricity of e, ρ(e) = 2. Also, for each element u ∈ S, ρ(u) = 2 as u is not adjacent to its inverse but adjacent to e and every element in S 0 . Now take an arbitrary element v ∈ S 0 , it follows from the construction and connectivity of GS(Γ) that v is not adjacent to e but adjacent to every vertex in S. Hence ρ(v) = 2.

The following Lemma is the inverse graph version of the first theorem of graph theory.

Lemma 3.1. In a non-empty inverse graph GS(Γ) of order n, the sum of the degrees is bounded above by n(n − 1) − |S|.

Proof. Let V (GS(Γ)) = {v1, v2, · · · , vn}. By the first theorem of graph theory, we have

\[\sum_{i=1}^{n} deg(v_i) = 2|E(G_S(\Gamma))|.\]

By Theorem 3.1, GS(Γ) can not be complete. Hence

\[\sum_{i=1}^{n} deg(v_i) = 2|E(G_S(\Gamma))| < 2 \cdot \frac{n(n-1)}{2} = n(n-1).\]

Since GS(Γ) is a non-empty graph, then by Proposition 3.1 S 6= ∅. As any pair u, v ∈ S with u = v ⁻¹ has no edge in GS(Γ), such a pair contributes −2 to the total degrees of the vertices of GS(Γ). Hence a total of −|S| degrees will be contributed by the elements of S as a shortage in the sum of the degrees of GS(Γ). Therefore,

\[\sum_{i=1}^{n} deg(v_i) \le n(n-1) - |S|.\]

The following corollary elicits the fact that the inequality in Lemma 3.1 cannot be improved.

Corollary 3.1. Let Γ be a finite group with no element of order 2. Then

\[\sum_{i=1}^{n} deg(v_i) = n(n-1) - |S|.\]

Proof. Let V (GS(Γ)) = {v1, v2, · · · , vn}. Without loss of generality, let v¹ = e, the identity element of Γ. By remark 2.1-(1), we have |S| = |Γ| − 1 = n − 1, i.e., S = {v2, . . . , vn}. Hence, deg(v1) = n − 1. Now, for vⁱ , v^j ∈ S, 2 ≤ i 6= j ≤ n, the relation

\[v_i * v_j = \begin{cases} e, & v_i = v_j^{-1}; \\ v_k, & \text{otherwise.} \end{cases}\]

Hence, deg(vi) = n − 2 for all vⁱ ∈ S. Therefore,

\[\sum_{i=1}^{n} deg(v_i) = deg(v_1) + \sum_{i=2}^{n} deg(v_i)\] \[= n - 1 + (n - 1)(n - 2)\] \[= (n - 1)(1 + n - 2)\] \[= (n - 1)(n - 1)\] \[= n(n - 1) - (n - 1)\] \[= n(n - 1) - |S|.\]

Example 3.1. Let Γ = {z ∈ C : z ⁵ = 1} be the group of fifth root of unity under multiplication. As Γ is generated by one of its elements say ω, then we can write Γ =< ω >= {ω, ω² , · · · , ω⁵ = 1}. Hence S = {ω, ω² , ω³ , ω⁴}. GS(Γ) is show in Figure 2.

Figure 2. Inverse graph, GS(Γ), of the group Γ

It is obvious that P 5 i=1 deg(ω i ) = 5(5 − 1) − 4 = 16.

Proposition 3.2. Let Γ be a finite group of an odd order n. Then the size of GS(Γ) is bounded above by the size of the inverse graph associated with a cyclic group of the same order.

Proof. Let m be the size of GS(Γ). By Lemma 3.1 and the first theorem of graph theory, we have m ≤ n(n−1)−|S| 2 . Now, suppose that Γ¹ = hωi = he, ω, . . . , ωⁿ−¹ i is a cyclic group of order n. As n is odd, then ω ⁱ ∈ Γ¹ is non-self-invertible since (ω i ) ⁻¹ = ω ^j where i + j = n. It follows from Corollary 3.1 that the size of G(Γ1) is equal to ⁿ(n−1)−|S^| 2 .

Theorem 3.5. Let \(\Gamma\) be a finite group and the set S of non-self-invertible elements be a non-empty. The associated inverse graph \(G_S(\Gamma)\) is

• (i) 2-regular if \(\Gamma\) is a group of four elements.
• (ii) \((2^n-2)\)-regular if \(\Gamma\) is a generalized quaternion group of order \(2^n\) where n>2.

Proof. (i) Let \(\Gamma = \{e, v_1, v_2, v_3\}\). Since S is non-empty, without lost of generality, \(S = \{v_1, v_2\}\). By construction \(G_S(\Gamma)\) is the cycle \(C_4\). Hence it is 2 - regular.

(ii) Let \(\Gamma = \langle u, v : v^4 = u^{2^{n-1}} = e, v^2 = u^{2^{n-2}}, vu = u^{-1}v \rangle\) be the generalized quaternion group with n > 2. Since the only non-trivial self-invertible element in \(\Gamma\) is \(u^{2^{n-2}}\), we have \(S = \Gamma \setminus \{e, u^{2^{n-2}}\}\). Consequently, \(deg(e) = deg(u^{2^{n-2}}) = 2^n - 2\). Now, for each element \(v \in S\), we have \(deg(v) = 2^n - 2\) as v is adjacent to all vertices except to itself and its inverse.

Corollary 3.2. Let G be a connected \((2^n - 2)\)-regular graph, where n > 2. Then there exists a generalized quaternion group of order \(2^n\) such that its inverse graph is isomorphic to G.

A graph G is bipartite if V(G) can be partitioned into two disjoint sets \(V_1\) and \(V_2\) such that \(uv \in E(G)\) implies either \(u \in V_1\) and \(v \in V_2\) or \(v \in V_1\) and \(u \in V_2\). If each vertex in \(V_1\) is adjacent to each vertex in \(V_2\), then G is a complete bipartite graph. Suppose \(|V_1| = r\) and \(|V_2| = s\), then this complete bipartite graph, denoted by \(K_{s,r}\), has order s+r and size sr.

Theorem 3.6. Let \(\Gamma\) be a finite abelian group with exactly two non-self-invertible elements. Then the associated inverse graph \(G_S(\Gamma)\) is complete bipartite.

Proof. Given a finite abelian group \((\Gamma, *)\) with |S| = 2. Consider the partition \(V(G_S(\Gamma)) = \{V_1, V_2\}\), where \(V_1 = S\) (non-self-invertible elements) and \(V_2 = \Gamma \setminus S\) (self-invertible elements). Let \(u, v \in V(G_S(\Gamma))\).

• (i) \(u \in V_1\) and \(v \in V_2\). If \(u * v = v_0 \in V_2\), then as \(\Gamma\) is abelian, we have \(e = v_0^2 = u^2 * v^2 = u^2 * e = u^2\) which implies that \(u = u^{-1}\). But this is not possible as \(u \in V_1\). Hence \(u * v \in V_1\). Therefore, there is an edge between them.
• (ii) \(u, v \in V_1\). As there are only two elements in \(V_1\), then \(u * v = e \in V_2\). Therefore, there is no edge between u and v.
• (iii) \(u, v \in V_2\). If \(u * v = u_0\), then as \(\Gamma\) is abelian, we have \(u_0^2 = u^2 * v^2 = e * e = e\) which implies that \(u_0 = u_0^{-1}\). Hence \(u * v \in V_2\). Therefore, there is no edge between u and v.

A graph G is planar provided it can be represented on a plane such that there is no crossing of its edges. It is a fact that every complete bipartite graph \(K_{2,r}\) is planar, 2—colourable and has a clique number of 2. Hence the following corollary is obvious.

Corollary 3.3. Let \(\Gamma\) be a finite abelian group with exactly two non-self-invertible elements. Then the associated inverse graph \(G_S(\Gamma)\) is

• (i) planar.
• (ii) 2-colourable.
• (iii) having a clique number of 2.

We conclude this section with the following two results that classify the inverse graphs of \(\mathbb{Z}_4\).

Lemma 3.2. Let \(\Gamma\) be a group of order four and \(G_S(\Gamma)\) be a non-empty graph. Then \(\Gamma \cong \mathbb{Z}_4\).

Proof. Let \(\Gamma\) be a group of four elements and S be the set of non-self-invertible elements of \(\Gamma\). Since elements of S occur in pairs, |S| is equal to 0, 2, or 4. |S| cannot be zero because this would imply that \(G_S(\Gamma)\) is empty. Also \(|S| \neq 4\) since \(e \notin S\). Hence |S| = 2 and \(\Gamma\) has exactly one non-trivial self-invertible element.

Theorem 3.7. Let \(\Gamma\) be a finite group of order greater that or equal to three. Then \(G_S(\Gamma)\) is the cycle \(C_4\) if and only if \(\Gamma \cong \mathbb{Z}_4\).

Proof. Suppose that \(G_S(\Gamma) = C_4\). By contrary, assume that \(\Gamma \ncong \mathbb{Z}_4\). Since \(G_S(\Gamma)\) is a non-empty graph, then by Lemma 3.2, we have \(n = |\Gamma| \neq 4\).

• (i) n=3. Not possible as the only non-empty inverse graph of order 3 is \(P_2\), the path of length 2.
• (ii) \(n \geq 5\). As each vertex of \(G_S(\Gamma)\) has degree two, then by Remark 2.1-(3), 2 = deg(e) = |S|. Therefore, exactly two elements u and \(v \in \Gamma\) are non-self-invertibles. Since e is adjacent to both of them in \(G_S(\Gamma)\), there must exist a non-trivial self-invertible element \(\omega\) that is adjacent to u. Hence \(u * \omega = v\) which implies that \(v * \omega = u\). Thus \(\omega\) is adjacent to both u and v, see Figure 3. But as \(|\Gamma| \geq 5\), we must then have \(G_S(\Gamma)\) to be disconnected which is again not true as our inverse graph is \(C_4\).

Thus the only possible value of the order is four and hence by Lemma 3.2 \(\Gamma \cong (\mathbb{Z}_4, +)\).

Figure 3. Skeletal inverse graph in the proof of Theorem 3.7

The converse follows immediately by constructing \(G_S(\mathbb{Z}_4)\).

A graph G is said to be Hamiltonian provided G contains a cycle that visits all its vertices. It follows immediately that every cycle \(C_n\) is Hamiltonian and hence \(G_S(\mathbb{Z}_4)\) is Hamiltonian. The following theorems give some Hamiltonian characterizations of inverse graphs.

Theorem 3.8. Let \(\Gamma = \mathbb{Z}_p\), the group of integers modulo p (under addition or multiplication), where p is prime. Then \(G_S(\mathbb{Z}_p)\) is Hamiltonian provided \(|\mathbb{Z}_p| \geq 4\).

Proof. Let

\[\text{[rumus tidak dapat ditampilkan dengan baik — lihat PDF asli]}\]

Since the only self-invertible element of \(\mathbb{Z}_p\) is the identity e, then \(deg(v_i) = n-2\) for all \(v_i \neq e \in G_S(\mathbb{Z}_p)\) (see the proof of Corollary 3.1). By Remark 2.1-(3), \(deg(e) = n-1 > n-2 \geq \frac{n}{2}\), \(\forall n \geq 4\). Hence \(deg(v) \geq \frac{n}{2}\) for all vertices of \(G_S(\mathbb{Z}_p)\). Thus by Dirac's theorem², \(G_S(\mathbb{Z}_p)\) is Hamiltonian.

Theorem 3.9. Let \((\mathbb{Z}_n, +)\) be the finite group of integers modulo n under addition. Then \(G_S(\mathbb{Z}_n)\) is Hamiltonian for all \(n \geq 6\).

Proof. We have two cases n is \(\begin{cases} even, \\ odd. \end{cases}\)

Case I: n is even. In this case, \(\mathbb{Z}_n\) has exactly one non-trivial self-invertible element, say u with deg(u) = deg(e) = n - 2. For each of the remaining non-self-invertible element \(v \in \mathbb{Z}_n\), we have

\[\text{[rumus tidak dapat ditampilkan dengan baik — lihat PDF asli]}\]

Therefore,

\[deg(e) = deg(u) = n - 2 > n - 3 \ge \frac{n}{2},\]

for all \(n \geq 6\). Thus by Dirac's theorem the graph \(G_S(\mathbb{Z}_n)\) is Hamiltonian.

Case II: n is odd. In this case, \(\mathbb{Z}_n\) has the identity e as the only self-invertible element. Therefore, \(deg(v_i) = n-2\) for all \(v_i \neq e \in G_S(\mathbb{Z}_n)\) (see the proof of Corollary 3.1). By Remark 2.1-3, \(deg(e) = n-1 > n-2 \geq \frac{n}{2}\), \(\forall n \geq 6\). Thus by Dirac's theorem the graph \(G_S(\mathbb{Z}_n)\) is Hamiltonian.

As a consequence of Theorems 3.8 and 3.9, we have the following corollaries.

Corollary 3.4. Let \(\Gamma\) be a finite abelian group of order greater than three with the identity as the only self-invertible element. Then \(G_S(\Gamma)\) is Hamiltonian.

Corollary 3.5. Let \((\Gamma, *)\) be a finite abelian group of order greater than three with exactly one non-trivial self-invertible element. Then \(G_S(\Gamma)\) is Hamiltonian.

^&lt;sup>2</sup>Dirac's theorem states that if G is a simple graph with n(>3) vertices, and if \(deg(v) \ge n/2\) for each vertex v, then G is Hamiltonian (see [16])

Theorem 3.10. Let \(\Gamma\) be a finite abelian group of order n > 3. If n = 2|S|, then \(G_S(\Gamma)\) is Hamiltonian.

Proof. Let \(\Gamma = \{e\} \cup T \cup S\), where T is the set of all non-trivial self-invertible elements of \(\Gamma\) and S is the set of non-self-invertible elements in \(\Gamma\). We have \(|T| = \left(\frac{n}{2} - 1\right)\) and \(|S| = \frac{n}{2}\). By Remark 2.1-3 \(deg(e) = \frac{n}{2}\). For \(v_i, v_k \in T\), if \(v_i * v_k = v\), then \(v_i = v * v_k\) and \(v_k = v_i * v\). Thus \(v_i * v_k = (v * v_k) * (v_i * v)\). As \(\Gamma\) is abelian, we have \(v_i * v_k = v^2 * v_i * v_k\). Hence \(v = v^{-1}\) and therefore, \(v \in T\). So there is no edge between any pair of non-trivial self-invertible elements in \(G_S(\Gamma)\). However, for \(v_i \in T\) and \(v_j \in S\), we must have \(v_i * v_j \in S\). Otherwise, there exists an element \(v_k \in T\) such that \(v_i * v_j = v_k\) which implies that \(v_j = v_i * v_k \in T\), a contradiction. Therefore, \(deg(v) = |S| = \frac{n}{2}\) for each element \(v \in T\). As for each \(v_j \in S\), elements of T contribute \(\left(\frac{n}{2} - 1\right)\) to its degree, identity contributes 1 and so we have \(deg(v_i) \geq \frac{n}{2}\) since there could be edges between any pair of elements of S. Thus by Dirac's theorem \(G_S(\Gamma)\) is Hamiltonian.

The concept of isomorphism is of prime importance in both group and graph theories. Among the three crucial problems for groups raised by Max Dehn in 1911, the isomorphism problem is the most difficult (the word and conjugacy problems constitute the other two: see [13] and [9]). The problem of deciding whether two words (using some algorithms) in some finite generating sets represent the same or conjugate elements in a group constitutes the same word are the word and conjugacy problems respectively. Isomorphism problem, on the other hand, has to do with determining whether two groups that appear different are actually the same. In fact, Francois and Vincent asserted that the problem of finding an isomorphism of two groups is unsolvable for some classes of groups, [9]. This is quite interesting as a lot of researches are still going on to solve these problems.

Informally speaking, isomorphic groups are really the same groups except for the notations used. Besides, if \(\Gamma_1\) and \(\Gamma_2\) are two isomorphic groups then they share the same group - theoretic properties such as abelian, cyclic, elements of finite order, numbers of involutions, etc. It is clear from the definition of inverse graphs that if \(\Gamma_1 \cong \Gamma_2\) then \(G_{S_1}(\Gamma_1) \cong G_{S_2}(\Gamma_2)\) where \(S_1\) and \(S_2\) are the sets of non-self-invertible elements in \(\Gamma_1\) and \(\Gamma_2\) respectively. Investigation into the converse of this statement constitutes the conclusion of this section.

As a consequence of Proposition 3.1 and Corollary 3.2 we have the following result.

Lemma 3.3. Let \(\Gamma_1\) and \(\Gamma_2\) be finite groups with \(G_{S_1}(\Gamma_1) \cong G_{S_2}(\Gamma_2)\). Let \(\Gamma_1\) be one the following:

• (i) A group which all its elements are involutions.
• (ii) A generalized quaternion group.

Then \(\Gamma_1 \cong \Gamma_2\).

Theorem 3.11. Let \(\Gamma_1\) and \(\Gamma_2\) be finite abelian groups with \(G_{S_1}(\Gamma_1) \cong G_{S_2}(\Gamma_2)\). Then \(\Gamma_1 \cong \Gamma_2\).

Proof. Let \(S_1 = \{u \in \Gamma_1 | u \neq u^{-1}\}\) and \(S_2 = \{v \in \Gamma_2 | v \neq v^{-1}\}\). Since \(G_{S_1}(\Gamma_1) \cong G_{S_2}(\Gamma_2)\), we have \(S_1 \cong S_2\). It has been shown in the proof of Theorem 3.10 that \(\Gamma_1 \setminus \{S_1, e\}\) and \(\Gamma_2 \setminus \{S_2, e\}\) are closed subsets. In fact, both \(\Gamma_1 \setminus S_1\) and \(\Gamma_2 \setminus S_2\) form subgroups of \(\Gamma_1\) and \(\Gamma_2\) respectively. Hence \(\Gamma_1 \setminus S_1 \cong \Gamma_2 \setminus S_2\) follows from the isomorphism between \(G_{S_1}(\Gamma_1)\) and \(G_{S_2}(\Gamma_2)\).

4. Graphs associated with finite groups

In this section, we illustrate by examples how our new inverse graphs are different from some of those known graphs that have been associated with finite groups.

• 1. Cayley graphs: Consider the Klein four-group \(\mathcal{K}_4 = \{e, u, v, uv : e = u^2 = v^2 = (uv)^2\}\). Its generating sets are \(C_1 = \langle u, v \rangle, C_2 = \langle u, uv \rangle, C_3 = \langle v, uv \rangle\) and \(C_4 = \langle u, v, uv \rangle\). The Cayley graphs \(\operatorname{Cay}(\mathcal{K}_4, C_1)\), \(\operatorname{Cay}(\mathcal{K}_4, C_2)\) and \(\operatorname{Cay}(\mathcal{K}_4, C_3)\) are \(C_4\) (a cycle of length four), while \(\operatorname{Cay}(\mathcal{K}_4, C_4)\) is \(K_4\) (a complete graph of four vertices). On the other hand, since \(S = \emptyset\), then by Proposition 3.1, \(G_S(\mathcal{K}_4)\) is empty.
• 2. Commuting graph \(G(\Gamma; P)\), where \(\Gamma\) is a group and P a subset of \(\Gamma\), has P as its vertex set with two distinct elements \(u, v \in P\) joined by an edge whenever uv = vu in \(\Gamma\). Notice that for any abelian group \(\Gamma\) and \(P = \Gamma\), the associated commuting graph \(G(\Gamma; P)\) is complete. However, by Theorem 3.1 there is no inverse graph that is complete.
• 3. Intersection graph \(G(\Gamma)\); with non-trivial subgroups of \(\Gamma\) as its vertices such that two vertices \(\gamma_1, \gamma_2\) are connected if and only if \((\gamma_1 \setminus \{e\}) \cap (\gamma_2 \setminus \{e\}) \neq \emptyset\), where e is the identity element of \(\Gamma\). Consider the group of integers modulo p, \((\mathbb{Z}_p, +)\), where p is prime. By Lagrange's theorem, the only non-trivial subgroup of \(\mathbb{Z}_p\) is itself. Hence the intersection graph \(G(\mathbb{Z}_p)\) is a trivial graph. On the other hand, the inverse graph of \((\mathbb{Z}_p, +)\) is non-trivial since \(S \neq \emptyset\), see (Proposition 3.1).
• 4. Prime graphs \(G(\Gamma)\), with primes dividing the order of \(\Gamma\) as its vertices such that two vertices \(r_1\) and \(r_2\) are connected if and only if there exist an element \(u \in \Gamma\) of order \(r_1r_2\). Again consider the group of integers modulo p, \((\mathbb{Z}_p, +)\), where p is prime. The prime graph \(G(\mathbb{Z}_p)\) is a trivial graph.
• 5. Non-commuting graph \(G(\Gamma)\), with elements of \(\Gamma\) as its vertices such that two vertices u,v are connected if and only if \(uv \neq vu\). If \(\Gamma\) is non-abelian and \(Z(\Gamma)\) is the center, then non-commuting graph \(G(\Gamma)\) is also defined on the set \(\Gamma \setminus Z(\Gamma)\) as well. Consider the symmetry group \(S_3 = \langle a,b | a^2 = b^2 = (ab)^2 \rangle\). The non-commuting graph \(G(S_3)\) has the identity as an isolated vertex which is not possible in any inverse graph with an associated group with more than two, see (Theorem 3.2). Moreover, \(G(S_3 \setminus \{e\})\) has five vertices while the inverse graph of \(S_3\) contains six vertices.
• 6. Conjugacy class graph \(G(\Gamma)\), with non-central conjugacy classes of \(\Gamma\) as its vertices such that two vertices U and V are connected if and only if U and V are not coprimes i.e., \((|U|, |V|) \neq 1\). Again consider the symmetry group \(S_3\). Since \(S_3\) has two non-central conjugacy classes, then its conjugacy class graph contains only two vertices while its inverse graph contains six vertices.
• 7. Directed power graph \(G(\Gamma)\), with elements of \(\Gamma\) as its vertices such that there is a directed edge from u to v if and only if \(v=u^t, u\neq v\) and \(t\in \mathbb{Z}^+\). The power graph associated with \(\Gamma\) is defined to be the underlining graph of \(G(\Gamma)\). Consider the cyclic group \(\Gamma=\{e,w,w^2\}\). Then the power graph \(G(\Gamma)\) is the complete graph \(K_3\) while its inverse graph is a path \(P_3\) of length two.

Acknowledgement

The authors acknowledge King Fahd University of Petroleum and Minerals for supporting this research.

References

• [1] D.F. Anderson and A. Badawi, he total graph of a commutative ring, J. Algebra 320 (2008), 2706–2719.
• [2] D.F. Anderson and P.S. Livingston, The Zero-Divisor Graph of a Commutative Ring, J. Algebra 217 (1999), 434–447.
• [3] N. Ashrafi, H.R Maimani, M.R. Pournaki, and S. Yassemi, Unit graphs associated with rings, Comm. Algebra 38 (210), 2851–2871.
• [4] E.A. Bertram, Some applications of graph theory to finite groups, Discrete Math. 44 (1983), 31–43.
• [5] E.A. Bertram, M. Herzog, and A. Mann, On a graph related to conjugacy classes of groups, Bull. London Math. Soc. 22 (1990), 569–575.
• [6] S. Brauler and K.A. Fowler, On groups of even order, Ann. Math. 62 (1955) 565–583.
• [7] A. Cayley, Desiderata and suggestions: The theory of groups: Graphical representation, Amer. J. Math. 1 (1878), 174–176 (English).
• [8] G. Chartrand, L. Lesniak, and P. Zhang, Graphs & digraphs, fifth edition, Chapman & Hall/CRC, 2010.
• [9] F. Dahmani and V. Guirardel, The isomorphism problem for all hyperbolic groups, Geom. Funct. Anal. 21 (2011), 223–300 (English).
• [10] C. Droms, B. Servatius, and H. Servatius, Connectivity and planarity of cayley graphs, Beitr. Algebra Geom. 39 (1998), 269–282 (eng).
• [11] A. Gruber, T.M. Keller, M.L. Lewis, K. Naughton, and B. Strasser, A characterization of the prime graphs of solvable groups, J. Algebra 422 (2015), 397–422, Special Issue on the Third International Symposium on Groups, Algebras and Related Topics Celebrating the 50th Anniversary of the Journal of Algebra.
• [12] B.H. Neumann, A problem of Paul Erdo s on group, J. Aust. Math. Soc. 21 (Series A) (1976), 467–472.
• [13] Z. Sela, The isomorphism problem for hyperbolic groups I, Ann. Math. 141 (1995), 217–283 (English).

• [14] J. Steinhardt, Cayley graphs formed by conjugate generating sets of Sn, arxiv:0711.3057 [math.co], 2007.
• [15] H.-J. Wang, Graphs associated to co-maximal ideals of commutative rings, J. Algebra 320 (2008), 2917–2933.
• [16] R.J. Wilson, Introduction to graph theory, John Wiley & Sons, Inc., New York, NY, USA, 1986.
• [17] D. Witte and J.A. Gallian, A survey: Hamiltonian cycles in cayley graphs, Discrete Math. 51 (1984), 293–304 (English).
• [18] B. Zelinka, Intersection graphs of finite abelian groups, Czechoslovak Math. J. 25 (1975), 171–174.