Intersection Hypergraph on D n D_{n} Sachin Ballal and Ardra A N Abstract Let G G be a group and S S be the set of all non-trivial proper subgroups of G G . The intersection hypergraph of G G , denoted by Γ ~ ℋ ​ ( G ) \tilde{\Gamma}_{\mathcal{H}}(G) , is a hypergraph whose vertex set is { H ∈ S | H ∩ K = { e } ​ for some ​ K ∈ S } \{H\in S\,\,|\,\,H\cap K=\{e\}\,\,\text{for some}\,K\in S\} and hyperedges are the maximal subsets of the vertex set with the property that any two vertices in it have a trivial intersection. The aim of this paper is to study the intersection hypergraph of dihedral groups, Γ ~ ℋ ​ ( D n ) \tilde{\Gamma}_{\mathcal{H}}(D_{n}) . We examine some of the structural properties, viz., diameter, girth and chromatic number of Γ ~ ℋ ​ ( D n ) \tilde{\Gamma}_{\mathcal{H}}(D_{n}) . Also, we provide characterizations for hypertreees, star structures of Γ ~ ℋ ​ ( D n ) \tilde{\Gamma}_{\mathcal{H}}(D_{n}) , and investigate the planarity and non-planarity of Γ ~ ℋ ​ ( D n ) \tilde{\Gamma}_{\mathcal{H}}(D_{n}) . Keywords: Hypergraphs, subgroups, diameter, chromatic number, planar, genus etc. AMS Subject Classification 05C25, 05C65 1 Introduction Hypergraph is a generalization of graph, allowing the analysis of multiple relationships rather than just pair-wise relationships. The notion of hypergraphs has been introduced by C. Berge [ 3 ] . The study of hypergraphs on algebraic structures is an emerging area as a generalization of graph to extend some prominent results from graph theory. In [ 4 ] , P. J. Cameron introduced different types of graphs on groups whose edges reflect the group structures in some way. D. F. Anderson and S. Al-Kaseasbeh [ 2 ] studied on the completeness, bipartiteness and planarity of intersection subgroup graph of a group . In [ 7 ] , P. Devi and R. Rajkumar studied on the complement of the intersection graph of subgroups of a group . They characterized finite groups whose graphs are bipartite, tree, star and planar. In [ 8 ] , Ch. Eslahchi and A. M. Rahimi introduced and studied k-zero divisor hypergraph of a commutative ring. Later, K. Selvakumar et al. [ 1 , 10 , 13 ] introduced and studied on k-maximal hypergraph and k-maximal ideal hypergraph as the extension of the concepts of co-maximal elements and co-maximal ideals of a ring. Also, k-annihilating ideal hypergraph of a ring was studied by K. Selvakumar et al. [ 11 , 12 ] . Recently, in [ 5 ] , P. J. Cameron et al. introduced and studied four types of hypergraphs, namely commuting hypergaphs, power hypergraphs, enhanced power hypergraphs, and generating hypergraphs defined on groups. Motivated from the study of hypergraphs on algebraic structures, we have introduced and studied hypergraphs on the subgroups of a group, in particular the subgroups of dihedral groups. A hypergraph \mathcal{H} is a pair (V(\mathcal{H}),E(\mathcal{H})) of disjoint sets, where V(\mathcal{H}) is a non-empty finite set whose elements are called vertices and the elements of E(\mathcal{H}) are non-empty subsets of V(\mathcal{H}) called hyperedges. Any hypergraph \mathcal{H}^{\prime}=(V^{\prime}(\mathcal{H}^{\prime}),E^{\prime}(\mathcal{H}^{\prime})) such that V^{\prime}(\mathcal{H}^{\prime})\subseteq V(\mathcal{H}) and E^{\prime}(\mathcal{H}^{\prime})\subseteq E(\mathcal{H}) is called a subhypergraph of \mathcal{H} . The path is a vertex–hyperedge alternative sequence, where the vertex belongs to the consecutive hyperedge in the sequence. The cycle is a path whose first vertex is the same as the last vertex. The length of a path is the number of hyperedges in the path. A hypergraph is connected if there exists a path between any pair of vertices, otherwise it is disconnected . The distance between two vertices is the minimum length of the path connecting these two vertices. The diameter of a hypergraph is the maximum distance among all pairs of vertices. The girth of a hypergraph is the length of a shortest cycle it contains. A hypergraph is called a star if there is a vertex which belongs to all hyperedges. The incidence graph (or bipartite representation) \mathcal{I}(\mathcal{H}) of \mathcal{H} is a bipartite graph with vertex V(\mathcal{H})\cup E(\mathcal{H}) and a vertex v\in V(\mathcal{H}) is adjacent to a vertex u\in E(\mathcal{H}) iff v\in u in \mathcal{H} . A proper vertex-coloring (often simply called a proper coloring) of a hypergraph \mathcal{H} is an assignment of colors to the vertices of \mathcal{H} such that no hyperedge contains vertices all of the same color. The chromatic number of \mathcal{H} , denoted by \chi(\mathcal{H}) , is the minimum number of colors used by a proper vertex-coloring of \mathcal{H} . The chromatic index of a hypergraph \mathcal{H} , denoted by \chi^{{}^{\prime}}(\mathcal{H}) , is the minimum number of colors needed to color the edges of \mathcal{H} such that no two intersecting edges have the same color. We denote by S_{n} the surface obtained from the sphere S_{0} by adding n handles. The number n is called the genus of the surface S_{n},n\geq 0 . The orientable genus of a graph G , denoted by g(G) , is the minimum genus of a surface in which G can be embedded. A surface obtained by adding k crosscaps to S_{0} is known as the non-orientable surface N_{k} . The number k is called the crosscap of N_{k} . The non-orientable genus of a graph G , denoted by \tilde{g}(G) , is the smallest integer k such that G can be embedded on N_{k} . A planar graph is a graph of genus (crosscap) 0, a toroidal graph is a graph of genus 1, and a projective-planar graph is a graph of crosscap 1. Further, note that if H is a subgraph of a graph G , then g(H)\leq g(G) and \tilde{g}(H)\leq\tilde{g}(G) . For more details on graphs and hypergraphs, one may refer [ 14 , 16 ] . In Section 2, we have introduced the intersection hypergraph of a group and analyzed some of the structural properties, viz., diameter, girth, chromatic index and chromatic number of the intersection hypergraph \tilde{\Gamma}_{\mathcal{H}}(D_{n}) of D_{n} . Also, we have characterized hypertrees and star hypergraphs in terms of n . In Section 3, we have characterized planar and non-planar hypergraph of D_{n} . 2 Intersection hypergraph of D_{n} and its structural properties We begin this section with the definition of the intersection hypergraph on the subgroups of a group. Our focus is mainly on the study of the intersection hypergraphs \tilde{\Gamma}_{\mathcal{H}}(D_{n}) of dihedral groups. We have examined the structural properties of \tilde{\Gamma}_{\mathcal{H}}(D_{n}) such as diameter, girth, chromatic index and chromatic number. Also, we have characterized the hypergraphs \tilde{\Gamma}_{\mathcal{H}}(D_{n}) that are star hypergraphs and hypertrees. The following definition is motivated from [ 5 ] . Definition 2.1 . Let G be a group and S be the set of all non-trivial proper subgroups of G . The intersection hypergraph of G , denoted by \tilde{\Gamma}_{\mathcal{H}}(G) , is a hypergraph whose vertex set, V=\{H\in S\,\,|\,\,H\cap K=\{e\}\,\,\text{for some $K\in S$}\} and E\subseteq V is a hyperedge if and only if 1. For distinct H,K\,\in E , H\cap K=\{e\}. 2. There does not exist E^{\prime}\supset E which satisfies (1). Example 2.1 . Consider the Klein-4 group, V_{4}=\{e,a,b,c\,|a^{2}=b^{2}=c^{2}=e,\,ab=c=ba,\,ac=b=ca,\,bc=a=cb\}. Then, the vertex set of \tilde{\Gamma}_{\mathcal{H}}(V_{4}) is V=\{\{e,a\},\{e,b\},\{e,c\}\} and the hyperedge set is E=\{\{\{e,a\},\{e,b\},\{e,c\}\}\} . The hypergraph, \tilde{\Gamma}_{\mathcal{H}}(V_{4}) is given in Figure 1 . \{e,b\} \{e,a\} \{e,c\} Figure 1: \tilde{\Gamma}_{\mathcal{H}}(V_{4}) Example 2.2 . Consider the dihedral group of order 8, D_{4}= . The vertex set of \tilde{\Gamma}_{\mathcal{H}}(D_{4}) is V=\{H_{2},H_{3},H_{4},H_{5},H_{6},H_{7},H_{8},H_{9}\} , where H_{2}=,H_{3}=, H_{4}=,H_{5}=,H_{6}=,H_{7}=,H_{8}=, H_{9}= . The hyperedge set of \tilde{\Gamma}_{\mathcal{H}}(D_{4}) is E=\{e_{1},e_{2},e_{3},e_{4}\} , where e_{1}=\{H_{2},H_{3},H_{4},H_{5},H_{6}\} , e_{2}=\{H_{3},H_{4},H_{5},H_{6},H_{7}\} , e_{3}=\{H_{3},H_{5},H_{9}\} and e_{4}=\{H_{4},H_{6},H_{8}\} . Figure 2 depicts the hypergraph \tilde{\Gamma}_{\mathcal{H}}(D_{4}) on D_{4} . e_{1} e_{2} e_{3} e_{4} {H_{2}} {H_{3}} {H_{5}} {H_{7}} {H_{4}} {H_{6}} {H_{9}} {H_{8}} Figure 2: \tilde{\Gamma}_{\mathcal{H}}(D_{4}) \square For a positive integer n\geq 1 , the dihedral group of order 2n , denoted by D_{n} , is defined as D_{n}=. Theorem 2.1 . [ 6 ] Every subgroup of D_{n} is cyclic or dihedral. A complete listing of the subgroups is as follows: 1. , where r\mid n , with index 2 r , 2. , where r\mid n and 0\leq i\leq r-1 , with index r . Every subgroup of D_{n} occurs exactly once in this listing. Remark 2.1 . 1. A subgroup of D_{n} is said to be of Type (1) if it is cyclic as stated in (1) of Theorem 2.1 . 2. A subgroup of D_{n} is said to be of Type (2) if it is dihedral subgroup as stated in (2) of Theorem 2.1 . Note 1 . Since \tilde{\Gamma}_{\mathcal{H}}(D_{n}) is empty for n=1 , we exclude this case and consider n\geq 2 throughout the article. Lemma 2.2 . \tilde{\Gamma}_{\mathcal{H}}(D_{n}) is non empty and moreover, all the proper non-trivial subgroups constitute the vertex set. Proof. If H_{1} is a non-trivial subgroup of D_{n} of Type (1) , then choose K_{1}==\{e,b\} . Hence, H_{1}\cap K_{1}=\{e\} and therefore, H_{1}\,\in\,V(\tilde{\Gamma}_{\mathcal{H}}(D_{n})) . If H_{2} is a proper subgroup of D_{n} of Type (2) , then there exists j\in\{0,1,2,\cdots,n-1\} such that a^{j}b\notin H_{2} . For K_{2}==\{e,a^{j}b\} , we have H_{2}\cap K_{2}=\{e\} . Hence, H_{2}\,\in\,V(\tilde{\Gamma}_{\mathcal{H}}(D_{n})) . ∎ In the following theorem, we established that \tilde{\Gamma}_{\mathcal{H}}(D_{n}) is connected and its diameter is atmost 3. Theorem 2.3 . \tilde{\Gamma}_{\mathcal{H}}(D_{n}) is connected and diam(\tilde{\Gamma}_{\mathcal{H}}(D_{n}) ) \leq 3 . Proof. Let H_{1},H_{2} be two distinct vertices of \tilde{\Gamma}_{\mathcal{H}}(D_{n}) . We prove that there exists a path from H_{1} to H_{2} and d(H_{1},H_{2})\leq 3 . If H_{1}\cap H_{2}=\{e\} , then there exists a hyperedge e_{1} containing H_{1} and H_{2} . Thus, H_{1}e_{1}H_{2} is a shortest path from H_{1}\,\text{to}\,H_{2} and d(H_{1},H_{2})=1 . e_{1} {H_{1}} {H_{2}} If H_{1}\cap H_{2}\neq\{e\} , we have the following cases: Case 1. Both H_{1} and H_{2} are of Type (1). Consider H_{3}==\{e,b\} . Observe that H_{1}\cap H_{3}=\{e\}\,\text{and}\,H_{2}\cap H_{3}=\{e\} . Therefore, there exist two distinct hyperedges e_{1}\,\text{and}\,e_{2} such that e_{1} contains H_{1}\,\text{and}\,H_{3} , and e_{2} contains H_{2}\,\text{and}\,H_{3} . Thus, H_{1}e_{1}H_{3}e_{2}H_{2} is a shortest path from H_{1} to H_{2} and d(H_{1},H_{2})=2 . e_{1} e_{2} {H_{1}} {H_{3}} {H_{2}} Case 2. One is of Type (1) and the other is of Type (2). Choose j\in\{0,1,2,\cdots,n-1\} such that a^{j}b\notin H_{1}\cup H_{2} . Consider H_{3}==\{e,a^{j}b\} . Observe that H_{1}\cap H_{3}=\{e\}\,\text{and}\,H_{2}\cap H_{3}=\{e\} . Therefore, there exist two distinct hyperedges e_{1}\,\text{and}\,e_{2} such that e_{1} contains H_{1}\,\text{and}\,H_{3} , and e_{2} contains H_{2}\,\text{and}\,H_{3} . Thus, H_{1}e_{1}H_{3}e_{2}H_{2} is a shortest path from H_{1} to H_{2} and d(H_{1},H_{2})=2 . Case 3. Both H_{1} and H_{2} are of Type (2). Let H_{1}= and H_{2}= , where r_{1}\neq 1,r_{2}\neq 1,\,r_{1},r_{2}\mid n and i,j are fixed positive integers such that 0\leq i\leq r_{1}-1 and 0\leq j\leq r_{2}-1 . Consider the following subcases: \underline{\textbf{Subcase 3.1.}} If r_{1}=r_{2} , \underline{\textbf{Subcase 3.1.(a)}} If there exists a positive integer r_{0} such that r_{0}\cap =\{e\} , then consider H_{3}= . Hence, H_{1}\cap H_{3}=\{e\}\,\text{and}\,H_{2}\cap H_{3}=\{e\} . Therefore, there exist two distinct hyperedges e_{1}\,\text{and}\,e_{2} such that e_{1} contains H_{1}\,\text{and}\,H_{3} , and e_{2} contains H_{2}\,\text{and}\,H_{3} . Thus, H_{1}e_{1}H_{3}e_{2}H_{2} is a shortest path from H_{1} to H_{2} and d(H_{1},H_{2})=2 . \underline{\textbf{Subcase 3.1.(b)}} If there does not exists any r_{0} such that \cap=\{e\} , then consider the following: If there exists l\in\{0,1,2,\cdots,n-1\} such that a^{l}b\notin H_{1}\cup H_{2} , then for H_{3}==\{e,a^{l}b\} , we have H_{1}\cap H_{3}=\{e\}\,\text{and}\,H_{2}\cap H_{3}=\{e\} . Therefore, there exist two distinct hyperedges e_{1}\,\text{and}\,e_{2} such that e_{1} contains H_{1}\,\text{and}\,H_{3} , and e_{2} contains H_{2}\,\text{and}\,H_{3} . Thus, H_{1}e_{1}H_{3}e_{2}H_{2} is a shortest path from H_{1} to H_{2} and d(H_{1},H_{2})=2 . If such l does not exist, then choose l_{1} and l_{2} from the set \{0,1,2,\cdots,n-1\} such that a^{l_{1}}b\notin H_{1} but a^{l_{1}}b\in H_{2} and a^{l_{2}}b\notin H_{2} but a^{l_{2}}b\in H_{1} . Consider K_{1}==\{e,a^{l_{1}}b\} and K_{2}= =\{e,a^{l_{2}}b\} . Observe that H_{1}\cap K_{1}=\{e\},\,\,K_{1}\cap K_{2}=\{e\} and H_{2}\cap K_{2}=\{e\} . Hence there exist distinct hyperedges e_{1},e_{2},e_{3} such that e_{1} contains H_{1}\,\text{and}\,K_{1} , e_{2}\,\text{contains}\,K_{1}\,\text{and}\,K_{2} , and e_{3}\,\text{contains}\,H_{2}\,\text{and}\,K_{2} . Hence, H_{1}e_{1}K_{1}e_{2}K_{2}e_{3}H_{2} is a shortest path from H_{1}\,\text{to}\,H_{2} and d(H_{1},H_{2})=3 . e_{1} e_{2} e_{3} {H_{1}} {H_{2}} {K_{2}} {K_{1}} \underline{\textbf{Subcase 3.2.}} If r_{1}\neq r_{2} , Choose l_{1}\in\{0,1,2,\cdots,n-1\} such that l_{1}\not\equiv i(mod\,r_{1}) and l_{1}\not\equiv j(mod\,r_{2}) and so a^{l_{1}}b\notin H_{1}\cup H_{2} . For H_{3}==\{e,a^{l_{1}}b\} , we have H_{1}\cap H_{3}=\{e\}\,\text{and}\,H_{2}\cap H_{3}=\{e\} . Therefore, there exist two distinct hyperedges e_{1}\,\text{and}\,e_{2} such that e_{1} contains H_{1}\,\text{and}\,H_{3} , and e_{2} contains H_{2}\,\text{and}\,H_{3} . Thus, H_{1}e_{1}H_{3}e_{2}H_{2} is a shortest path from H_{1} to H_{2} and d(H_{1},H_{2})=2 . ∎ Corollary 2.3.1 . The diameter, diam(\tilde{\Gamma}_{\mathcal{H}}(D_{n}))=\begin{cases}1,\,\text{$n$ is a prime},\\ 3,\,n=4k\,\,\text{where $k$ is a positive integer},\\ 2,\,\text{otherwise}.\end{cases} Corollary 2.3.2 . The chromatic index, \chi^{{}^{\prime}}(\tilde{\Gamma}_{\mathcal{H}}(D_{n}))=\begin{cases}m-1,\,n=4k\,\,\text{where $k$ is a positive integer},\\ m,\,\text{otherwise}.\end{cases} where m denotes the number of hyperedges of \tilde{\Gamma}_{\mathcal{H}}(D_{n}) . Proof. Let e_{1},e_{2} be two hyperedges of \tilde{\Gamma}_{\mathcal{H}}(D_{n}) . If dist(e_{1},e_{2}) is the minimum number of hyperedges in a sequence of incident hyperedges connecting e_{1} and e_{2} , then diam(\tilde{\Gamma}_{\mathcal{H}}(D_{n}))=max_{e_{1},e_{2}\in E}\,dist(e_{1},e_{2}), where E is the hyperedge set of \tilde{\Gamma}_{\mathcal{H}}(D_{n}). Therefore, from the Corollary 2.3.1 , max_{e_{1},e_{2}\in E}\,dist(e_{1},e_{2})=\begin{cases}1,\,\text{n is a prime},\\ 3,\,n=4k\,\,\text{where $k$ is a positive integer},\\ 2,\,\text{otherwise}.\end{cases} If max_{e_{1},e_{2}\in E}\,dist(e_{1},e_{2})\leq 2 , then any two hyperedges in the hypergraph are incident. If n\neq 4k, then, by Theorem 2.3 , all the hyperedges of \tilde{\Gamma}_{\mathcal{H}}(D_{n}) are incident. Hence, \chi^{{}^{\prime}}(\tilde{\Gamma}_{\mathcal{H}}(D_{n}))=m . Now, if n=4k where k is a positive integer, by the proof of Theorem 2.3 , the hyperedge containing and the hyperedge containing are not incident and they are the only two non-incident hyperedges of the hypergraph \tilde{\Gamma}_{\mathcal{H}}(D_{n}) . Hence, \chi^{{}^{\prime}}(\tilde{\Gamma}_{\mathcal{H}}(D_{n}))=m-1 . ∎ In the following theorem, we have provided the necessary and sufficient conditions under which \tilde{\Gamma}_{\mathcal{H}}(D_{n}) is a star hypergraph. Theorem 2.4 . For hypergraph \tilde{\Gamma}_{\mathcal{H}}(D_{n}) of D_{n} , the following are equivalent: 1. n is prime. 2. \tilde{\Gamma}_{\mathcal{H}}(D_{n}) has exactly one hyperedge. 3. \tilde{\Gamma}_{\mathcal{H}}(D_{n}) is star. Proof. ( 1\Rightarrow 2 ). Suppose that n=p , a prime number. Then, is the only non-trivial subgroup of D_{n} of Type (1) and the non-trivial proper subgroup of D_{n} of Type (2) are \{\,|\,0\leq i\leq p-1\} . Observe that, \cap=\{e\}\,\,\text{for}\,\,0\leq i\leq p-1 and, \cap=\{e\} for all distinct i,j\in\{0,1,2,\cdots,p-1\} . Therefore, \tilde{\Gamma}_{\mathcal{H}}(D_{n}) has exactly one hyperedge. ( 2\Rightarrow 3 ). Suppose that \tilde{\Gamma}_{\mathcal{H}}(D_{n}) has exactly one hyperedge. If \tilde{\Gamma}_{\mathcal{H}}(D_{n}) is not a star, then for each vertex H_{0} of \tilde{\Gamma}_{\mathcal{H}}(D_{n}) , there exists a hyperedge that does not contain H_{0} which is a contradiction. Therefore, \tilde{\Gamma}_{\mathcal{H}}(D_{n}) must be a star. ( 3\Rightarrow 1 ). Suppose that \tilde{\Gamma}_{\mathcal{H}}(D_{n}) is a star. If n is not a prime, then we claim that for each vertex H_{0} of \tilde{\Gamma}_{\mathcal{H}}(D_{n}) , there exists an another vertex H_{1} such that H_{0}\cap H_{1}\neq\{e\} . To prove the claim, consider the following cases: Case 1. n=p^{\alpha} , for some prime p and \alpha\geq 2 . \underline{\textbf{Subcase 1.1.}} Let H_{0} be of Type (1) . Suppose H_{0}= , for fixed r such that r\mid n and r\neq n . \underline{\textbf{Subcase 1.1.(a).}} If r=1 , then for H_{1}= , H_{0}\cap H_{1}=\neq\{e\} . \underline{\textbf{Subcase 1.1.(b).}} If r\neq 1 , then for H_{1}= , H_{0}\cap H_{1}=\neq\{e\} . \underline{\textbf{Subcase 1.2.}} Let H_{0} be of Type (2) . Suppose H_{0}= , for fixed r such that r\neq 1,\,r\mid n and for fixed i such that 0\leq i\leq r-1 . \underline{\textbf{Subcase 1.2.(a).}} If r=n , then H_{0}==\{e,a^{i}b\} . Now, choose l\in\{0,1,2,...,p-1\} such that l\equiv i(mod\,p) and consider H_{1}= . Hence, H_{0}\cap H_{1}=\neq\{e\} . \underline{\textbf{Subcase 1.2.(b).}} If r\neq n , then choose H_{1}==\{e,a^{i}b\} and hence H_{0}\cap H_{1}=\neq\{e\} . Case 2. n has at least two distinct prime divisors, i.e., n=p_{1}p_{2}\prod_{i}p_{i}^{\alpha_{i}} , where p_{1},p_{2} are distinct primes and \alpha_{i} ’s are non-negative integers. \underline{\textbf{Subcase 2.1.}} Let H_{0} be of Type (1) . Suppose H_{0}= , for fixed r such that r\mid n and r\neq n . \underline{\textbf{Subcase 2.1.(a)}} If r=1 , then for H_{1}= , H_{0}\cap H_{1}=\neq\{e\} . \underline{\textbf{Subcase 2.1.(b)}} If r\neq 1 , then for H_{1}= , H_{0}\cap H_{1}=\neq\{e\} . \underline{\textbf{Subcase 2.2.}} Let H_{0} be of Type (2) . Suppose H_{0}= , for fixed r such that r\neq 1,\,r\mid n and for fixed i such that 0\leq i\leq r-1 . \underline{\textbf{Subcase 2.2(a)}}. If r=n , then H_{0}==\{e,a^{i}b\} . Choose l\in\{0,1,2,...,{p_{1}}-1\} such that l\equiv i(mod\,p_{1}) and choose the subgroup H_{1}= . \underline{\textbf{Subcase 2.2.(b).}} If r\neq n , then choose H_{1}==\{e,a^{i}b\} and hence H_{0}\cap H_{1}=\neq\{e\} . From all the cases above, we have proved that for each vertex H_{0} of \tilde{\Gamma}_{\mathcal{H}}(D_{n}) , there exists an another vertex H_{1} such that H_{0}\cap H_{1}\neq\{e\} . So, there exists a hyperedge not containing H_{0} which is a contradiction. ∎ We need the following definitions and results to characterize hypergraphs \tilde{\Gamma}_{\mathcal{H}}(D_{n}) of D_{n} that are hypertrees in terms of n . Definition 2.2 . [ 14 ] A host graph for a hypergraph is a connected graph on the same vertex set such that every hyperedge induces a connected subgraph of the host graph. A hypergraph \mathcal{H}=(X,\mathcal{D}) is called a hypertree if there exists a host tree T=(X,E) such that each edge D\in\mathcal{D} induces a subtree in T . Definition 2.3 . [ 14 ] A hypergraph \mathcal{H} has the Helly property (is Helly, for short) if for every subfamily of its edges the following implication holds: If every two edges of the subfamily have a non-empty intersection, then the whole subfamily has a non-empty intersection. Definition 2.4 . [ 14 ] The line graph of a hypergraph \mathcal{H}=(X,\mathcal{D}) , denoted by \mathcal{L}(\mathcal{H}) , is the graph with the set \mathcal{D} as the vertex set and two vertices are adjacent iff the respective edges intersect. Definition 2.5 . [ 14 ] A hypergraph is called chordal if every cycle of length \geq 4 has two non-consecutive vertices which are adjacent. Lemma 2.5 . [ 14 ] Every hypertree is a Helly hypergraph. Lemma 2.6 . [ 14 ] A hypergraph \mathcal{H} is a hypertree iff \mathcal{H} is Helly and \mathcal{L}(\mathcal{H}) is chordal. Theorem 2.7 . \tilde{\Gamma}_{\mathcal{H}}(D_{n}) is a hypertree iff n is a prime or n=4 . Proof. Suppose that \tilde{\Gamma}_{\mathcal{H}}(D_{n}) is a hypertree. If n is neither a prime nor n=4 , then consider the following cases: Case 1. n=4k\,\,\text{for some positive integer $k\geq 2$} . Consider \mathcal{S} as the set of all hyperedges of \tilde{\Gamma}_{\mathcal{H}}(D_{n}) except the hyperedge e_{1} , where e_{1} contains . Then, from the proof of Corollary 2.3.2 , \mathcal{S} is a subfamily of hyperedge set of \tilde{\Gamma}_{\mathcal{H}}(D_{n}) such that any two hyperedges in \mathcal{S} have a non-empty intersection. Now, we claim that no vertex belongs to all the hyperedges of \mathcal{S} , i.e., for each vertex H_{0} , there exists a hyperedge e_{2}\in\mathcal{S} such that H_{0}\notin e_{2} and so \tilde{\Gamma}_{\mathcal{H}}(D_{n}) does not satisfy the Helly property. Therefore, by Lemma 2.5 , \tilde{\Gamma}_{\mathcal{H}}(D_{n}) is not a hypertree which is a contradiction. To prove the claim, consider the following cases: Subcase 1.1. Let H_{0} be of Type (1) . Suppose H_{0}= , for fixed r such that r\mid n and r\neq n . \underline{Subcase\,1.1.(a).} If r=1 , then consider the hyperedge e_{2}=\{,,\cdots,,\\ \}. Clearly, e_{2}\in\mathcal{S} . But H_{0}\,\cap=\neq\{e\} and therefore, H_{0}\notin e_{2} . \underline{Subcase\,1.1.(b).} If r\neq 1 , then consider the hyperedge e_{2}=\{,,\cdots,,\\ \}. Clearly, e_{2}\in\mathcal{S} . But H_{0}\,\cap=\neq\{e\} and therefore, H_{0}\notin e_{2} . Subcase 1.2. Let H_{0} be of Type (2) . Suppose H_{0}= , for fixed r such that r\neq 1,\,r\mid n and for fixed i such that 0\leq i\leq r-1 . \underline{Subcase\,1.2.(a).} If r=n , then consider e_{2} be the hyperedge containing , where l\equiv i(mod\,4) . Clearly, e_{2}\in\mathcal{S} but H_{0}\,\cap=\neq\{e\}. Therefore, H_{0}\notin e_{2} . \underline{Subcase\,1.2.(b).} If r\neq n , then choose e_{2} be a hyperedge containing in \mathcal{S} . Observe that H_{0}\,\cap =\neq\{e\} and therefore H_{0}\notin e_{2} . Case 2. n\neq 4k for any k\geq 2 . By Theorem 2.3 , any two hyperedges of \tilde{\Gamma}_{\mathcal{H}}(D_{n}) have a non-empty intersection. But, by Theorem 2.4 , no vertex belongs to all the hyperedges of \tilde{\Gamma}_{\mathcal{H}}(D_{n}) . Thus, \tilde{\Gamma}_{\mathcal{H}}(D_{n}) does not satisfy Helly property and so by Lemma 2.5 , \tilde{\Gamma}_{\mathcal{H}}(D_{n}) is not a hypertree which is a contradiction. Conversely, first suppose that n is prime. Then, by Theorem 2.4 , \tilde{\Gamma}_{\mathcal{H}}(D_{n}) has a single hyperedge consists of p+1 vertices, say H_{1},H_{2},\cdots,H_{p+1} . Figure 3 depicts a host tree of \tilde{\Gamma}_{\mathcal{H}}(D_{n}) and therefore \tilde{\Gamma}_{\mathcal{H}}(D_{n}) is a hypertree. H_{1} H_{2} H_{3} H_{p} H_{p+1} Figure 3: Host tree of \tilde{\Gamma}_{\mathcal{H}}(D_{n}) , when n is a prime. Now, for n=4 , we have the group D_{4} as given in Example 2.2 . Clearly, \tilde{\Gamma}_{\mathcal{H}}(D_{4}) is Helly. Now, the line graph \mathcal{L}(\tilde{\Gamma}_{\mathcal{H}}(D_{4})) of \tilde{\Gamma}_{\mathcal{H}}(D_{4}) as depicted in Figure 4 is chordal. Therefore, by Lemma 2.6 , \tilde{\Gamma}_{\mathcal{H}}(D_{4}) is a hypertree. e_{1} e_{2} e_{3} e_{4} Figure 4: \mathcal{L}(\tilde{\Gamma}_{\mathcal{H}}(D_{4})) ∎ In the following theorem, we find the girth of the hypergraph, \tilde{\Gamma}_{\mathcal{H}}(D_{n}) . Theorem 2.8 . gr(\tilde{\Gamma}_{\mathcal{H}}(D_{n}))\in\{2,\infty\} . Proof. Consider the following cases. Case 1. If n=p , a prime number, then by Theorem 2.4 , \tilde{\Gamma}_{\mathcal{H}}(D_{n}) has exactly one hyperedge. Thus, the hypergraph does not contain a cycle and so gr(\tilde{\Gamma}_{\mathcal{H}}(D_{n}))=\infty . Case 2. If n is not a prime, then consider H_{1}=\{e,b\} and H_{2}=\{e,ab\} . Clearly, H_{1}\,\cap\,H_{2}=\{e\} . We claim that there exist two distinct hyperedges e_{1} and e_{2} such that both contains H_{1} and H_{2} , and so H_{1}e_{1}H_{2}e_{2}H_{1} is a shortest cycle of length 2. Hence, gr(\tilde{\Gamma}_{\mathcal{H}}(D_{n}))=2 . e_{1} e_{2} {H_{1}} {H_{2}} {K_{2}} {K_{1}} Consider the following cases: \underline{\text{Subcase}\,\,2.1}\hskip 9.24994pt\text{Suppose}\,n=p^{\alpha},\,\text{for some prime $p$}\,\text{and}\,\alpha\geq 2 . Then, consider K_{1}= and K_{2}= . Observe that H_{i}\cap K_{j}=\{e\} for all i,j\in\{1,2\} and K_{1}\cap K_{2}\neq\{e\} . Therefore, there exist two distinct hyperedges e_{1},e_{2} such that e_{1} contains H_{1},H_{2}\,\text{and}\,K_{1} , and e_{2} contains H_{1},H_{2}\,\text{and}\,K_{2} . \underline{\text{Subcase}\,\,2.2}\hskip 9.24994pt\text{Suppose}\,n contains atleast two distinct prime divisors. i.e., n=p_{1}p_{2}\prod_{i}p_{i}^{\alpha_{i}}, where p_{1},p_{2} are distinct primes and \alpha_{i} ’s are non-negative integers. Consider K_{1}=\,\text{and}\,K_{2}= . Observe that H_{i}\cap K_{j}=\{e\} for all i,j\in\{1,2\} and K_{1}\cap K_{2}\neq\{e\} . Therefore, there exists two distinct hyperedges e_{1},e_{2} such that e_{1} contains H_{1},H_{2} and K_{1} , and e_{2} contains H_{1},H_{2},\,\text{and}\,K_{2} . ∎ The following result discusses the chromatic number of \tilde{\Gamma}_{\mathcal{H}}(D_{n}) . Theorem 2.9 . The chromatic number, \chi(\tilde{\Gamma}_{\mathcal{H}}(D_{n}))=2. Proof. Divide the vertex set of \tilde{\Gamma}_{\mathcal{H}}(D_{n}) into two sets A\,\text{and}\,B , where A=\{,\,|\,i\in\{1,2,\cdots,n-1\},\,d\mid n,\,\text{and}\,1\leq j\leq d-1\} and B=\{,,\,|\,d\mid n\} . We claim that every hyperedge of \tilde{\Gamma}_{\mathcal{H}}(D_{n}) has at least one vertex from A as well as B. Let e_{1} be a hyperedge of \tilde{\Gamma}_{\mathcal{H}}(D_{n}) . If e_{1} contains only vertices from B , then we can find a vertex in A for some i\in\{1,2,\cdots,n-1\} such that \cap\,\,H=\{e\} , for all H\in e_{1} . Hence, the vertex must belongs to e_{1} and this contradicts the maximality of e_{1} . Similarly, the hyperedge cannot contain only vertices from the set A . Hence, each hyperedge has at least one vertex from both A and B. Assign the color c_{1} to the vertices in A and the color c_{2} to the vertices in B . This is a proper coloring of \tilde{\Gamma}_{\mathcal{H}}(D_{n}) . Consequently, \chi(\tilde{\Gamma}_{\mathcal{H}}(D_{n}))=2. ∎ 3 Planarity and Non-Planarity of hypergraph To discuss the planarity and orientable genus of \tilde{\Gamma}_{\mathcal{H}}(D_{n}) on D_{n} , we need the following results. Theorem 3.1 . [ 15 ] A graph G is planar iff it contains no subdivision of K_{5} or K_{3,3} . Theorem 3.2 . [ 15 ] A hypergraph is planar iff its incidence graph is planar. Lemma 3.3 . [ 16 ] If G is a graph with n vertices, m edges, girth gr and genus g , then \dfrac{m(gr-2)}{2\cdot gr}-\dfrac{n}{2}+1\leq g Theorem 3.4 . [ 15 ] For any hypergraph \mathcal{H} , g(\mathcal{H})=g(\mathcal{I}(\mathcal{H})) . The following two results characterize planarity and non-planarity of the hypergraph \tilde{\Gamma}_{\mathcal{H}}(D_{n}) on D_{n} . We characterize the hypergraph \tilde{\Gamma}_{\mathcal{H}}(D_{n}) which are planar in terms of n . Also, we characterize the non-planar hypergraph \tilde{\Gamma}_{\mathcal{H}}(D_{n}) in terms of genus of its incidence graph. Theorem 3.5 . \tilde{\Gamma}_{\mathcal{H}}(D_{n}) is planar iff n is a prime or n=4 . Proof. Suppose that \tilde{\Gamma}_{\mathcal{H}}(D_{n}) is planar. Assume n is neither a prime nor n=4 . We will find three distinct vertices H_{1},H_{2},H_{3} of \tilde{\Gamma}_{\mathcal{H}}(D_{n}) and three distinct hyperedges e_{1},e_{2},e_{3} of \tilde{\Gamma}_{\mathcal{H}}(D_{n}) such that all H_{1},H_{2},H_{3} belongs to each e_{1},e_{2},e_{3} . Consider the subhypergraph G of \tilde{\Gamma}_{\mathcal{H}}(D_{n}) with \{e_{1},e_{2},e_{3}\} as hyperedge set and the set of all vertices in e_{1},e_{2},\,\text{and}\,\,e_{3} as the vertex set of G . So, the incidence graph \mathcal{I}(G) of G contain K_{3,3} . Hence, the incidence graph \mathcal{I}(\tilde{\Gamma}_{\mathcal{H}}(D_{n})) of \tilde{\Gamma}_{\mathcal{H}}(D_{n}) , contains K_{3,3} and so \tilde{\Gamma}_{\mathcal{H}}(D_{n}) is non-planar, a contradiction. e_{1} e_{2} e_{3} {H_{1}} {H_{2}} {H_{3}} {K_{2}} {K_{1}} {K_{3}} (a) H_{1} H_{2} H_{3} e_{1} e_{2} e_{3} (b) Choose K_{1}=,K_{2}=\,\text{and}\,K_{3}= , where p is a prime divisor of n . Also, choose positive integers l_{1},l_{2},l_{3} from the set \{0,1,2,\cdots,n-1\} such that l_{i}\not\equiv 0(mod\,p) . So, a^{l_{1}}b,a^{l_{2}}b,a^{l_{3}}b\notin K_{3} . Consider H_{1}= ,H_{2}=\,\text{and}\,H_{3}= . Thus, H_{i}\cap H_{j}=\{e\} for i\neq j\,\text{and}\,i,j\in\{1,2,3\}. Also, K_{i}\cap K_{j}\neq\{e\} and H_{i}\cap K_{j}=\{e\}\,\,\text{for all}\,\,i,j\in\{1,2,3\}. Hence, there exists three distinct hyperedges e_{1},e_{2},e_{3} such that e_{1} contains H_{1},H_{2},H_{3} and K_{1} , e_{2} contains H_{1},H_{2},H_{3} and K_{2} , and e_{3} contains H_{1},H_{2},H_{3} and K_{3} . Conversely, first suppose that n is prime. By Theorem 2.4 , \tilde{\Gamma}_{\mathcal{H}}(D_{n}) has a single hyperedge. So, the corresponding incidence graph can be embedded on a plane and hence, \tilde{\Gamma}_{\mathcal{H}}(D_{n}) is planar. Now, for n=4 , we have the group D_{4} as given in Example 2.2 . The incidence graph \mathcal{I}(\tilde{\Gamma}_{\mathcal{H}}(D_{4})) of \tilde{\Gamma}_{\mathcal{H}}(D_{4}) is depicted in Figure 6 . Clearly, \mathcal{I}(\tilde{\Gamma}_{\mathcal{H}}(D_{4})) can be embedded on a plane. So, \tilde{\Gamma}_{\mathcal{H}}(D_{4}) is planar. H_{2} H_{3} H_{4} H_{5} H_{6} H_{7} H_{8} H_{9} e_{1} e_{2} e_{3} e_{4} Figure 6: \mathcal{I}(\tilde{\Gamma}_{\mathcal{H}}(D_{4})) ∎ Theorem 3.6 . \tilde{\Gamma}_{\mathcal{H}}(D_{n}) is non-planar iff the orientable genus, g(\tilde{\Gamma}_{\mathcal{H}}(D_{n})) is at least 2. Proof. It is clear that if the genus g(\tilde{\Gamma}_{\mathcal{H}}(D_{n})) is at least two, then \tilde{\Gamma}_{\mathcal{H}}(D_{n}) is non-planar. Conversely, suppose that \tilde{\Gamma}_{\mathcal{H}}(D_{n}) is non-planar. Now, by Theorem 3.5 , \tilde{\Gamma}_{\mathcal{H}}(D_{n}) is non-planar iff n is neither a prime nor n=4 . To prove that g(\tilde{\Gamma}_{\mathcal{H}}(D_{n})) is atleast 2, we consider the following cases: Case 1 . n is even. \underline{\textbf{Subcase 1.1}} Suppose n=6 . The non-trivial proper subgroups of D_{6} are as follows: H_{2}=,H_{3}=,H_{4}=\{e,b\},H_{5}=\{e,a^{3}b\},H_{6}=\{e,ab\},H_{7}=\{e,a^{4}b\},H_{8}=\{e,a^{2}b\},\\ H_{9}=\{e,a^{3}b\},H_{10}=,H_{11}=,H_{12}=,H_{13}=,H_{14}=,\\ H_{15}= . So, the hyperedges of \tilde{\Gamma}_{\mathcal{H}}(D_{6}) are: e_{1}=\{H_{2},H_{3},H_{4},H_{5},H_{6},H_{7},H_{8},H_{9}\} , e_{2}=\{H_{2},H_{4},H_{5},H_{8},H_{9},H_{14}\} , e_{3}=\{H_{2},H_{4},H_{5},H_{6},H_{7},H_{15}\} , e_{4}=\{H_{2},H_{6},H_{7},H_{8},H_{9},H_{13}\} , e_{5}=\{H_{3},H_{4},H_{7},H_{8},H_{10}\} , e_{6}=\{H_{3},H_{5},H_{6},H_{9},H_{12}\} and e_{7}=\{H_{4},H_{5},H_{6},H_{7},H_{8},H_{9},H_{11}\} . In the incidence graph \mathcal{I}(\tilde{\Gamma}_{\mathcal{H}}(D_{6})) of \tilde{\Gamma}_{\mathcal{H}}(D_{6}) , the number of vertices, n_{0}=21 , the number of edges, m=43 and the girth, gr=4 , as H_{2}e_{1}H_{4}e_{2}H_{2} is a shortest cycle of length 4 in \mathcal{I}(\tilde{\Gamma}_{\mathcal{H}}(D_{6})) . Thus, by Lemma 3.3 , the genus g(\mathcal{I}(\tilde{\Gamma}_{\mathcal{H}}(D_{6})))\geq\dfrac{m(gr-2)}{2\cdot gr}-\dfrac{n_{0}}{2}+1=\dfrac{43\cdot 2}{2\cdot 4}-\dfrac{21}{2}+1=1.25. Consequently, by Theorem 3.4 g(\tilde{\Gamma}_{\mathcal{H}}(D_{6})) is at least 2. \underline{\textbf{Subcase 1.2}} Suppose n\geq 8 . Let G be the subhypergraph \tilde{\Gamma}_{\mathcal{H}}(D_{n}) induced by the vertex set, \Omega=\{H_{0},H_{1},...,H_{n-1},,,,,\}, where H_{i}=,\,i\in\{0,1,...,n-1\} . Hence, e_{1}=\{H_{0},H_{1},...,H_{n-1},\} , e_{2}=\{H_{0},H_{1},...,H_{n-1},\} , e_{3}=\{H_{1},H_{2}...,H_{n-1},\} , e_{4}=\{H_{0},H_{2},...,H_{n-1},\} and e_{5}=\{H_{0},H_{1},...,H_{n-1},\} are the only hyperedges of the subhypergraph G induced by \Omega . Consider the corresponding incidence graph \mathcal{I}(G) of G . In \mathcal{I}(G) , the number of vertices, n_{0}=(n+5)+5, the number of edges, m=5n-1, and the girth, gr=4 . So, by Lemma 3.3 and as n\geq 8 , \displaystyle g(\mathcal{I}(\tilde{\Gamma}_{\mathcal{H}}(D_{n})))\geq\dfrac{m\cdot(gr-2)}{2\cdot gr}-\dfrac{n_{0}}{2}+1 \displaystyle\geq\dfrac{(5n-1)(4-2)}{2\cdot 4}-\dfrac{n+10}{2}+1 \displaystyle=\dfrac{3n-17}{4} \displaystyle\geq 1.75. Consequently, by Theorem 3.4 , g(\tilde{\Gamma}_{\mathcal{H}}(D_{n})) is at least 2. Case 2 . n is odd. \underline{\textbf{Subcase 2.1}} : n=p^{\alpha},\,p\,\,\text{is an odd prime}\,\text{and}\,\alpha\geq 2. \underline{\textbf{Subcase 2.1(a)}}: Suppose p=3\,\text{and}\,\alpha=2,\,\,\text{i.e.,}\,n=3^{2}=9 . The non-trivial proper subgroups of D_{9} are as follows: H_{2}=,H_{3}=,H_{4}=\{e,b\},H_{5}=\{e,ab\},H_{6}=\{e,a^{2}b\},H_{7}=\{e,a^{3}b\},\\ H_{8}=\{e,a^{4}b\},H_{9}=\{e,a^{5}b\},H_{10}=\{e,a^{6}b\},H_{11}=\{e,a^{7}b\},H_{12}=\{e,a^{8}b\},H_{13}=,\\ H_{14}=,H_{15}= . The following are the hyperedges of \tilde{\Gamma}_{\mathcal{H}}(D_{9}) : e_{1}=\{H_{2},H_{4},H_{5},H_{6},H_{7},H_{8},H_{9},H_{10},H_{11},H_{12}\} , e_{2}=\{H_{3},H_{4},H_{5},H_{6},H_{7},H_{8},H_{9},H_{10},H_{11},H_{12}\} , e_{3}=\{H_{5},H_{6},H_{8},H_{9},H_{11},H_{12},H_{13}\} , e_{4}=\{H_{4},H_{6},H_{7},H_{9},H_{10},H_{12},H_{14}\} and e_{5}=\{H_{4},H_{5},H_{7},H_{8},H_{10},H_{11},H_{15}\} . In the incidence graph \mathcal{I}(\tilde{\Gamma}_{\mathcal{H}}(D_{9})) of \tilde{\Gamma}_{\mathcal{H}}(D_{9}) , the number of vertices, n_{0}=19 , the number of edges, m=41 and the girth, gr=4 as H_{4}e_{1}H_{5}e_{2}H_{4} is a shortest cycle of length 4 in \mathcal{I}(\tilde{\Gamma}_{\mathcal{H}}(D_{9})) . Thus, the genus g(\mathcal{I}(\tilde{\Gamma}_{\mathcal{H}}(D_{9})))\geq\dfrac{m\cdot(gr-2)}{2\cdot gr}-\dfrac{n_{0}}{2}+1=\dfrac{41\cdot 2}{2\cdot 4}-\dfrac{19}{2}+1=1.75. Consequently, by Theorem 3.4 , g(\tilde{\Gamma}_{\mathcal{H}}(D_{9})) is at least 2. \underline{\textbf{Subcase 2.1(b)}}: Suppose n=p^{\alpha}>9\,\text{and}\,\alpha=2,\,\text{i.e.,}\,p^{2}>9. Consider the subhypergraph G induced by the vertex set \Omega=\{H_{0},H_{1},...,H_{p^{2}-1},,,\}, where H_{i}=,\,\\ i\in\{0,1,...,2^{\alpha}-1\} . So, the hyperedges of the subhypergraph G induced by \Omega are: e_{1}=\{H_{0},H_{1},...,H_{p^{2}-1},\} , e_{2}=\{H_{0},H_{1},...,H_{p^{2}-1},\} and e_{3}=\{H_{0},H_{1},...,H_{p^{2}-1},\} . In the incidence graph \mathcal{I}(G) of G , the number of vertices, n_{0}=(p^{2}+3)+3=p^{2}+6, the number of edges, m=(p^{2}+1)\cdot 2+p^{2}-p+1=3\cdot p^{2}-p+3, and the girth, gr=4 . So, by Lemma 3.3 and as p\geq 5 , \displaystyle g(\mathcal{I}(G))\geq\dfrac{m\cdot(gr-2)}{2\cdot gr}-\dfrac{n_{0}}{2}+1 \displaystyle=\dfrac{(3\cdot p^{2}-p+3)(4-2)}{2\cdot 4}-\dfrac{p^{2}+6}{2}+1 \displaystyle=\dfrac{p(p-1)}{4}-\,1.25 \displaystyle\geq 5-1.25=3.75. Consequently, by Theorem 3.4 , g(\tilde{\Gamma}_{\mathcal{H}}(D_{n}))>2 . \underline{\textbf{Subcase 2.1(c)}}: Suppose n=p^{\alpha}>9\,\text{and}\,\alpha\geq 3. Consider the subhypergraph G induced by the vertex set, \Omega=\{H_{0},H_{1},...,H_{p^{\alpha}-1},K_{0},K_{1},K_{2}\} , where H_{i}=,\,i\in\{0,1,...,p^{\alpha}-1\}, and K_{j}=,\,j\in\{0,1,2\},\,. So, the hyperedges of G are e_{1}=\{H_{0},H_{1},...,H_{p^{\alpha}-1},K_{0}\} , e_{2}=\{H_{0},H_{1},...,H_{p^{\alpha}-1},K_{1}\} and e_{3}=\{H_{0},H_{1},...,H_{p^{\alpha}-1},K_{2}\} . Note that each hyperedge has p^{\alpha}+1 vertices. Consider the corresponding incidence graph, \mathcal{I}(G) . In \mathcal{I}(G) , the number of vertices, n_{0}=(p^{\alpha}+3)+3=p^{\alpha}+6 , the number of edges, m=(p^{\alpha}+1)\cdot 3=3\cdot p^{\alpha}+3, and the girth, gr=4 . So, by Lemma 3.3 and as p^{\alpha}>9 , \displaystyle\dfrac{m\cdot(gr-2)}{2\cdot gr}-\dfrac{n_{0}}{2}+1 \displaystyle=\dfrac{(3\cdot p^{\alpha}+3)(4-2)}{2\cdot 4}-\dfrac{p^{\alpha}+6}{2}+1 \displaystyle=\dfrac{p^{\alpha}}{4}-1.25>1. Consequently, by Theorem 3.4 , g(\tilde{\Gamma}_{\mathcal{H}}(D_{n})) is at least 2. \underline{\textbf{Subcase 2.2}}: n has at least two distinct prime divisors. Let k be the largest integer such that k|=p_{1} , where p_{1} is the smallest prime divisor of n . Let G be the subhypergraph of \tilde{\Gamma}_{\mathcal{H}}(D_{n}) induced by the vertex set \Omega=\{H_{0},H_{1},...,H_{n-1},,,\} , where H_{i}=,\,i\in\{0,1,...,n-1\}. So, the hyperedges of the subhypergraph G induced by \Omega are e_{1}=\{H_{0},H_{1},...,H_{n-1},\} , e_{2}=\{H_{0},H_{1},...,H_{n-1},\} and e_{3}=\{H_{0},H_{1},...,H_{n-1},\} . In the incidence graph \mathcal{I}(G) of G , the number of vertices, n_{0}=n+6, the number of edges, m=3n+3-p_{1}, and the girth, gr=4 . Observe that, for all odd numbers that are not a power of prime, the difference between the number and its smallest prime divisor is strictly greater than 9. So, by Lemma 3.3 , \displaystyle g(G)\geq\dfrac{m\cdot(gr-2)}{2\cdot gr}-\dfrac{n_{0}}{2}+1 \displaystyle=\dfrac{(3n+3-p_{1})(4-2)}{2\cdot 4}-\dfrac{n+6}{2}+1 \displaystyle=\dfrac{n-p_{1}}{4}-\frac{5}{4} \displaystyle>\dfrac{9}{4}-1.25>1. Consequently, by Theorem 3.4 , g(\tilde{\Gamma}_{\mathcal{H}}(D_{n})) is at least 2. ∎ Corollary 3.6.1 . If \tilde{\Gamma}_{\mathcal{H}}(D_{n}) is non-planar, then it cannot be embedded on a torus. The following results play a key role in proving the non-orientable genus of \tilde{\Gamma}_{\mathcal{H}}(D_{n}) . Lemma 3.7 . [ 9 ] \tilde{g}(K_{m,n})=\left\lceil\dfrac{(m-2)(n-2)}{2}\right\rceil,\,m,n\geq 2 Lemma 3.8 . [ 9 ] Let G be a connected graph with n\geq 3 vertices and q edges. If G contains no cycle of length 3, then \tilde{g}(G)\geq\left\lceil\dfrac{q}{2}-n+2\right\rceil. Theorem 3.9 . [ 15 ] For any hypergraph \mathcal{H} , \tilde{g}(\mathcal{H})=\tilde{g}(\mathcal{I}(\mathcal{H})) . Theorem 3.10 . \tilde{\Gamma}_{\mathcal{H}}(D_{n}) is non-planar iff the non-orientable genus, \tilde{g}(\tilde{\Gamma}_{\mathcal{H}}(D_{n})) is at least 2. Proof. If the non-orientable genus, \tilde{g}(\tilde{\Gamma}_{\mathcal{H}}(D_{n})) is at least 2, then clearly \tilde{g}(\tilde{\Gamma}_{\mathcal{H}}(D_{n})) is non-planar. Conversely, suppose that \tilde{\Gamma}_{\mathcal{H}}(D_{n}) is non-planar. By Theorem 3.5 , \tilde{\Gamma}_{\mathcal{H}}(D_{n}) is non-planar iff neither n is a prime nor n=4 . To prove that the non-orientable genus, \tilde{g}(\tilde{\Gamma}_{\mathcal{H}}(D_{n})) is at least 2, consider the following cases: \underline{\textbf{Case 1.}} Suppose that n=6 . The incidence graph \mathcal{I}(\tilde{\Gamma}_{\mathcal{H}}(D_{6})) of \tilde{\Gamma}_{\mathcal{H}}(D_{6}) does not contain a cycle of length 3. In \mathcal{I}(\tilde{\Gamma}_{\mathcal{H}}(D_{6})) , the number of vertices, n_{0}=21 , and the number of edges, q=43 . Thus, by Lemma 3.8 , \tilde{g}(\mathcal{I}(\tilde{\Gamma}_{\mathcal{H}}(D_{6})))\geq\left\lceil\dfrac{43}{2}-21+2\right\rceil=3. Consequently, by Theorem 3.9 , \tilde{g}(\tilde{\Gamma}_{\mathcal{H}}(D_{6}))>2 . \underline{\textbf{Case 2.}} Suppose that n=8 . Consider K_{1}=,K_{2}=,K_{3}=,K_{4}= and K_{5}= . Observe that K_{i}\cap K_{j}\neq\{e\} for i,j\in\{1,2,3,4,5\} . Choose l_{1},l_{2},l_{3} from the set \{0,1,2,\cdots,n-1\} such that l_{i}\not\equiv 3(mod\,4) and l_{i}\not\equiv 1(mod\,2) for i\in\{1,2,3\} . Then, for H_{1}=,H_{2}= and H_{3}= , we have H_{i}\cap H_{j}=\{e\} for distinct i,j\in\{1,2,3\} . Also, H_{i}\cap K_{j}=\{e\} for i\in\{1,2,3\} and j\in\{1,2,3,4,5\} . Therefore, there exist five distinct hyperdges e_{1},e_{2},e_{3},e_{4},e_{5} such that e_{1} contains H_{1},H_{2},H_{3}\,\text{and}\,K_{1} , e_{2} contains H_{1},H_{2},H_{3}\,\text{and}\,K_{2} , e_{3} contains H_{1},H_{2},H_{3}\,\text{and}\,K_{3} , e_{4} contains H_{1},H_{2},H_{3}\,\text{and}\,K_{4} , and e_{5} contains H_{1},H_{2},H_{3}\,\text{and}\,K_{5} . Consider the subhypergraph G_{1} of \tilde{\Gamma}_{\mathcal{H}}(D_{8}) with \{e_{1},e_{2},e_{3},e_{4},e_{5}\} as the hyperedge set and the set of all vertices in e_{1},e_{2},e_{3},e_{4}\,\text{and}\,\,e_{5} as the vertex set of G_{1} . Thus, the incidence graph \mathcal{I}(G_{1}) of G_{1} contains K_{3,5} as a subgraph. By Lemma 3.7 , \tilde{g}(K_{3,5})=2 . Consequently, by Theorem 3.9 , \tilde{g}(\tilde{\Gamma}_{\mathcal{H}}(D_{8}))\geq 2. e_{1} e_{2} e_{3} e_{4} e_{5} {H_{1}} {H_{2}} {H_{3}} {K_{2}} {K_{1}} {K_{3}} {K_{4}} {K_{5}} (a) H_{1} H_{2} H_{3} e_{1} e_{2} e_{3} e_{4} e_{5} (b) \underline{\textbf{Case 3.}} Suppose that n\geq 9. e_{1} e_{2} e_{3} {H_{1}} {H_{2}} {H_{3}} {H_{4}} {H_{5}} {K_{2}} {K_{1}} {K_{3}} (a) H_{1} H_{2} H_{3} H_{4} H_{5} e_{1} e_{2} e_{3} (b) Consider K_{1}=,K_{2}= and K_{3}= , where p is a prime divisor of n . Observe that K_{i}\cap K_{j}\neq\{e\} for i,j\in\{1,2,3\} . Choose l_{1},l_{2},l_{3},l_{4} and l_{5} from the set \{0,1,2,\cdots,n-1\} such that l_{i}\not\equiv 0(mod\,p) for all i\in\{1,2,3,4,5\} . Then, for H_{1}=, H_{2}=, H_{3}=,H_{4}= and H_{5}= , we have H_{i}\cap H_{j}=\{e\} for distinct i,j\in\{1,2,3\} . Also, H_{i}\cap K_{j}=\{e\} for i\in\{1,2,3,4,5\} and j\in\{1,2,3\} . Therefore, there exist three distinct hyperedges e_{1},e_{2},e_{3} such that e_{1} contains H_{1},H_{2},H_{3},H_{4},H_{5}\,\text{and}\,K_{1} , e_{2} contains H_{1},H_{2},H_{3},H_{4},H_{5}\,\text{and}\,K_{2} , and e_{3} contains H_{1},H_{2},H_{3},H_{4},H_{5}\,\text{and}\,K_{3} . Consider the subhypergraph G_{2} of \tilde{\Gamma}_{\mathcal{H}}(D_{n}) with \{e_{1},e_{2},e_{3}\} as the hyperedge set and the set of all vertices in e_{1},e_{2}\,\text{and}\,\,e_{3} as the vertex set of G_{2} . Thus, the incidence graph \mathcal{I}(G_{2}) of G_{2} contains K_{3,5} as a subgraph. By Lemma 3.7 , \tilde{g}(K_{3,5})=2 . Consequently, by Theorem 3.9 , \tilde{g}(\tilde{\Gamma}_{\mathcal{H}}(D_{n}))\geq 2. ∎ Corollary 3.10.1 . If \tilde{\Gamma}_{\mathcal{H}}(D_{n}) is non-planar, then it cannot be embedded on a projective plane. Corollary 3.10.2 . \tilde{\Gamma}_{\mathcal{H}}(D_{n}) is either planar or has both orientable and non-orientable genus at least two.