Enhancing technology leaders' instructional leadership through a project-based learning online course

1.   Introduction

The study of group and graph theories has had considerable attention over the past several years. An important example of such interplay is the notion of the Cayley graph that dates back to 1878 (see ^[4]). Other important examples that can be found are the notions of commuting graph (see ^[5]) and non-commuting graph of a group (see ^[7]). Several other studies have highlighted the relationship between graph theory and group theory (see ^[1,2,3,6,9]).

Let $\Gamma$ be a graph with vertex set $V$ and edge set $E$. We say that $\Gamma$ is connected if there is a path between every pair of vertices of $\Gamma$. If vertex $u$ is adjacent to vertex $v$, then we denote it shorten by $u \sim v$. The length of a smallest cycle contained in a graph $\Gamma$ is called the girth and it is denoted by gr($\Gamma$). The distance between $a$ and $b$ in a graph $\Gamma$ is the length of a shortest path between $a$ and $b$. The diameter of a connected graph $\Gamma$ is the length of the longest path between two distinct vertices of $\Gamma$. A bipartite graph is a graph whose vertices can be divided into two disjoint and independent sets $A$ and $B$ such that every edge has one vertex in $A$ and the other in $B$. A complete bipartite graph is a bipartite graph such that every vertex $a\in A$ is adjacent to every vertex $b\in B$. A tree is a connected graph such that there is no cycle as a subgraph. A dominating set for a graph $\Gamma$ is a subset $D$ of a vertex set $V$ such that every vertex in $V\setminus D$ is adjacent to at least one vertex in $D$. The domination number $\gamma(\Gamma)$ is the number of vertices in a smallest dominating set for $\Gamma$. A cycle that meets every vertex in a graph exactly once is called a Hamiltonian cycle. A graph that includes a Hamiltonian cycle is called a Hamiltonian graph.

Throughout this article, $G$ denotes a finite group. A subgroup $H$ of a group $G$ is called a normal subgroup if and only if $ghg^{-1}\in H$ for all $g\in G$ and $h\in H$. If $H$ is a subgroup of $G$ and $a\in G$, then the left coset of $H$ containing $a$ is $aH = \{ah |h\in H\}$. Similarly the right coset of $H$ containing $a$ is $Ha = \{ha |h\in H\}$. For basic definitions in graph theory and group theory, we refer the reader to ^[10,11,12].

This article concerns a bipartite graph associated with elements and cosets of subgroups of $G$. In Section 2, we introduce the bipartite graph associated with elements and cosets of subgroups of $G$ and we provide some examples of $\Gamma(G)$. Furthermore, we give a clear view of its basic properties including diameter, girth, connectivity and the dominating number. In fact, we display some relations between group theory and graph theory through this graph. In Section 3, we study the planarity and outer planarity of $\Gamma(G)$. In Section 4, we shed light on the relationship between the Hamiltonian property of this graph and the number theory problem throughout dihedral groups.

2.   Basic results

In this section, we define a new type of graph that is determined by group theoretic properties and we present some examples that give a clear view of our new graph. Then we present some characteristics of $\Gamma(G)$.

Definition 2.1. A bipartite graph associated to elements and cosets of subgroups of a finite group $G$ denoted by $\Gamma(G)$ is defined as the following: The set of vertices $V(\Gamma(G)) = A\cup B$, where $A$ is the set of all elements of a group $G$ and $B$ is the set of all subgroups of $G$ and two vertices $x \in A$ and $H \in B$ are adjacent if and only if $xH = Hx$.

Theorem 2.2. Let $G$ be a group. Then $\Gamma(G)$ has no isolated vertex.

Proof. If $G = \{e\}$, then trivially $e$ is adjacent to $G$ and $\Gamma(G) = K_2$. Assume that $G \neq \{e\}$. Then for every vertex $x\in A$ and every vertex $H\in B$, we have $x$ is adjacent to $\{e\}$ and $H$ is adjacent to $e$. Therefore $deg(x)$ and $deg(H)$ are at least $1$ and the result follows.

Theorem 2.3. The graph $\Gamma(G)$ is connected with diameter less than or equal $3$.

Proof. We have to prove that for every two arbitrary vertices, there exists a path between them of length at most $3$. So, we have the following cases:

Case 1. $x_1, x_2 \in A$.

