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.