It is obvious that $x_1$ and $x_2$ have common neighbour (for example $\{e\}$ or $G$) in $B$ and we have a path of length $2$.

Case 2. $H_1, H_2 \in B$.

Similar to the case 1, two vertices $H_1$ and $H_2$ have common neighbour $e$ in $A$ and again we have a path of length $2$.

Case 3. $x \in A$ and $H \in B$.

By the above two cases, we will have a path $x \sim \{e\} \sim e\sim H$ of length $3$.

Hence $\Gamma(G)$ is connected and $diam(G) \leq 3$.

As a consequence of Theorem 2.3, we can see that $\Gamma(G)$ can not be tree or star graph.

Example 2.4. Firstly, we consider the group $S_3 = \{ e, (1 2), (1 3), (2 3), (1 2 3), (1 3 2)\}$. The set $A = S_3$ and the set $B = \{ H_0 = \{e\}, H_1 = \{e, (1 2)\}, H_2 = \{e, (1 3)\}, H_3 = \{e, (2 3)\}, H_4 = \{e, (1 2 3), (1 3 2)\}, H_5 = S_3\}$. It is clear that $Z(S_3) = \{e\}$ and $H_4$ is normal subgroup in $S_3$. Hence $\{e\}$ and $H_4$ are adjacent with all vertices in the set $A$. The graph $\Gamma(S_3)$ is drawn in Figure 1(a). Secondly, let $G = \mathbb{Z}_8$. So, the set $A = \mathbb{Z}_8$ and the set $B = \{ H_0 = \{e\}, H_1 = < 2 > , H_2 = < 4 > , \mathbb{Z}_8\}$. Since all subgroups of $\mathbb{Z}_8$ are normal, $\Gamma(\mathbb{Z}_8)$ is complete bipartite graph (see Figure 1(b)).

Theorem 2.5. If $Z(G) \neq \{e\}$ and $|B| \geq 2$, then the girth of $\Gamma(G)$ equals 4.

Proof. Since any bipartite graph has no odd cycle. Hence, there is no cycle of length 3. we may have a cycle of length 4 as the following $e \sim H_1\sim z \sim H_2 \sim e$, where $e, z\in Z(G)$ and $H_1, H_2 \in B$.

Definition 2.6. A group $G$ is called Dedekind group if all subgroups of $G$ are normal. If $G$ is non-abelian and Dedekind group, then it is called Hamiltonian.

Theorem 2.7. The graph $\Gamma(G)$ is complete bipartite graph if and only if $G$ is a Dedekind group.

Proof. First, we note that if $H$ is a normal subgroup of $G$, then $xH = Hx$ for every element $x$ in $G$. Thus, if $H$ is a normal subgroup of $G$, then $H$ is adjacent to all elements of $G$. Hence, if $G$ is a Dedekind group, then $\Gamma(G)$ is complete bipartite graph. Conversely, if $\Gamma(G)$ is complete bipartite, then every element of $G$ must adjacent to every subgroup of $G$. So, if $H$ is an arbitrary subgroup of $G$, then we should have $xH = Hx$ for every element $x\in G$. It is equivalent to say that $H$ is a normal subgroup of $G$. Thus, every subgroup of $G$ should be normal which implies that $G$ is a Dedekind group as required.

Example 2.8. Let $G = Q_{8}$ be quaternion group. Then we have the following subgroups $H_1 = \{1\}, H_2 = \{1, -1\}, H_3 = \{1, -1, i, -i\}, H_4 = \{1, -1, j, -j\}, H_5 = \{1, -1, k, -k\}, H_6 = Q_{8}$. It is clear that $Q_8$ is a Hamiltonian group and so all subgroups of $Q_8$ are normal. Hence the graph $\Gamma(Q_8)$ is $K_{8, 6}$ (See Figure 2).

Lemma 2.9. Assume that $G$ is a group, $Z(G)$ is the center of $G$, $\{x_1, x_2, x_3, \cdots, x_n\}$ is the set of representative elements of distinct left cosets of $Z(G)$ in $G$ and $H$ is a subgroup of $G$. Then

(i) if $x_i$ is adjacent to $H$, then all element in $x_{i}Z(G)$ is also adjacent to $H$

(ii) if $x_i$ is not adjacent to $H$, then any element in $x_{i}Z(G)$ can not be adjacent to $H$.

Proof. $(i)$ Assume that $x_i$ is adjacent to $H$ and $z$ is an arbitrary element in $Z(G)$. Then we have $x_{i}z H = x_{i}Hz = Hx_{i}z$ which implies that $x_{i}z$ is adjacent to $H$. $(ii)$ Suppose that $x_{i}$ is not adjacent to $H$ and $x_{i}z$ is adjacent to $H$ for some $z \in Z(G)$. Then we have $x_{i}zH = Hx_{i}z$. So $zx_{i}H = zHx_i$. By removing $z$ from both sides, we got $x_{i}H = Hx_{i}$ which is a contradiction.

Theorem 2.10. Let $G$ be a group. Then the dominating number of the graph $\Gamma(G)$ is exactly 2.

Proof. Suppose that $D = \{e, G\}$. Then it is clear that $D$ is a dominating set. Because, if $e \neq x\in A$, then it will adjacent to $G$ and if $G\neq H\in B$, then $H$ will adjacent to $e$. Moreover, $D$ is the smallest dominating set and we can not have a singleton dominating set. Thus, the domination number $\gamma(\Gamma) = |D| = 2$ as required.

3.   Planarity and outer planarity

In this section, we deal with the planarity and outer planarity of $\Gamma(G)$. Let us start with the following simple lemma.

Lemma 3.1. Let $G$ be a cyclic group of order $p$, where $p$ is a prime number. Then $\Gamma(G)$ is planar.

Proof. From the definition of bipartite graph and the structure of cyclic group of order $p$, we can see that the vertex set of $\Gamma(G)$ consists of $p$ elements of $G$ in the set $A$ and $2$ subgroups (the trivial subgroup and the whole group $G$) in the set $B$. Thus it is complete bipartite $K_{p, 2}$ and so $\Gamma(G)$ is planar (see Figure 3).

Lemma 3.2. Let $G$ be a cyclic group of order $p_1p_2$, where $p_1$ and $p_2$ are two distinct prime numbers. Then $\Gamma(G)$ is not planar.

Proof. It is clear that we have at least $4$ subgroups of order $1$, $p_1$, $p_2$ and $p_1p_2$. Hence $\Gamma(G)$ contains subgraphs $K_{p_1 p_2, 4}$. Since $p_1p_2 \geq 3$, so $\Gamma(G)$ contains $K_{3, 3}$ which implies that $\Gamma(G)$ is not planar.

Theorem 3.3. Let $G$ be a cyclic group of order $n$, where $n = {p_1}^{\alpha_1}{p_2}^{\alpha_2}\cdots {p_k}^{\alpha_k}$. If $k = 1$ and $\alpha_{k} = 1$. Then $\Gamma(G)$ is planar. Otherwise it is not planar.

Proof. It is clear that if $k = 1$ and $\alpha_k = 1$, then $G$ is a cyclic group of prime order and so $\Gamma(G)$ is planar by Lemma $3.1$. If $k = 1$ and $\alpha_k \geq 2$, then we have at least three subgroups of order $1, p_1$ and $p_1^{\alpha_1}$ which they are all adjacent to every element of $G$. Thus it contains subgraph $K_{3, 3}$. So, $\Gamma(G)$ is not planar. If $k > 2$, then we may again find at least three subgroups of $G$ which are adjacent to all elements of $G$. Hence, $\Gamma(G)$ is not planar.

In the following theorem we classify the planarity of $\Gamma(G)$ and show that the only cyclic groups of prime order have planar graphs.

Theorem 3.4. Let $G$ be a finite group and $\Gamma(G)$ be the associated bipartite graph of $G$. Then $\Gamma(G)$ is planar if and only if $G$ is a cyclic group of order prime number.

Proof. It is clear that if $G$ is a cyclic group of prime order, then $\Gamma(G)$ is planar by Lemma 3.1. Conversely, assume that $\Gamma(G)$ is planar. Then we may consider the following cases:

Case 1. $G$ is a cyclic group.

In this case, we can see that the only possibility for $\Gamma(G)$ to be planar is when $G$ is a cyclic group of prime order, by Lemma 3.1 and Theorem 3.3. Thus the result follows.

Case 2. $G$ is not a cyclic group.

In this case, we can consider the following two subcases:

${\bf{(i)}} \; G$ is a simple group.

If $G$ contains an element $x$ of order $3$ or more, then $\Gamma(G)$ contains a copy of $K_{3, 3}$ induced on the vertices $e, x, x^2$ of $A$ and the vertices $\{e\}, < x > , G$ of $B$ which is a contraction. Thus every non-identity element of $G$ has order $2$. So, by a group theory result $G$ must be an abelian group and since by our assumption $G$ is simple, it will be a cyclic group of prime order as required.

${\bf{(ii)}} \; G$ is not a simple group.

Since $G$ is not simple, there is a normal subgroup $N$ such that $\{e\} \neq N \neq G$. Thus, there are two distinct elements $e \neq x\in N$ and $x \neq g \in G$. Hence the induced subgraph to vertices $e, x, g$ of $A$ and $\{e\}, N, G$ of $B$ provide $K_{3, 3}$ and is a contradiction. Thus the proof is completed.

Example 3.5. If $G$ is a group of order less than $9$. Then $\Gamma(G)$ is the following:

If $|G| = 1$, then $\Gamma(G) = K_{1, 1}$ and so it is planar. If $|G| = 2$, then $\Gamma(G) = K_{2, 2}$. So $\Gamma(G)$ is planar. If $|G| = 3$, then $\Gamma(G) = K_{3, 2}$ and so $\Gamma(G)$ is planar. If $|G| = 4$, then we have two cases. If $G$ is cyclic, then $\Gamma(G) = K_{4, 3}$ which implies that $\Gamma(G)$ is not planar. If $G$ is not cyclic, then $\Gamma(G) = K_{4, 5}$ and again $\Gamma(G)$ is not planar. If $|G| = 5$ then $\Gamma(G) = K_{5, 2}$. Thus $\Gamma(G)$ is planar. If $|G| = 6$, then we have two cases. If $G$ is cyclic, then $\Gamma(G) = K_{6, 4}$ which implies that $\Gamma(G)$ is not planar. If $G$ is not cyclic, then $G = S_3$ and $\Gamma(G)$ has $K_{3, 3}$ as a subgraph. Thus $\Gamma(G)$ is not planar. If $|G| = 7$ then $\Gamma(G) = K_{7, 2}$ and is planar. If $|G| = 8$, then $G$ is one of $\mathbb{Z}_8$, $Q_8$ or $D_8$. In all cases $\Gamma(G)$ is not planar (see Figures 1 and 2 and the point that the induced subgraph $\{e, x, y\}\subseteq A$ and $\{\{e\}, Z(D_8), D_8\}$ is $K_{3, 3}$ and so it is not planar).

Definition 3.6. A graph $\Gamma$ that has a planar drawing such that all vertices lie on the outer-face of the graph is called an outer planar graph ^[10].

A known result shows that a graph is outer planar if it has no subgraph isomorphic to $K_4$ or $K_{2, 3}$.

Theorem 3.7. Let G be a cyclic group of order $p\geq 3$, where $p$ is a prime number. Then $\Gamma(G)$ is not an outer planar graph.

Proof. Assume that G is a cyclic group of order $p\geq 3$. We can see that the vertex set $A$ consists of $p$ elements, where $p\geq 3$, and two vertices in $B$. Hence the graph contains $K_{2, 3}$ as a subgraph of $\Gamma(G)$. Therefore $\Gamma(G)$ is not an outer planar graph.

One can easily see that if a graph is an outer planar then it is planar too. But, the converse is not true. The following example shows that we may have a planar graph which is not outer planar.

Example 3.8. Let $\mathbb{Z}_5$ be a cyclic group of order $5$. Then we can see that $\Gamma(\mathbb{Z}_5) = K_{2, 5}$ which is planar. But it is not an outer planar graph.

Similar to Theorem 3.4, we may classify all outer planar graphs as the following.

Theorem 3.9. $\Gamma(G)$ is outer planar if and only if $|G| = 1$ or $2$.

Proof. It is clear that if $|G| = 1$ or $2$, then $\Gamma(G) = K_2$ or $C_4$, respectively. So, $\Gamma(G)$ is outer planar. Conversely, assume that $\Gamma(G)$ is outer planar. If $G$ is not cyclic, then by Theorem 3.4, $\Gamma(G)$ is not planar and consequently it is not Outer planar. Thus assume that $G$ is a cyclic group. Again by Theorem 3.4, if $G$ is not a cyclic group of prime order, then $\Gamma(G)$ is not outer planar. Hence the only possibility for $G$ is a cyclic group of order $2$, by Theorem 3.7. If $G = \{e\}$, then $\Gamma(G) = K_2$ is outer planar as well. Therefore $|G| = 1$ or $2$ as required.

4.   Hamiltonian

In this section we discuss the Hamiltonicity of the graph $\Gamma(D_{2n})$. We show that $\Gamma(D_{2n})$ is not Hamiltonian in many cases.

Lemma 4.1. Let $\Gamma(G)$ be Hamiltonian graph. Then $|A| = |B|$.

Proof. Suppose that $V(\Gamma(G)) = A\cup B$ and $\Gamma(G)$ is Hamiltonian. Thus we will have a cycle that meets all vertices of $\Gamma(G)$. If we start from a vertex $x_1$ in $A$, then will meet $y_1$ in $B$ and meets $x_2$ in $A$ and then $y_2$ in $B$. After $|A|$ steps we will reach to $x_{|A|}$ in $A$ and $y_{|A|}$ in $B$ and finally reach $x_1$. Since, Hamiltonian cycle must meet all vertices in $A$ and $B$, we should have $|A| = |B|$.

In the rest of this section, we are going to investigate for what values of $n$, $\Gamma(D_{2n})$ is Hamiltonian or not, where $D_{2n}$ is a dihedral group of order $2n$. Recall that $D_{2n}$ is a group generated by two elements $a$ and $b$ such that $a^n = b^2 = e$ and $bab = a^{-1}$. In the following theorems, we show that $\Gamma(D_{2n})$ is not Hamiltonian in many cases. First, we start with the following simple lemma.

Lemma 4.2. If $p$ is prime then $p^x > 2x+2$ for all $x\geq 3$.

Proof. Let $f(x) = p^x$. Then by the mean value theorem, for $[1, n]$, we have $f'(x) = p^xln(p)$ and $\frac{f(x)-f(3)}{x-3} = f'(c)$, where $3 < c < x$. Since $f'(c) = p^cln(c) > 2^3$. Thus $\frac{p^x-p^3}{x-3} > 2^3$. Hence, $p^x > 8x+p^3-24$, then $p^x > 8x+8-24 = 8x-16$. Therefore $p^x > 2x+2$, for all $x\geq 3$.

Lemma 4.3. Let $D_{2n}$ be a dihedral group of order $2n$. Then the number of subgroups of $D_{2n} = \tau(n)+\sigma(n)$, where $\tau(n)$ is the number of divisors of $n$ and $\sigma(n)$ is the sum of divisors of $n$.

Proof. (See ^[8]).

Thus if $V(\Gamma(D_{2n})) = A \cup B$, then we have $|A| = 2n$ and $|B| = \tau(n)+\sigma(n)$, for all $n \geq 3$. So, by Lemma $4.1$, if for some values of $n$, $2n = |A| \neq |B| = \tau(n)+\sigma(n)$, then $\Gamma(D_{2n})$ can not be Hamiltonian. In the following theorems, we determine many values of $n$ such that $\Gamma(D_{2n})$ is not Hamiltonian.

Lemma 4.4. $\Gamma(S_3)$ is not Hamiltonian.

Proof. As in Figure 1(a), $\Gamma(S_3)$ has 6 vertices in $A$ and $6$ vertices in $B$ as the following: $A = \{e, (12), (13), (23), (123), (132)\}$ and $B = \{H_0, H_1, H_2, H_3, H_4, S_3\}$. Moreover, we have $deg(H_1) = deg(H_2) = deg(H_3) = 2$ and $H_1, H_2$ and $H_3$ have a common neighbor $e$. If $\Gamma(S_3)$ is Hamiltonian, then we should have a cycle visited every vertex exactly once. But, we can easily check that it is not possible. Because, if there exists a cycle consisting vertices $H_1, H_2$ and $H_3$, then we have to visit identity element $e$ at least twice which is a contradiction to Hamiltonian cycle. Hence $\Gamma(S_3)$ is not Hamiltonian.

Theorem 4.5. $\Gamma(D_{2p})$ is not Hamiltonian for every prime number $p$.

Proof. Assume that $V(\Gamma(D_{2p})) = A \cup B$, then we will have $|A| = 2p$ and $|B| = p+3$. Thus $|A| = |B|$ will deduce that $p = 3$. Now, if $p = 3$ then $\Gamma(D_6) = \Gamma(S_3)$ is not Hamiltonian, by Lemma 4.4. Thus the proof follows.

Theorem 4.6. Let $p \geq 3$ be prime. If $n = p^2$ or $n = p^3$, then $\Gamma(D_{2p})$ is not Hamiltonian.

Proof. It is enough to prove that $|A| \neq |B|$. If $n = p^2$, then $|A| = 2p^2$ and $|B| = p^2+p+4$. So, $|A| \neq |B|$, because $p^2-p-4 = 0$ has no prime number solution. Similarly, for $n = p^3$, we have $|A| = 2p^3$ and $|B| = p^3+p^2+p+5$. So, $|A| \neq |B|$, because $p^3-p^2-p-5 = 0$ has no prime number solution. Thus the proof follows.

Theorem 4.7. $\Gamma(D_{2n})$ is not Hamiltonian for all $n = p^k$, where $p$ is prime and $k\geq 4$.

Proof. By the same method as in the above case, we have $|A| = 2p^k$ and $|B| = \tau(n) +\sigma(n)$. Hence, $|B| = k+1+1+p+p^2+\cdots+p^k = k+1+\dfrac{p^{k+1}-1}{p-1} = \dfrac{p^{k+1}+kp-k+p-2}{p-1}$. If $|A| = |B|$, then we will have $2p^{k+1} -2p^{k} = p^{k+1}+kp+p-k-2$, or equivalently $p^{k+1}-2p^k-kp-p+k+2 = 0$. Thus $p^k(p-2)-(k+1)p+2(k+1)-k = 0$

$\iff (p-2)(p^k-k-1) = k$. If $p = 2$, then we have $|A| = 2^{k+1} \neq 2^{k+1}+k = |B|$ and so $\Gamma(D_{2n})$ is not Hamiltonian. So $p-2\geq 1$. Therefore, $p^k-k-1 < k$. By Lemma $4.2$, $2k+2-k-1 < p^k-k-1\leq k$ or $k+1\leq k$ which is a contradiction. Thus, $|A|\neq |B|$ and therefore $\Gamma(D_{2n})$ is not Hamiltonian.

Corollary 4.8. $\Gamma(D_{2n})$ is not Hamiltonian, if $n = p^k$, for all $k\geq 1$ and prime number $p$.

The last theorem of the paper deals with the case that $n = pq^k$. The following lemma plays an important role in the proof of Theorem 4.10.

Lemma 4.9. Let $k\geq 2$, $p$ and $q$ be distinct prime numbers. Then the equation $p = \dfrac{q^k+q^{k-1}+q^{k-2}+\cdots+q+(3+2k)}{q^k-q^{k-1}-\cdots-q-1}$ has only integer solution when $q = 2$.

Proof. It can be easily seen that $q^k-q^{k-1}- q^{k-2} -\cdots-q-2 = (q-2)(q^{k-1}+q^{k-2}+\cdots+q+1)$ and so, $q^k-q^{k-1}-q^{k-2}-\cdots-q-1 = (q-2)(q^{k-1}+q^{k-2}+\cdots+q+1)+1$. Thus, if $q = 2$, then $q^k-q^{k-1}-q^{k-2}-\cdots-q-1 = 0+1 = 1$. Hence, $p = 2^k+2^{k-1}+\cdots+2+3+2k = (2^k+2^{k-1}+\cdots+2+1)+(2+2k) = \dfrac{2^{k+1}-1}{2-1}+(1+2k) \\ = 2^{k+1}+2k+1$.

Now, If $q = 3$, then $p = \dfrac{q^k+q^{k-1}+q^{k-2}+\cdots+q+(3+2k)}{q^k-q^{k-1}-\cdots-q-1}$ is not integer.

Moreover, assume that $p = \dfrac{A}{B}$, where $A = q^k+q^{k-1}+q^{k-2}+\cdots+q+(3+2k)$ and $B = q^k-q^{k-1}-\cdots-q-1$, then $B = (q-2)(q^{k-1}+q^{k-2}+\cdots+q+1)+1 = (q^k+q^{k-1}+\cdots+q^2+q)-2(q^{k-1}+\cdots+q+1)+1$. Hence, $-3-2k = A-2(q^{k-1}+\cdots+q+1)-2(k+1)$. Therefore, $A = B+2(q^{k-1}+\cdots+q+1)+2(k+1)$. So,

$p = \dfrac{A}{B} = \dfrac{B+2(q^{k-1}+\cdots+q+1)+2(k+1)}{B} = 1+\dfrac{2[(q^{k-1}+\cdots+q+1)+(k+1)]}{B}$

$= 1+2(\dfrac{C}{B})$, where $C = [(q^{k-1}+\cdots+q+1)+(k+1)]$. On other hand,

$B = (q-2)(q^{k-1}+q^{k-2}+\cdots+q+1)+1$

= $(q^{k-1}+q^{k-2}+\cdots+q+1)+(q-3)(q^{k-1}+q^{k-2}+\cdots+q+1)+1$

= $q^{k-1}+q^{k-2}+\cdots+q+1+(k+1)+(q-3)(q^{k-1}+q^{k-2}+\cdots+q+1)-k$

= $C+(q-3)(q^{k-1}+q^{k-2}+\cdots+q+1)-k$

$\geq C+(q^{k-1}+q^{k-2}+\cdots+q+1)-k$, since $q > 3$

$\geq C+(q^{k-2}+q^{k-3}\cdots+q+1)$

$\geq C$, since $q^{k-1} \geq k$

Therefore, $B > C$, and so, $\dfrac{C}{B} < 1$, which implies that $p = 1+2(\dfrac{C}{B})$ is not an integer.

Theorem 4.10. If $p$ and $q$ are distinct prime numbers and $n = pq^k$, where $p < q$ and $k\geq 1$, then $\Gamma(D_{2n})$ is not Hamiltonian.

Proof. If $\Gamma(D_{2n})$ is Hamiltonian, then we should have $2n = 2pq^k = \tau(n)+\sigma(n) = (2k+2)+(1+p+q+q^2+\cdots+q^k+pq+pq^2+\cdots+pq^k)$. Thus, $p = \dfrac{q^k+q^{k-1}+\cdots+q+(3+2k)}{q^k-q^{k-1}-\cdots-q-1}$. Let us start with the case that $k = 1$. In this case, we have $n = pq$ and so $2pq = 2n = |D_{2n}| = \tau(n)+\sigma(n) = 4+1+p+q+pq$ will imply that $(p-1)(q-1) = 6$. All solutions of this equation are $(p, q) = (2, 7), (7, 2), (3, 4)$, or $(4, 3)$. The only acceptable case is $(2, 7)$. But, if we draw $\Gamma(D_{28})$, then we can see that there are $13$ subgroups of order $2$ and degree $2$ in $B$. Moreover, they have a common neighbor identity element $e$. By the same reason as we mentioned in Lemma 4.4, $\Gamma(D_{28})$ is not Hamiltonian. Thus, $\Gamma(D_{2n})$ is not Hamiltonian for $n = pq$. Now, assume that $k \geq 2$. Then by Lemma $4.9$, the only integer solution for the above equation is $q = 2$, $p = 2^k+2k+1$. Since, $p < q$, so this solution is not acceptable and therefore, there is no integer solution. Hence $\Gamma(D_{2n})$. can not be Hamiltonian and the proof is complete.

Finally, we have checked the condition $|A| = |B|$ in $\Gamma(D_{2n})$ for all $3\leq n \leq 1000$ and found the numbers $3, 14, 52,130,184$ and $656$. It seems that as we removed the possibilities $3$ and $14$ for graphs $\Gamma(D_{6})$ and $\Gamma(D_{28})$, respectively. So, we possibly could be able to consider the other cases and show that they are not Hamiltonian. Thus, we end the paper with the following conjecture.

Conjecture. $\Gamma(D_{2n})$ is not Hamiltonian for all $n\ge 2$.

Acknowledgments

The authors would like to thank the referees for their valuable suggestions and important comments which helped to improve the manuscript.

Conflict of interest

The authors declare no conflict of interest.