# Unimodality and Monotonic Portions of Certain Domination Polynomials

Amanda Burcroff  Department of Mathematical Sciences
Durham University
Durham, United Kingdom DH1 3LE<EMAIL_ADDRESS>or
<EMAIL_ADDRESS>and  Grace O’Brien  Department of Mathematics
University of Michigan
Ann Arbor, Michigan 48009<EMAIL_ADDRESS>
###### Abstract.

Given a simple graph $G$ on $n$ vertices, a subset of vertices $U\subseteq
V(G)$ is _dominating_ if every vertex of $V(G)$ is either in $U$ or adjacent
to a vertex of $U$. The _domination polynomial_ of $G$ is the generating
function whose coefficients are the number of dominating sets of a given size.
We show that the domination polynomial is unimodal, i.e., the coefficients are
non-decreasing and then non-increasing, for several well-known families of
graphs. In particular, we prove unimodality for spider graphs with at most
$400$ legs (of arbitrary length), lollipop graphs, arbitrary direct products
of complete graphs, and Cartesian products of two complete graphs. We show
that for every graph, a portion of the coefficients are non-increasing, where
the size of the portion depends on the upper domination number, and in certain
cases this is sufficient to prove unimodality. Furthermore, we study graphs
with $m$ _universal vertices_ , i.e., vertices adjacent to every other vertex,
and show that the last $(\frac{1}{2}-\frac{1}{2^{m+1}})n$ coefficients of
their domination polynomial are non-increasing.

##  1\. Introduction

Graph domination has become a mainstream branch of graph theory over the last
half century, but only in the past decade have researchers asked enumerative
questions about the number of dominating sets of a particular size in a fixed
graph. In this paper, we study these quantities on several families of graphs
and determine special properties of these counts as sequences, iterating over
the size of the dominating sets for a given graph.

Let $G=(V,E)$ be a simple graph on $n$ vertices. A set $U\subseteq V$ is
called _dominating_ if every vertex of $G$ is either in $U$ or adjacent to a
vertex of $U$. Let $d_{i}(G)$ denote the number of dominating sets of a graph
$G$ of a fixed size $i$. A significant portion of the study of domination in
graphs has focused on finding the minimum size of a dominating set in $G$, the
domination number, $\gamma(G)$. Note that the minimum $i$ such that
$d_{i}(G)>0$ is precisely $\gamma(G)$, so calculating these quantities
$d_{i}(G)$ encompasses the task of determining the domination number. It is
often convenient to look at these $d_{i}(G)$ in terms of generating functions;
the domination polynomial, $D(G,x)$, is given by

$D(G,x)=\sum_{i=1}^{n}d_{i}(G)x^{i}\,.$

Even without precisely calculating the quantities $d_{i}(G)$, one can
investigate properties of their distribution, such as their relative order.
Alikhani and Peng posed the following conjecture in 2014:

######  Conjecture 1.1 ([2]).

The domination polynomial of any graph is unimodal.

Note that, in general, the coefficients of the domination polynomial are not
log-concave (see an example of minimum size on $9$ vertices in [5]). This
implies that the domination polynomials are not real-rooted, and in fact it is
known that the roots are dense in the complex plane [8].

There has been an assortment of partial progress toward Conjecture 1.1 (see
[4] for a survey of recent results). In 2020, Beaton and Brown [5] show that
paths, cycles, and complete multipartite graphs all have unimodal domination
polynomials. Moreover, they prove that graphs with sufficiently large minimum
degree have unimodal domination polynomials (see Theorem 2.1), which they use
to show that almost all graphs have unimodal domination polynomials. In [1],
Alikhani and Jahari demonstrate unimodality of the domination polynomials for
several families of graphs, including every friendship graph as well as the
corona of any graph with $P_{3}$ or $K_{n}$.

In this paper, we identify other families of graphs with unimodal domination
polynomials and study the behavior of certain portions of the coefficients.
The families of graphs that we study generally have certain extremal degree
properties, i.e., have many vertices of low degrees, high degrees, or equal
degrees. We start with spider graphs, which are trees with only one vertex of
degree larger than $2$. We extend our methods used for spider graphs to handle
lollipop graphs, which consist of vertices of degree at most $2$ and all other
vertices of high degree. We then move on to two well-structured families of
regular graphs, namely the direct and Cartesian products of complete graphs.
We furthermore show that graphs with a very low upper domination number have
unimodal domination polynomials; such graphs generally have all vertices of
large degree. Lastly, we focus on graphs with one or more universal vertices,
which have the maximum possible degree. Loosely speaking, this paper is
structured so that the degree sequences of the graphs involved are
lexicographically increasing (though, of course, such an ordering depends on
the choice of several parameters).

More explicitly, the remainder of this paper is structured as follows. We
begin by providing the necessary background in Section 2. In Section 3, we
consider spider graphs having a bounded number of legs, each of arbitrary
length. In particular, we prove that all spider graphs with at most $400$ legs
have unimodal domination polynomials. We remark that the bound $400$ is
somewhat arbitrary; a portion of the proof relies on a number of computer
checks that could be carried out further, but in our case slowed down around
this threshold. Our work includes a generalization of the methods developed by
Beaton and Brown [5] for paths. We furthermore show that any lollipop graph,
i.e., a graph obtained by appending a path to a complete graph, has a unimodal
domination polynomial in Section 4.

Next, we investigate connected direct and Cartesian products of complete
graphs. The interplay between dominating sets and graph products has been the
subject of myriad studies, as surveyed in [12, Chapter 28] and [15]. In
general, it can be hard to estimate how the sequence $d_{i}(G)$ behaves under
graph products. One of the most famous open problems in graph domination is
Vizing’s conjecture that the domination number of a Cartesian product of
graphs is at least the product of their domination numbers [17]. In Sections
5.1 and 5.2, we prove the unimodality of the direct product of arbitrarily
many complete graphs and the Cartesian product of two complete graphs,
respectively. The former family includes the unitary Cayley graphs of
$\mathbb{Z}/q\mathbb{Z}$ for every squarefree integer $q$, which have received
recent attention for their extremal domination properties [9, 10, 11, 16].

In Section 6, we use a Hall-type argument to show that a portion of the
domination polynomial coefficients are non-increasing, where the size of this
portion depends on the upper domination number. The _upper domination number_
$\Gamma(G)$ of a graph $G$ is the maximum size of a minimal dominating set in
$G$. Our bound in particular implies that graphs of odd order with
$\Gamma(G)\leq 4$ and graphs of even order with $\Gamma(G)\leq 3$ have
unimodal domination polynomials.

In Section 7, we study graphs with $m$ universal vertices, as suggested in the
open problems section of [5]. A _universal vertex_ is a vertex that is
adjacent to every other vertex, i.e., has degree $n-1$. We show that the last
$\left(\frac{1}{2}-\frac{1}{2^{m+1}}\right)n$ coefficients of the domination
polynomial are non-increasing. As a direct corollary, any graph with at least
$\log_{2}(n)-1$ universal vertices has a unimodal domination polynomial. We
conclude with several directions for future research in Section 8.

##  2\. Preliminaries

Here we provide some basic definitions, an overview of the relevant families
of graphs and graph operations, as well as a collection of previous results.

A polynomial is called _unimodal_ if its coefficients are non-decreasing and
then non-increasing. We order the coefficients of a polynomial $f(x)$ of
degree $n$ by increasing order of the corresponding powers of $x$; thus when
we refer to the last $k$ coefficients, we mean the coefficients of
$x^{n-k+1}$, $x^{n-k+2}$, …, $x^{n}$. If $f(x)$ is unimodal, a coefficient of
$x^{k}$ is a _mode_ if it achieves the maximum value over all coefficients; in
this case, we say $f$ _has a mode at_ $k$. Note that a unimodal polynomial may
have multiple modes. Given two unimodal polynomials $f(x)$ and $g(x)$, we
refer to the _distance_ between modes appearing as the coefficients of
$x^{k_{f}}$ and $x^{k_{g}}$ in $f(x)$ and $g(x)$, respectively, as the
quantity $|k_{f}-k_{g}|$.

We begin by discussing the domination polynomials of spiders. The _spider
graph_ (or _spider_) $S(\lambda_{1},\ldots,\lambda_{t})$ is the graph formed
by taking $t$ paths, each on $\lambda_{i}$ vertices, and connecting one end of
each path to an additional central vertex. The induced path graph on a set of
vertices comprising one of the original paths is called a _leg of length
$\lambda_{i}$_.

Figure 1. The spider graph $S(1,2,2,3).$

In the study of spiders, we make use of the several common graph notions,
defined here. Let $G=(V,E)$ be a graph and $v$ be a vertex. The _open
neighborhood of $v$_, denoted by $N(v)$, is the set of all neighbors of $v$.
The closed neighborhood of $v$, denoted by $N[v]$, is the open neighborhood of
$v$ along with $v$ itself, i.e., $N[v]=\\{u\in V:\\{u,v\\}\in
E\\}\cup\\{v\\}$. We also look at subgraphs obtained by the deletion of one or
more vertices. For any $U\subseteq V$, the graph $G-U$ is the graph obtained
by removing all vertices in $U$ and any edges incident to a vertex in $U$.
When $U=\\{v\\}$ consists of a single vertex, we often write $G-v$ for
$G-\\{v\\}$. The subgraph $G/v$ obtained by _contracting_ the vertex $v$ has
vertex set $V\backslash\\{v\\}$, and its edge set consists of all edges in
$G-\\{v\\}$ plus all edges between two vertices in $N(v)$.

After our discussion of spiders, we move on to graph products. There are
multiple ways to define a product of graphs; we focus on two of the most
common, namely the direct and Cartesian products. Let $G=(V(G),E(G))$ and
$H=(V(H),E(H))$ be graphs. The direct product (or _tensor product_) of $G$ and
$H$ is the graph $G\times H$ on $V(G\times H)=V(G)\times V(H)$ where $(g,h)$
and $(g^{\prime},h^{\prime})$ are adjacent if $\\{g,g^{\prime}\\}\in E(G)$ and
$\\{h,h^{\prime}\\}\in E(H)$. The Cartesian product (or _box product_) is the
graph $G\operatorname{\square}H$ on the vertices of $V(G)\times V(H)$ where
$(g,h)$ and $(g^{\prime},h^{\prime})$ are adjacent if $g=g^{\prime}$ and
$\\{h,h^{\prime}\\}\in E(H)$, or $\\{g,g^{\prime}\\}\in E(G)$ and
$h=h^{\prime}$. When we take the product of multiple graphs simultaneously,
the definitions follow associatively from the definitions for the product of
two graphs.

Finally, we introduce two theorems, which we utilize several times throughout
this paper.

######  Theorem 2.1 ([5, Theorem 3.2]).

If $G$ is a graph on $n$ vertices with minimum degree
$\delta(G)\geq 2\log_{2}(n)$, then $D(G,x)$ is unimodal with a mode at
$\left\lceil{\frac{n}{2}}\right\rceil$.

######  Theorem 2.2 ([2, Theorem 5]).

Let $G$ be a graph on $n$ vertices. Then for every $0\leq i<\frac{n}{2}$, we
have $d_{i}(G)\leq d_{i+1}(G)$.

Theorem 2.1 is the foundation for Beaton and Brown’s proof that almost all
graphs (in the context of the Erdős-Rényi graph model) are unimodal ([5,
Theorem 3.3]). Their result allows us to simplify the consideration of many
families of graphs. The proof of Theorem 2.2 is a direct application of Hall’s
Theorem (see Theorem 6.1). In general, making statements about the first half
of the coefficients of a domination polynomial has been relatively
straightforward, while claims about the second half have proved more
difficult.

##  3\. Spiders With at Most $400$ Legs

Trees are a particularly elusive case of Conjecture 1.1 due to their low
minimum degree, as noted in [5]. As a first step towards understanding the
behavior of the domination polynomials for trees in general, we study spider
graphs, a family of trees. In this section, we show that all spider graphs
with at most $400$ legs have unimodal domination polynomials.

In order to establish unimodality for the domination polynomials of spiders,
we adapt methods developed by Beaton and Brown to show that $D(P_{n},x)$ is
unimodal for all $n$, where $P_{n}$ is the path on $n$ vertices. In
particular, we require the following theorem, which allows us to establish
unimodality for a sequence of polynomials.

######  Theorem 3.1.

_([5, Theorem 2.2])_ Suppose we have a sequence of polynomials $(f_{n})_{n\geq
1}$ with non-negative coefficients that satisfy
$f_{n}=x(f_{n-1}+f_{n-2}+f_{n-3})$ for $n\geq 4$. Let $\mathcal{P}_{n}$ denote
the following property: for all $i\in\\{1,\ldots,n\\}$, $f_{i}$ is unimodal
with a mode at $\mu_{i}$ and for $i\geq 2$, we additionally have
$0\leq\mu_{i}-\mu_{i-1}\leq 1$. Assume $\mathcal{P}_{4}$ holds. Then
$\mathcal{P}_{n}$ holds for all $n\geq 1$ (and so each $f_{n}$ is unimodal).

In order to apply Theorem 3.1 to spiders, we use the following recurrence due
to Kotek, Preen, Simon, Tittmann, and Trinks.

######  Proposition 3.2.

_([14, Proposition 3.1])_ Let $G$ be a graph. If there exist $u,v\in V(G)$
such that $N[u]\subseteq N[v]$, then

$D(G,x)=xD(G/v)+D(G-v)+xD(G-N[v])\,.$

We show that if $G$ can be formed by appending a path on $3$ vertices to a
graph, then we can confirm the unimodality of $D(G,x)$ by checking certain
unimodality and mode conditions on subgraphs of $G$. We now proceed to
characterize which subgraphs must be considered.

Fix a graph $H$ on $n$ vertices and a vertex $v\in V(H)$. Let $H_{v}^{(\ell)}$
denote the graph obtained by appending a path on $\ell$ vertices by adding an
edge between $v$ and a leaf, i.e., a vertex of degree $1$, of the path. We set
$H_{v}^{(0)}:=H$. Thus, $H_{v}^{(\ell)}$ has $n+\ell$ vertices for all
$\ell\geq 0$.

######  Lemma 3.3.

Let $G=(V,E)$ be a graph, and fix $v\in V(G)$. Suppose we have that

  1. (i)

$D(G,x)$, $D(G_{v}^{(1)},x)$, $D(G_{v}^{(2)},x)$, and $D(G_{v}^{(3)},x)$ are
unimodal with modes at $\mu_{0}$, $\mu_{1}$, $\mu_{2}$, and $\mu_{3}$,
respectively, and

  2. (ii)

$0\leq\mu_{i}-\mu_{i-1}\leq 1$ for $i\in\\{1,2,3\\}$.

Then $D(G_{v}^{(\ell)},x)$ is unimodal for all $\ell\in\mathbb{N}$.

###### Proof.

Let $u_{i}$ be the unique vertex in $V\left(G_{v}^{(i)}\right)\backslash
V\left(G_{v}^{(i-1)}\right)$ for $i\in\\{1,2,3\\}$, as illustrated in Figure
2. Observe that $G_{v}^{(3)}/u_{2}\cong G_{v}^{(2)}$ and
$G_{v}^{(3)}-N[u_{2}]=G_{v}^{(3)}-\\{u_{1},u_{2},u_{3}\\}=G$.

Since $N[u_{3}]\subseteq N[u_{2}]$ in $G_{v}^{(3)}$, by Proposition 3.2 we
have

$D\left(G_{v}^{(3)},x\right)=xD\left(G_{v}^{(2)},x\right)+D\left(G_{v}^{(3)}-\\{u_{2}\\},x\right)+xD\left(G,x\right).$

Moreover, note that $G_{v}^{(3)}-\\{u_{2}\\}=G_{v}^{(1)}\cup\\{u_{3}\\}$.
Since $u_{3}$ must be included in every dominating set of
$G_{v}^{(1)}\cup\\{u_{3}\\}$, we have
$D\left(G_{v}^{(3)}-\\{u_{2}\\},x\right)=xD\left(G_{v}^{(1)},x\right)$. Thus,
Theorem 3.1 applies with $f_{n}=D\left(G_{v}^{(3)},x\right)$,
$f_{n-1}=D\left(G_{v}^{(2)},x\right)$, $f_{n-2}=D\left(G_{v}^{(1)},x\right)$,
and $f_{n-3}=D\left(G,x\right)$. ∎

Figure 2. Illustrations of the graphs constructed in Lemma 3.3, where
$G=S(1,2,2,3)$ and $v$ chosen to be the unique vertex of degree at least $3$.

While we use Lemma 3.3 to show that spiders with a bounded number of legs have
unimodal domination polynomials, similar techniques could be applied to other
families of graphs satisfying similar hypotheses. We need only check that
these conditions hold when attaching paths on at most $3$ vertices to
establish unimodality after attaching paths of arbitrary lengths. Once such
family where similar methods can be used is the set of lollipop graphs, which
we investigate in Section 4.

We now establish the precise domination polynomial of a spider graph with legs
of length at most $3$. This classification is then used to complete the finite
number of checks needed to ensure the conditions of Lemma 3.3 hold for spiders
with a bounded number of legs, each with length at most $3$.

######  Lemma 3.4.

Let $S$ be a spider comprised of $\ell_{1}$ legs of length $1$, $\ell_{2}$
legs of length $2$, and $\ell_{3}$ legs of length $3$. If $\ell_{1}>0$, we
have

$D(S,x)=x(1+x)^{\ell_{1}}(2x+x^{2})^{\ell_{2}}(2x+3x^{2}+x^{3})^{\ell_{3}}+x^{\ell_{1}}(2x+x^{2})^{\ell_{2}}(x+3x^{2}+x^{3})^{\ell_{3}}\,.$

If $\ell_{1}=0$, we have

$D(S,x)=x(2x+x^{2})^{\ell_{2}}(2x+3x^{2}+x^{3})^{\ell_{3}}+(2x+x^{2})^{\ell_{2}}(x+3x^{2}+x^{3})^{\ell_{3}}-x^{\ell_{2}}(x+x^{2})^{\ell_{3}}\,.$

###### Proof.

Let $z$ denote the center vertex of the spider. We claim that

$A(x):=x(1+x)^{\ell_{1}}(2x+x^{2})^{\ell_{2}}(2x+3x^{2}+x^{3})^{\ell_{3}}$

is the generating function whose coefficients count the number of dominating
sets of $S$ that include $z$. Observe that $2x+3x^{2}+x^{3}$ (resp.
$2x+x^{2}$, $1+x$) counts the number of sets of a path of length $3$ (resp.
$2$, $1$) whose closed neighborhood includes all vertices except possibly one
endpoint of the path. The dominating sets of $S$ are formed by taking such a
subset of vertices in each of the $\ell_{i}$ paths of length $i$, and then
attaching the (possibly uncovered) endpoint of each path to $z$ via an edge.

We now proceed to count the number of dominating sets of $S$ that do not
contain $z$. Observe that $x+3x^{2}+x^{3}$ (resp. $2x+x^{2}$, $x$) counts the
number of dominating sets of a path of length $3$ (resp. $2$, $1$). Suppose
that we choose a subset of vertices $W\subset V(S)$ formed by taking such a
subset of vertices in the $\ell_{i}$ paths of length $i$, and then attaching
an endpoint of each path to $z$ via an edge. Note that there are
$x^{\ell_{1}}(2x+x^{2})^{\ell_{2}}(x+3x^{2}+x^{3})^{\ell_{3}}$ such sets. Our
construction of $W$ guarantees that $W$ dominates all vertices of $S$ except
for possibly $z$; we now consider two cases regarding when $z$ is dominated.

  1. (i)

If $\ell_{1}>0$, then one of the legs of length $1$ in $S$ must have its leaf
included in $W$. Thus, $W$ dominates $z$. So, by the above, $W$ is a
dominating set of $S$.

  2. (ii)

If $\ell_{1}=0$, then $W$ is non-dominating precisely when all the endpoints
of the paths that are attached to $z$ are not included in $W$. Such sets are
counted by $x^{\ell_{2}}(x+x^{2})^{\ell_{3}}$.

We can therefore see that the number of dominating sets of $S$ not containing
$z$ is given by the coefficients of

$B(x):=\begin{cases}x^{\ell_{1}}(2x+x^{2})^{\ell_{2}}(x+3x^{2}+x^{3})^{\ell_{3}}&\text{
if }\ell_{1}>0\,,\\\
(2x+x^{2})^{\ell_{2}}(x+3x^{2}+x^{3})^{\ell_{3}}-x^{\ell_{2}}(x+x^{2})^{\ell_{3}}&\text{
if }\ell_{1}=0\,.\end{cases}$

Setting $D(S,x)=A(x)+B(x)$ yields the desired equalities. ∎

######  Lemma 3.5.

Let $S=S(\lambda_{1},\ldots,\lambda_{t})$ be a spider with $t\leq 400$, and
fix $i$ such that $\lambda_{i}>3$. Let
$S^{\prime}=S(\lambda_{1},\ldots,\lambda_{i-1},\lambda_{i}+1,\lambda_{i+1},\ldots,\lambda_{t})$.
If $D(S,x)$ is unimodal with a mode at $\mu$, then $D(S^{\prime},x)$ is
unimodal with a mode either at $\mu$ or $\mu+1$.

###### Proof.

Apply Lemma 3.3 to the vertices at the end of the leg of length $\lambda_{i}$;
in particular, set $u_{3}$ to be the leaf of this leg, $u_{2}$ the unique
neighbor of $u_{3}$, $u_{1}$ the other neighbor of $u_{2}$, and $v$ the other
neighbor of $u_{1}$. ∎

######  Theorem 3.6.

All spider graphs with at most $400$ legs (each of arbitrary length) have
unimodal domination polynomials.

###### Proof.

We first note that for $t\leq 400$, one can check via computer (as we have
successfully done) that a spider $S$ with $t$ legs, each of length at most
$3$, satisfies the hypotheses of Lemma 3.3. The domination polynomials for
these spiders are given explicitly by Lemma 3.4, so the computer check is
straightforward. It then follows immediately from Lemma 3.5 that every spider
with at most $400$ legs has a unimodal domination polynomial. ∎

The natural next step is to determine if $D(S,x)$ is unimodal for any spider
$S$. Note that the unimodality of these polynomials is implied by Alikhani and
Peng’s conjecture (1.1). However, proving the following conjecture on spiders
with legs of length at most $3$ would also be sufficient to prove unimodality
for all spiders by applying Lemma 3.3.

######  Conjecture 3.7.

Let $S$ be a spider with legs of length at most $3$, and $S^{\prime}$ be a
spider obtained by deleting a leaf from $S$. Then $D(S,x)$ and
$D(S^{\prime},x)$ are unimodal with at least one pair of modes at $\mu_{S}$
and $\mu_{S^{\prime}}$, respectively, such that
$|\mu_{S}-\mu_{S^{\prime}}|\leq 1$.

##  4\. Lollipop Graphs

Furthering our study of graphs with low minimum degree, we show that all
lollipop graphs have unimodal domination polynomials. We use recursive methods
with respect to appending paths, similar to those used for spider graphs in
the previous section.

######  Definition 4.1.

The _$(m,n)$ -lollipop graph_ $L_{m,n}$ is the graph on $m+n$ vertices
consisting of a complete graph on $m$ vertices and a path graph on $n$
vertices, connected at a leaf of the path via an edge.

######  Lemma 4.2.

For $1\leq n\leq 3$ and $m\geq 3$, we have that $D(L_{m,n},x)$ is unimodal
with a mode at $\mu$, where

$\mu=\begin{cases}\left\lfloor\frac{m}{2}\right\rfloor+1&\text{ if }n=1\,,\\\
\left\lceil\frac{m}{2}\right\rceil+1&\text{ if }n=2\,,\\\
\left\lfloor\frac{m}{2}\right\rfloor+2&\text{ if }n=3\,.\\\ \end{cases}$

###### Proof.

We break into cases depending on the value of $n$. Beaton and Brown [5]
completed the case $m=3$ in the remark after their Corollary 2.3, so we can
take $m\geq 4$. Thus, $m+n\geq 7$, so in particular, we know by Theorem 2.2
that the first $4$ coefficients are non-decreasing.

Case $n=1$: Note that a set of at least $2$ vertices in $L_{m,1}$ is non-
dominating if and only if it does not contain the leaf or the leaf’s unique
neighbor, i.e., the set is contained in the remaining $m-1$ vertices. Hence,
for $i\geq 2$ we have

$d_{i}(L_{m,1})={m+1\choose i}-{m-1\choose i}={m\choose i-1}+{m-1\choose
i-1}\,.$

The first summand ${m\choose i-1}$ has modes at
$\left\lceil\frac{m}{2}\right\rceil+1$ and
$\left\lfloor\frac{m}{2}\right\rfloor+1$, while the second summand
${m-1\choose i-1}$ has modes at $\left\lceil\frac{m-1}{2}\right\rceil+1$ and
$\left\lfloor\frac{m-1}{2}\right\rfloor+1$. In particular, both sequences have
a mode at
$\left\lfloor\frac{m}{2}\right\rfloor+1=\left\lceil\frac{m-1}{2}\right\rceil+1$.
Hence, $D(L_{m,1},x)$ is unimodal with a mode at the desired position.

Case $n=2$: A set of at least $3$ vertices in $L_{m,2}$ is dominating if and
only if it nontrivially intersects the closed neighborhood of the unique leaf.
Thus, for $i\geq 3$ we have

$d_{i}(L_{m,2})={m+2\choose i}-{m\choose i}={m+1\choose i-1}+{m+1\choose
i}-{m\choose i}={m+1\choose i-1}+{m\choose i-1}\,.$

Similar to our analysis in Case 1, though with the indexing for $m$ shifted by
one, we can see that $D(L_{m,2},x)$ is unimodal with a mode at
$\left\lfloor\frac{m+1}{2}\right\rfloor+1=\left\lceil\frac{m}{2}\right\rceil+1$.

Figure 3. The lollipop $L_{5,3}$ with designated vertices $u$ and $v$.

Case $n=3$: Let $u$ denote the unique leaf of $L_{m,3}$, and let $v$ be the
unique vertex of distance $2$ from $u$ (see Figure 3). A set of at least $4$
vertices is dominating if and only if it dominates both $u$ and $v$. This is
because the unique neighbor of $u$ is dominated provided that $u$ is
dominated, and moreover, by the pigeonhole principle at least one vertex of
$K_{m}$ is included in the set hence all vertices of $K_{m}$ are dominated.
There are ${m+1\choose i}$ sets of size $i$ that do not dominate $u$,
${m\choose i}$ sets of size $i$ that do not dominate $v$, and ${m-1\choose i}$
sets of size $i$ that dominate neither $u$ nor $v$. Hence, we have

$\displaystyle d_{i}(L_{m,3})$ $\displaystyle={m+3\choose i}-{m+1\choose
i}-{m\choose i}+{m-1\choose i}$ $\displaystyle={m+2\choose i-1}+{m+2\choose
i}-{m+1\choose i}-{m-1\choose i-1}$ $\displaystyle={m+2\choose i-1}+{m\choose
i-2}+{m\choose i-1}-{m-1\choose i-1}$ $\displaystyle={m+2\choose
i-1}+{m\choose i-2}+{m-1\choose i-2}\,.$

Similar to the previous two cases, we have that ${m\choose i-2}+{m-1\choose
i-2}$ is unimodal with a mode at $\left\lfloor\frac{m}{2}\right\rfloor+2$.
Moreover, ${m+2\choose i-1}$ has a mode at
$\left\lfloor\frac{m+2}{2}\right\rfloor+1=\left\lfloor\frac{m}{2}\right\rfloor+2$.
Hence, $D(L_{m,3},x)$ is as desired. ∎

######  Theorem 4.3.

All lollipop graphs have unimodal domination polynomials.

###### Proof.

This follows directly from Lemma 3.3 and Lemma 4.2. ∎

##  5\. Products of Complete Graphs

While the minimum size of a dominating set in a product of graphs has been
studied for decades [12, 15, 17], there has been little work toward
understanding the dominating sets of larger sizes in a graph product. In
general, this relationship can be rather complex, so we focus on a family of
graphs that has been shown to have interesting domination properties in other
contexts: direct and Cartesian products of complete graphs. The direct product
of complete graphs has been shown to have extremal properties in the
domination chain [9, 11, 16], while the Cartesian products of two complete
graphs were used by the first author to demonstrate the tightness of Brešar,
Klavžar, and Rall’s inequality $\Gamma(G\times H)\geq\Gamma(G)\Gamma(H)$,
which holds for any graphs $G$ and $H$ [10, 7].

###  5.1. Direct Products of Complete Graphs

In this section, we investigate the domination polynomials of the connected
direct product of complete graphs. We first prove unimodality for certain
regular graphs in Lemma 5.1, including graphs of the form $K_{2}\times K_{n}$.
Then, we consider the product of an arbitrary number of complete graphs.

######  Lemma 5.1.

Let $G$ be an $m$-regular graph on $2n$ vertices for some $3\leq n-1\leq
m<2n$. Then, $D(G,x)$ is unimodal with a mode at $n$.

###### Proof.

Let $G=(V,E)$ be a graph as described. First, we notice that by Theorem 2.2,
we have $d_{1}(G)\leq d_{2}(G)\leq\cdots\leq d_{n-1}(G)\leq d_{n}(G)$. By the
degree condition, each vertex $v$ has a closed neighborhood of size at least
$n$. Every set of vertices that does not dominate $v$ must be a subset of
$V(G)\backslash N[v]$, which has size $2n-|N[v]|\leq n$. Iterating over the
vertices, we see that there are at most $2n$ non-dominating sets of size $n$,
and furthermore every set of size at least $n+1$ is dominating. Thus,
${2n\choose n}-2n\leq d_{n}(G)\leq{2n\choose n}$, and $d_{n+r}(G)={2n\choose
n+r}$ for $1\leq r\leq n$. In particular, we clearly have $d_{n+1}(G)\geq
d_{n+2}(G)\geq\cdots\geq d_{2n}(G)$. For $n\geq 4$, it is straightforward to
check that

${2n\choose n}-2n\geq{2n\choose n+1}\,.$

Since $d_{n-1}(G)\leq{2n\choose n-1}={2n\choose n+1}=d_{n+1}(G)\leq d_{n}(G)$,
we can conclude that $D(G,x)$ is unimodal with a mode at $n$. ∎

######  Remark 5.2.

Lemma 5.1 can also be proven using the minimum degree argument from Theorem
2.1 and a finite number of exceptional cases. However, the exceptional cases
would include checking the domination polynomials of all $(n-1)$-regular
graphs on $2n$ vertices for $n\leq 9$, which appears computationally
challenging.

We can now focus on connected direct products of at least three complete
graphs. Note that a direct product of complete graphs is connected if and only
if each complete graph has order at least $2$ and at most one of the complete
graphs has order exactly $2$. We begin by proving a technical lemma, which we
will use later to show that all but finitely many direct products of complete
graphs satisfy the hypotheses of Theorem 2.1.

######  Lemma 5.3.

Suppose we have positive integers $2\leq n_{1}\leq n_{2}\leq\cdots\leq n_{t}$
with $n_{2}\geq 3$; and additionally if $t=2$, then $n_{1}\geq 3$. If there
exist positive integers $\ell_{i}\leq n_{i}$ for $1\leq i\leq t$ such that

$(\ell_{1}-1)(\ell_{2}-1)\cdots(\ell_{t}-1)\geq
2\log_{2}(\ell_{1}\ell_{2}\cdots\ell_{t})\,,$

then

$(n_{1}-1)(n_{2}-1)\cdots(n_{t}-1)\geq 2\log_{2}(n_{1}n_{2}\cdots n_{t})\,.$

###### Proof.

By induction, we can assume that $n_{i}=\ell_{i}+1$ for exactly one choice of
$i$, and $n_{j}=\ell_{j}$ for all $j\neq i$. Note that we must have $n_{i}\geq
3$, and
$\prod_{j\in\\{1,\ldots,t\\}\backslash\\{i\\}}(n_{j}-1)=\prod_{j\in\\{1,\ldots,t\\}\backslash\\{i\\}}(\ell_{j}-1)\geq
2$ by our hypotheses on $n_{1},\ldots,n_{t}$. Thus, we have

$\displaystyle\prod_{k=1}^{t}(n_{k}-1)-2\log_{2}\left(\prod_{k=1}^{t}n_{k}\right)$
$\displaystyle=\left(\frac{n_{i}-1}{\ell_{i}-1}\right)\prod_{k=1}^{t}(\ell_{k}-1)-\left(2\log_{2}\left(\prod_{k=1}^{t}\ell_{k}\right)+2\log_{2}\left(\frac{n_{i}}{\ell_{i}}\right)\right)$
$\displaystyle=\left(\frac{1}{\ell_{i}}+1\right)\prod_{k=1}^{t}(\ell_{k}-1)-2\log_{2}\left(\prod_{k=1}^{t}\ell_{k}\right)-2\log_{2}\left(\frac{\ell_{i}+1}{\ell_{i}}\right)$
$\displaystyle\geq\prod_{j\in\\{1,\ldots,t\\}\backslash\\{i\\}}(\ell_{j}-1)-2\log_{2}\left(\frac{\ell_{i}+1}{\ell_{i}}\right)$
$\displaystyle\geq 2-\log_{2}\left(\frac{\ell_{i}+1}{\ell_{i}}\right)$
$\displaystyle>0\,.$

Observe that the last inequality follows since
$\frac{\ell_{i}+1}{\ell_{i}}<2$, hence
$\log_{2}\left(\frac{\ell_{i}+1}{\ell_{i}}\right)<1$. ∎

######  Proposition 5.4.

Suppose we have positive integers $2\leq n_{1}\leq n_{2}\leq\cdots\leq n_{t}$
with $n_{2}\geq 3$ and $t\geq 2$; and additionally if $t=2$, then $n_{1}\geq
3$. Then

$(n_{1}-1)(n_{2}-1)\cdots(n_{t}-1)\geq 2\log_{2}(n_{1}n_{2}\cdots n_{t})$

unless $t=2$ with

$(n_{1},n_{2})\in\\{(3,3),(3,4)\\}\,,$

or $t=3$ with

$(n_{1},n_{2},n_{3})\in\\{(2,3,3),(2,3,4),(2,3,5),(2,3,6),(2,4,4),(3,3,3)\\}\,,$

or $t=4$ with

$(n_{1},n_{2},n_{3},n_{4})\in\\{(2,3,3,3),(2,3,3,4)\\}\,.$

###### Proof.

This follows Lemma 5.3 and basic case checking. ∎

Note that the inequalities appearing in Lemma 5.3 and Proposition 5.4 is
precisely the minimum degree condition of Theorem 2.1. We now combine these
results to obtain the main theorem of this section.

######  Theorem 5.5.

The domination polynomials of all connected direct products of complete graphs
are unimodal.

###### Proof.

Lemma 5.1 implies that all graphs of the form $K_{2}\times K_{n}$ have
unimodal domination polynomials. Combining Proposition 5.4 and Theorem 2.1, we
find that the domination polynomials of all connected direct products of
complete graphs are unimodal except possibly the ten exceptional cases listed
in Proposition 5.4. It is straightforward to compute the domination
polynomials in these ten remaining cases and see that the polynomials are
indeed unimodal. ∎

###  5.2. Cartesian Products of Complete Graphs

Motivated by our progress in understanding the direct product of complete
graphs, we consider the domination polynomials of Cartesian products of
complete graphs. We briefly show that unimodality holds for the Cartesian
product of two complete graphs (known as a rook graph), followed by a
discussion of why higher order products are more difficult to handle than in
the direct product case.

######  Theorem 5.6.

$D(K_{m}\operatorname{\square}K_{n},x)$ is unimodal for all
$m,n\in\mathbb{N}$.

###### Proof.

Without loss of generality we can assume $m\leq n$, since
$K_{m}\operatorname{\square}K_{n}\cong K_{n}\operatorname{\square}K_{m}$. When
$m=1$, $D(K_{m}\operatorname{\square}K_{n},x)$ is unimodal as its coefficients
are merely the binomial coefficients. When $m=2$, we notice that
$K_{2}\operatorname{\square}K_{n}$ is an $n$-regular graph on $2n$ vertices.
Therefore, by Lemma 5.1, $D(K_{2}\operatorname{\square}K_{n},x)$ is unimodal.
For $m\geq 3$, we can divide the set of remaining products of two complete
graphs into three cases:

  1. (1)

$m=3$

  2. (2)

$4\leq m\leq n\leq 7$

  3. (3)

$m\geq 4,n\geq 8$.

Let us consider $m=3$. We see for $n\geq 9$,
$D(K_{m}\operatorname{\square}K_{n},x)$ is unimodal by Theorem 2.1. The cases
for $n\leq 8$ can be checked explicitly. Similarly, the ten cases for $4\leq
m\leq n\leq 7$ can be checked explicitly. We see
$D(K_{6}\operatorname{\square}K_{7},x)$ and
$D(K_{7}\operatorname{\square}K_{7},x)$ are unimodal by Theorem 2.1. The
remaining eight cases can be verified by computer.

Therefore, it only remains to show that
$D(K_{m}\operatorname{\square}K_{n},x)$ is unimodal for $m\geq 4,n\geq 8$.
Recall Theorem 2.1 proves that if $\delta_{G}\geq 2\log_{2}(|V|)$, then
$D(G,x)$ is unimodal. So, we see for $m\geq 4$, $n\geq 8$, the minimum degree
is given by

$\delta_{K_{m}\operatorname{\square}K_{n}}=(m-1)+(n-1)\geq
2\log_{2}(m)+n-2\geq 2\log_{2}(m)+2\log_{2}(n)=2\log_{2}(mn)\,.$

∎

We now discuss why higher order products are more infeasible than in the
direct product case. For a bounded number of complete graphs included in the
Cartesian product, there is a finite and increasing number of cases that do
not satisfy the hypotheses of Theorem 2.1. Thus, while one could iterate this
procedure for Cartesian products of three or more complete graphs, the number
of exceptional cases, i.e., those graphs not covered by Theorem 2.1, quickly
becomes computationally challenging to handle. Already for a Cartesian product
of three complete graphs, there are $72$ exceptional cases, and $221$ for a
product of four complete graphs. Contrast this to the direct product case,
where the minimum degree is $(n_{1}-1)(n_{2}-1)\cdots(n_{t}-1)$, which in
general is much larger than the minimum degree
$(n_{1}-1)+(n_{2}-1)+\cdots+(n_{t}-1)$ in the Cartesian setting. As we saw in
Proposition 5.4, the hypotheses of Theorem 2.1 were satisfied for all
connected direct products of five or more complete graphs.

One particular special case that may be interesting to investigate is the
domination polynomial of the hypercube graph, defined recursively by
$Q_{n}:=K_{2}\operatorname{\square}Q_{n-1}$ with $Q_{1}:=K_{2}$. The problem
of determining the domination number of $Q_{n}$ is a fundamental problem in
coding theory and is only known in special cases, namely for $n\leq 9$ and
$n=2^{k}-1$ or $2^{k}$, see [13, 3]. Thus, precisely determining the
domination polynomials of hypercubes is very difficult, but it may still be
possible to further understand the behavior of their coefficients.

##  6\. Unimodality and Upper Domination

In this section, we use a Hall-type argument to show that for sufficiently
large $i$, depending on the upper domination number, the coefficients
$d_{i}(G)$ are non-increasing.

A subset $M\subseteq E(G)$ is a _matching_ if no two edges in $M$ share a
vertex. A matching $M$ _saturates_ a set of vertices $U\subseteq V(G)$ if
every vertex of $U$ is incident to an edge in $M$. We make use of Hall’s
classic theorem on saturated matchings in bipartite graphs.

######  Theorem 6.1 (Hall’s Theorem, see, e.g., [6, Theorem 5.2]).

Let $G$ be a bipartite graph with bipartition $(X,Y)$. Then $G$ contains a
matching that saturates every vertex in $X$ if and only if, for all
$U\subseteq X$, we have $|N(U)|\geq|U|$.

Similar to the construction used by Alikhani and Peng to prove Theorem 2.2, we
define a bipartite graph with vertices labeled by dominating sets of $G$. This
construction admits a saturated matching provided the dominating sets are
sufficiently large, with the lower bound depending on the upper domination
number. Recall that the upper domination number $\Gamma(G)$ of a graph $G$ is
the maximum size of a minimal dominating set.

######  Theorem 6.2.

Let $G$ be a graph on $n$ vertices. If $i\geq\frac{n+\Gamma(G)-1}{2}$, then
$d_{i}(G)\geq d_{i+1}(G)$.

###### Proof.

Let $A$ be a set of vertices labeled by the dominating sets of size $i+1$ in
$G$, and let $B$ be a set of vertices labeled by the dominating sets of size
$i$. We construct a bipartite graph on $A\cup B$ by connecting two vertices if
the corresponding dominating set of size $i$ is contained in the corresponding
dominating set of size $i+1$. Note that every vertex of $B$ has degree $n-i$.
Moreover, since a dominating set of size $i$ in $G$ contains a minimal
dominating set of size at most $\Gamma(G)$, each vertex in $A$ has degree at
least $i+1-\Gamma(G)$.

We want to show that $A$ admits a saturated perfect matching into $B$. By
Theorem 6.1, it is sufficient to show that $|N(T)|\geq|T|$ for every
$T\subseteq A$. Suppose that there exists $U\subseteq A$ such that
$|N(U)|<|U|$. Since each vertex of $U$ has degree at least $i+1-\Gamma(G)$,
there must exist a vertex of $N(U)$ with degree greater than $i+1-\Gamma(G)$
in the induced subgraph on $U\cup N[U]$. That is, we must have
$i+1-\Gamma(G)<n-i$. By our choice of $i$, we reach a contradiction. Thus, $A$
admits a saturated perfect matching, so $|A|\leq|B|$, i.e., $d_{i+1}(G)\leq
d_{i}(G)$. ∎

In particular, we obtain the following corollary.

######  Corollary 6.3.

Let $G$ be a graph on $n$ vertices. If $n$ is odd and $\Gamma(G)\leq 4$, or if
$n$ is even and $\Gamma(G)\leq 3$, then $D(G,x)$ is unimodal with a mode at
$\left\lceil{\frac{n}{2}}\right\rceil$ or
$\left\lceil{\frac{n}{2}}\right\rceil+1$.

###### Proof.

Suppose first that $n$ is odd. From Theorem 2.2, we have that

$d_{1}(G)\leq d_{2}(G)\leq\cdots\leq d_{\frac{n+1}{2}}(G)\,.$

By Theorem 6.2, we furthermore have

$d_{\frac{n+3}{2}}(G)\geq d_{\frac{n+5}{2}}(G)\geq\cdots\geq d_{n}(G)\,.$

Thus, regardless of the relation between $d_{\frac{n+1}{2}}(G)$ and
$d_{\frac{n+3}{2}}(G)$, the resulting sequence is unimodal. The argument for
$n$ even is analogous, but instead the only relation we cannot determine is
between $d_{\frac{n}{2}}(G)$ and $d_{\frac{n+2}{2}}(G)$. ∎

######  Remark 6.4.

Note that we could use Corollary 6.3 to show that the lollipop graphs
$L_{m,n}$ have unimodal domination polynomials for $n\leq 3$. However, we need
to know additional information about the location of modes of these graphs in
order to induct on $n$ with Theorem 3.1, hence we handled this case more
explicitly in Section 4.

##  7\. Graphs with Universal Vertices

In this section, we investigate properties of the domination polynomial of a
graph with many universal vertices. Let $G$ be a graph on $n$ vertices. A
_universal vertex_ is a vertex whose closed neighborhood is the entire graph,
i.e., a vertex of degree $n-1$. Since any set of vertices containing a
universal vertex is necessarily dominating, we can place lower bounds on the
coefficients $d_{i}(G)$ in terms of the number of universal vertices. This
allows us to prove unimodality for graphs with sufficiently many universal
vertices, in particular when the number of universal vertices is at least
$\log_{2}(n)-1$.

We use the following result of Beaton and Brown to show that the coefficients
of the domination polynomial for a graph with one or more universal vertices
are non-increasing past a certain threshold. For a graph on $n$ vertices, let
$r_{k}(G)$ be the proportion of subsets of $V(G)$ of size $k$ that are
dominating. That is, $r_{k}(G)=\frac{d_{k}(G)}{{n\choose k}}.$

######  Lemma 7.1.

_([5, Lemma 3.1])_ Let $G$ be a graph on $n$ vertices, and $k\geq\frac{n}{2}$.
If $r_{k}(G)\geq\frac{n-k}{k+1}$ then $d_{i+1}(G)\leq d_{i}(G)$ for all $i\geq
k$. In particular, if $k=\left\lceil\frac{n}{2}\right\rceil$ then $D(G,x)$ is
unimodal with a mode at $\left\lceil\frac{n}{2}\right\rceil$.

######  Theorem 7.2.

Let $G$ be a graph on $n$ vertices, $m$ of which are universal. Let $w_{m}$ be
the smallest positive real root of $f_{m}(x)=x^{m+1}-x^{m}-2x+1$. Then
$d_{i}(G)\geq d_{i+1}(G)$ for all $i\geq(1-w_{m})n$.

###### Proof.

Suppose that we have $d_{i+1}(G)>d_{i}(G)$ for some $i\geq\frac{n}{2}$, and we
wish to show that $i<(1-w_{m})n$. Since any non-dominating set of size $i$
must not contain any of the $m$ universal vertices, we have

$d_{i}(G)\geq{n\choose i}-{n-m\choose i}\,.$

By Lemma 7.1, we must have

$\frac{d_{i}(G)}{{n\choose i}}<\frac{n-i}{i+1}\,.$

Combining the above two inequalities yields

${n\choose i}-{n-m\choose i}\leq d_{i}(G)\leq\frac{n-i}{i+1}{n\choose i}\,.$

We can then divide both sides by ${n\choose i}$ and rearrange to obtain

$\frac{n-i}{i+1}+\prod_{j=0}^{m-1}\frac{n-i-j}{n-j}>1\,.$

Since $\frac{n-i-j}{n-j}<\frac{n-i}{n}$ for any $j>0$, we furthermore have

$\frac{n-i}{i}+\left(\frac{n-i}{n}\right)^{m}\geq\frac{n-i}{i+1}+\left(\frac{n-i}{n}\right)^{m}>1\,.$

Setting $i=(1-\kappa)n$, we see that this condition is equivalent to

$\frac{\kappa n}{(1-\kappa)n}+\left(\frac{\kappa
n}{n}\right)^{m}-1=\frac{\kappa}{1-\kappa}+\kappa^{m}-1>0\,.$

Multiplying by $\kappa-1$ (which is necessarily negative) yields

$\kappa^{m+1}-\kappa^{m}-2\kappa+1<0.$

Since $f(0)>0$ and $f(\kappa)<0,$ by the above inequality, we must have that
$\kappa>w_{m}$. Hence, we can conclude $i=(1-\kappa)n<(1-w_{m})n$, as desired.
∎

We can now use a bound on the smallest positive root of $f_{m}(x)$, the proof
of which is included at the end of this section, to show that that certain
domination polynomials are unimodal.

######  Lemma 7.3.

For $m\in\mathbb{N}$, the smallest positive real root of
$f_{m}(x)=x^{m+1}-x^{m}-2x+1$ lies in the range
$\left(\frac{1}{2}-\frac{1}{2^{m+1}},\frac{1}{2}\right)$.

When the above bounds $w_{m}$ are sufficiently close to $\frac{1}{2}$ with
respect to the number of vertices $n$, we can conclude that the latter half of
the domination coefficients is non-increasing.

######  Theorem 7.4.

If $G$ is a graph on $n$ vertices having at least $\log_{2}(n)-1$ universal
vertices, then $D(G,x)$ is unimodal with a mode at
$\left\lceil\frac{n}{2}\right\rceil$ or
$\left\lceil\frac{n}{2}\right\rceil+1$.

###### Proof.

Let $m$ denote the number of universal vertices of $G$. By Theorem 7.2, we
have
$d_{i}(G)\geq d_{i+1}(G)$ for $i\geq(1-w_{m})n$. Using the estimate
$\frac{1}{2}-w_{m}<\frac{1}{2^{m+1}}$ from Lemma 7.3 along with our assumption
that $m\geq\log_{2}(n)-1$, this implies

$(1-w_{m})n<\left(\frac{1}{2}+\frac{1}{2^{m+1}}\right)n=\frac{n}{2}+\frac{n}{2^{m+1}}\leq\frac{n}{2}+1\,.$

Therefore, we have $d_{i}(G)\geq d_{i+1}(G)$ for $i\geq\frac{n}{2}+1$. Since,
by Theorem 2.2, we also have $d_{i}(G)\leq d_{i+1}(G)$ for $i<\frac{n}{2}$, we
can conclude that $d_{i}(G)$ is unimodal with a mode as claimed. ∎

######  Remark 7.5.

Note that the minimum degree of a graph satisfying the hypotheses of Theorem
7.4 can be as low as $\log_{2}(n)-1$. Thus, these graphs may have minimum
degree as low as half of the lower threshold required to apply Theorem 2.1 by
Beaton and Brown, which assumes that the minimum degree is at least
$2\log_{2}(n)$.

Lastly, we prove the claimed bounds on $w_{m}$, the smallest positive root of
the polynomial $f_{m}(x)=x^{m+1}-x^{m}-2x+1$.

###### Proof of Lemma 7.3.

By Descartes’ Rule of Signs, this polynomial can have at most two positive
real roots. Moreover, since $f_{m}(0),f_{m}(2)>0$ and
$f_{m}\left(\frac{1}{2}\right)<0$, $f_{m}$ must have one root in the interval
$\left(0,\frac{1}{2}\right)$, which we denote by $w_{m}$, and another in the
interval $\left(\frac{1}{2},2\right)$.

We expect $w_{m}$ to approach $\frac{1}{2}$ from below as $m$ increases. So we
let $\varepsilon_{m}=\frac{1}{2}-w_{m}>0$ and estimate $\varepsilon_{m}$.
Using the fact that $(1+\frac{1}{y})^{y}>e$ for all $y<-1$, we have

$(w_{m})^{m}=\left(\frac{1-2\varepsilon_{m}}{2}\right)^{m}=\frac{(1-2\varepsilon_{m})^{-\frac{1}{2\varepsilon_{m}}(-2\varepsilon_{m}m)}}{2^{m}}\leq\frac{e^{-2\varepsilon_{m}m}}{2^{m}}\,.$

Now, additionally using the hypothesis that $2w_{m}-1=(w_{m})^{m}(w_{m}-1)$,
we have

$2\left(\frac{1}{2}-\varepsilon_{m}\right)-1\geq\frac{e^{-2\varepsilon_{m}}}{2^{m}}\left(\left(\frac{1}{2}-\varepsilon_{m}\right)-1\right)\,.$

In particular, recalling that $\varepsilon_{m}<\frac{1}{2}$ we obtain

$\varepsilon_{m}\leq\frac{e^{-2\varepsilon_{m}m}}{2^{m+1}}\left(\frac{1}{2}+\varepsilon_{m}\right)\leq\frac{1}{2^{m+1}}\left(\frac{1}{2}+\varepsilon_{m}\right)=\frac{1}{2^{m+2}}+\frac{\varepsilon_{m}}{2^{m+1}}<\frac{1}{2^{m+1}}\,.$

This yields the corresponding lower bound for $w_{m}$. ∎

##  8\. Further Directions

As discussed in Section 3, the unimodality of the domination polynomials for
families of graphs with low minimum degree is of particular interest. We show
that spiders with at most $400$ legs have unimodal domination polynomials, so
a natural extension would be showing this result for an arbitrary number of
legs. If Conjecture 3.7 holds, this would be sufficient to prove unimodality
for all spider graphs. Part of this conjecture asserts that the operation of
leaf deletion yields a domination polynomial having a mode of distance at most
$1$ from a mode of the original domination polynomial. In fact, we have not
yet found a counterexample to this phenomenon for trees, leading to the
following question.

######  Question 8.1.

Does there exist a tree $T$ and a leaf $v\in V(T)$ such that $D(T)$ and
$D(T\backslash v)$ are both unimodal but have no modes of distance at most
$1$?

In Subsection 5.2, we show that the Cartesian product of any two complete
graphs is unimodal with a mode at $\left\lceil\frac{n}{2}\right\rceil$ using
Theorem 2.1. If one considers Cartesian products of arbitrarily many complete
graphs, it is straightforward to see that there are infinitely many graphs
that do not satisfy the hypotheses of Theorem 2.1, unlike in the direct
product case. It would be interesting to develop new techniques for showing
unimodality for this family, which may generalize to higher order products.

We examined graphs with many vertices of the highest possible degree in
Section 7. It seems likely that the results in this section could be
generalized for graphs with many vertices of the near highest degree, i.e.,
for graphs with $m$ vertices of degree $n-k$ for fixed $k$ and sufficiently
large $n$. In this setting, it would be interesting to determine the threshold
for $m$ (in terms of $n$ and $k$) after which one could determine that the
domination polynomial is unimodal with a mode at
$\left\lceil\frac{n}{2}\right\rceil$.

##  9\. Acknowledgements

The authors thank Joe Gallian for his tireless efforts leading the Duluth REU
community. They furthermore thank Colin Defant, Milan Haiman, Noah Kravitz,
and Yelena Mandelshtam for helpful suggestions and insightful questions. This
research was conducted at the University of Minnesota Duluth Mathematics REU
and was supported, in part, by NSF-DMS Grant 1949884 and NSA Grant
H98230-20-1-0009. The first author was also supported by a Marshall
scholarship, and additional support for the second author was provided by the
Mitya.

## References

  * [1] S. Alikhani and S. Jahari. Some families of graphs whose domination polynomials are unimodal. Iranian Journal of Mathematical Sciences and Informatics, 12(1) (2014), 69–80.
  * [2] S. Alikhani and Y. H. Peng. Introduction to domination polynomial of a graph. Ars Combinatoria, 114 (2014), 257–266.
  * [3] J. Azarija, M. Henning, and S. Klavžar. (Total) domination in prisms. The Electronic Journal of Combinatorics, 24(1) (2017), P19.
  * [4] I. Beaton. Domination Polynomials: A Brief Survey and Analysis. Master’s Thesis at Dalhousie University, (2017). https://dalspace.library.dal.ca/handle/10222/73123
  * [5] I. Beaton and J. Brown. On the unimodality of domination polynomials. arXiv:2012.11813 [math.CO], (2020).
  * [6] J. A. Bondy and U. S. R. Murty. Graph Theory with Applications. Elsevier Science Publishing Company, New York, NY (1976).
  * [7] B. Brešar, S. Klavžar, and D. F. Rall. Dominating direct products of graphs. Discrete Mathematics, 307 (2007), 1636--1642.
  * [8] J. Brown and J. Tufts. On the roots of domination polynomials. Graphs and Combinatorics, 30 (2014), 527--547.
  * [9] A. Burcroff. Domination parameters of the unitary Cayley graph of $\mathbb{Z}/n\mathbb{Z}$. Discussiones Mathematicae Graph Theory [to appear], https://doi.org/10.7151/dmgt.2352, (2021).
  * [10] A. Burcroff. Tightness of domination inequalities for direct product graphs. Discrete Mathematics, 344(9) (2021), 112495.
  * [11] C. Defant and S. Iyer. Domination and upper domination of direct product graphs. Discrete Mathematics, 341 (2018), 2742--2752.
  * [12] R. Hammack, W. Imrich, and S. Klavžar. Handbook of Product Graphs. CRC Press, Boca Raton, FL (2011).
  * [13] F. Harary and M. Livingston. Independent domination in hypercubes. Applied Mathematics Letters, 6(3) (1993), 27--28.
  * [14] T. Kotek, J. Preen, F. Simon, P. Tittmann, and M. Trinks. Recurrence relations and splitting formulas for the domination polynomial. The Electronic Journal of Combinatorics, 19(3) (2012), P47.
  * [15] R. Nowakowski and D. F. Rall. Associative graph products and their independence, domination and coloring numbers. Discussiones Mathematicae Graph Theory, 16 (1996), 53--79.
  * [16] H. Vemuri. Domination in direct products of complete graphs. Discrete Applied Mathematics, 285 (2020), 473--482.
  * [17] V. G. Vizing. Some unsolved problems in graph theory. Russian Mathematical Surveys, 23(6) (1968), 125--141.


C-ITS

    cooperative intelligent transportation system
V2V

    vehicle-to-vehicle
V2I

    vehicle-to-infrastructure
LSTM

    long short term memory
TDL

    tapped delay line
TA

    temporal averaging
VTV

    vehicle-to-vehicle
AWGN

    additive white Gaussian noise
RTV

    roadside-to-vehicle
STA

    spectral temporal averaging
SNR

    signal-to-noise ratio
CDP

    constructed data pilots
TRFI

    time domain reliable test frequency domain interpolation
MMSE-VP

    minimum mean square error using virtual pilots
DL

    deep learning
DPA

    data-pilot aided
AE-DNN

    auto-encoder deep neural network
DNN

    deep neural networks
ISI

    inter-symbol-interference
OFDM

    orthogonal frequency-division multiplexing
LS

    least square
RS

    reliable subcarriers
URS

    unreliable subcarriers
MMSE

    minimum mean squared error
NMSE

    normalized mean-squared error
SoA

    state-of-the-art
BER

    bit error rate
RSU

    road side unit
AE

    auto-encoder
CP

    cyclic prefix
PLCP

    physical layer convergence protocol
MSE

    mean squared error

# Temporal Averaging LSTM-based Channel Estimation Scheme for IEEE 802.11p
Standard

Abdul Karim Gizzini1, Marwa Chafii3, Shahab Ehsanfar2, Raed M. Shubair3
1ETIS, UMR8051, CY Cergy Paris Université, ENSEA, CNRS, France
2 Professorship of Communications Engineering, Technische Universität
Chemnitz, Germany
3 Department of Electrical and Computer Engineering, New York University
(NYU), Abu Dhabi 129188, UAE
Email: abdulkarim.gizzini<EMAIL_ADDRESS>{marwa.chafii<EMAIL_ADDRESS>
###### Abstract

In vehicular communications, reliable channel estimation is critical for the
system performance due to the doubly-dispersive nature of vehicular channels.
IEEE 802.11p standard allocates insufficient pilots for accurate channel
tracking. Consequently, conventional IEEE 802.11p estimators suffer from a
considerable performance degradation, especially in high mobility scenarios.
Recently, deep learning (DL) techniques have been employed for IEEE 802.11p
channel estimation. Nevertheless, these methods suffer either from performance
degradation in very high mobility scenarios or from large computational
complexity. In this paper, these limitations are solved using a long short
term memory (LSTM)-based estimation. The proposed estimator employs an LSTM
unit to estimate the channel, followed by temporal averaging (TA) processing
as a noise alleviation technique. Moreover, the noise mitigation ratio is
determined analytically, thus validating the TA processing ability in
improving the overall performance. Simulation results reveal the performance
superiority of the proposed schemes compared to the recently proposed DL-based
estimators, while recording a significant reduction in the computational
complexity.

###### Index Terms:

Channel estimation, deep learning, LSTM, vehicular communications, IEEE
802.11p standard.

##  I Introduction

Vehicular communication technologies [1] describe a set of communication
models that can be employed by vehicles in different application contexts,
resulting in a well organized network infrastructure. The main motivation
behind such technologies is to facilitate several future smart city
applications including road safety and autonomous driving.

In general, wireless communications in vehicular environment encounter a
critical reliability challenge due to the doubly selective nature of the
vehicular channel that varies rapidly especially in high mobility scenarios.
Moreover, a precisely-estimated channel is critical for the equalization,
demodulation, and decoding operations performed at the receiver. Therefore,
robust and accurate channel estimation plays a crucial role in determining the
overall system performance. IEEE 802.11p standard is an international standard
that defines vehicular communications specifications. However, IEEE 802.11p
standard is based initially on the IEEE 802.11a standard that was proposed for
indoor environments, where an insufficient number of pilots is allocated for
channel estimation. As a result, IEEE 802.11p conventional estimators are
based on the data-pilot aided (DPA) estimation, where the demapped data
subcarriers, besides pilot subcarriers are employed in the channel estimation.
In order to improve the DPA estimation performance, spectral temporal
averaging (STA) estimator [2] applies averaging in both the time and the
frequency domains as post processing operations to the DPA estimated channel.
STA estimator performs well in low signal-to-noise ratio (SNR) region, however
it suffers from a significant performance degradation in high SNR region
especially in high mobility vehicular scenarios. The time domain reliable test
frequency domain interpolation (TRFI) [3] estimator assumes high correlation
between successive symbols, thus it employs frequency domain interpolation to
improve the DPA performance. TRFI estimator outperforms the STA estimator in
high SNR region, however, these conventional estimators suffer from a
considerable performance degradation in high mobility scenarios.

Recently, the rapid advancements in DL and their successful applications in
several domains, have sparked significant interest to adopt DL techniques for
wireless communication applications including channel estimation. DL
techniques are characterized by robustness, low-complexity, and good
generalization ability making their integration into communication systems
beneficial. Motivated by these advantages, DL algorithms have been used for
IEEE 802.11p channel estimator, where the authors in [4] and [5] employ deep
neural networks (DNN) as a post processing unit after the STA and TRFI
conventional estimators respectively. The simulation results have showed that
STA-DNN and TRFI-DNN are able to significantly improve the performance,
however, they suffer from an error floor in high mobility scenarios. Another
different DL-based approach has been proposed in [6], where LSTM unit followed
by DNN network are employed as a pre-processing modules for channel estimation
and noise error compensation. After that, DPA estimation is applied using the
DNN output. This LSTM-DNN-DPA estimator, outperforms the recently proposed
STA-DNN and TRFI-DNN estimators, but it suffers from a considerable
computational complexity due to the employment of two consecutive DL networks.

In order to overcome the high complexity of the LSTM-DNN-DPA estimator, while
improving the bit error rate (BER) and normalized mean-squared error (NMSE)
performances, in this paper we propose an LSTM-based estimator, where the
channel is estimated using an LSTM unit only. After that, DPA estimation is
applied using the LSTM estimated channel. Finally, unlike the LSTM-DNN-DPA
estimator where DNN network is used for noise elimination, in the proposed
estimator, TA processing is employed as a noise alleviation technique where
the noise alleviation ratio is calculated analytically. We also provide a
detailed computational complexity analysis and make a comparison between the
recent related work on LSTM-DNN-DPA estimator and our proposed LSTM-DPA-TA
estimator.

The remainder of this paper is organized as follows: in Section II, the system
model followed by the recently proposed state-of-the-art (SoA) DL-based IEEE
802.11p estimators are provided. The proposed LSTM-DPA-TA, as well as the TA
processing analytical derivation, are described in Section III. In Section IV,
simulation results and computational complexity analysis are presented where
the performance of the proposed scheme is evaluated in terms of BER. Finally,
the paper is concluded in Section V.

##  II SoA DNN-Based Channel Estimators

###  II-A System Model

IEEE 802.11p standard employs orthogonal frequency-division multiplexing
(OFDM) transmission scheme with ${K=64}$ total subcarriers.
${K_{\text{on}}=52}$ active subcarriers are used, and they are divided into
${K_{\text{d}}=48}$ data subcarriers and ${K_{\text{p}}=4}$ pilot subcarriers.
The remaining ${K_{\text{n}}=12}$ subcarriers are used as a guard band.
Moreover, IEEE 802.11p frame structure consists mainly of three parts. The
first part contains the preamble that is used at the receiver for signal
detection, timing synchronization, and channel estimation. Second, the signal
field carries the transmission parameters like the employed code rate,
modulation order, and frame length. Finally, we have the OFDM data symbols. A
detailed discussion of the IEEE 802.p standard and all its features are
presented in [7].

Figure 1: LSTM-based IEEE 802.11p channel estimators block diagram.

In this paper, we assume perfect synchronization at the receiver, and we omit
the signal field for simplicity. Therefore, we consider only the two long
training symbols followed by $I$ OFDM data symbols within each transmitted
frame. The received OFDM symbol can be expressed as:

$\small\tilde{\bm{y}}_{i}[k]=\left\\{\begin{array}[]{ll}\tilde{\bm{h}}_{i,d}[k]\tilde{\bm{x}}_{i,d}[k]+\tilde{\bm{v}}_{i,d}[k],&\quad
k\in{\mathcal{K}}_{\text{d}}\\\
\tilde{\bm{h}}_{i,p}[k]\tilde{\bm{x}}_{i,p}[k]+\tilde{\bm{v}}_{i,p}[k],&\quad
k\in{\mathcal{K}}_{\text{p}}\\\ \end{array}\right.,$ (1)

where $\tilde{\bm{x}}_{i}[k]$ and $\tilde{\bm{h}}_{i}[k]$ denote the $i$-th
transmitted OFDM symbol and its respective time variant frequency-domain
channel response. Moreover, $\tilde{\bm{v}}_{i}[k]$ represents the frequency-
domain counterpart of additive white Gaussian noise (AWGN) of variance
$\sigma^{2}$. ${\mathcal{K}}_{\text{d}}$ and ${\mathcal{K}}_{\text{p}}$ are
the sets of data and pilot subcarriers indices respectively.

###  II-B IEEE 802.11p Channel Estimators

####  II-B1 DPA Basic Estimation

The DPA basic estimation employs the demapped data subcarriers besides pilots
subcarriers to estimate the channel for the current OFDM symbol, such that

$\small\bm{d}_{i}[k]=\mathfrak{D}\big{(}\frac{\bm{y}_{i}[k]}{\hat{\tilde{\bm{h}}}_{\text{DPA}_{i-1}}[k]}\big{)},~{}\hat{\tilde{\bm{h}}}_{\text{DPA}_{0}}[k]=\hat{\tilde{\bm{h}}}_{\text{LS}}[k],~{}k\in{\mathcal{K}}_{\text{on}},$
(2)

where $\mathfrak{D}(.)$ is the demapping operation to the nearest
constellation point according to the employed modulation order.
$\hat{\tilde{\bm{h}}}_{\text{LS}}[k]$ refers to the LS estimated channel at
the received preambles denoted as $\bm{y}^{(p)}_{1}[k]$, and
$\bm{y}^{(p)}_{2}[k]$, such that

$\small\hat{\tilde{\bm{h}}}_{\text{LS}}[k]=\frac{\bm{y}^{(p)}_{1}[k]+\bm{y}^{(p)}_{2}[k]}{2\bm{p}[k]},~{}k\in{\mathcal{K}}_{\text{on}},$
(3)

where $\bm{p}[k]$ represents the frequency domain predefined preamble
sequence. After that, the final DPA channel estimated are updated as follows

$\small\hat{\tilde{\bm{h}}}_{\text{DPA}_{i}}[k]=\frac{\bm{y}_{i}[k]}{\bm{d}_{i}[k]},~{}k\in{\mathcal{K}}_{\text{on}}.$
(4)

It is worth mentioning that the DPA basic estimation is considered as the
starting point by most of the IEEE 802.11p channel estimators.

####  II-B2 STA-DNN Estimator

The authors in [4] discovered that employing an optimized DNN after the
conventional STA estimator [2] leads to significant performance improvement,
while recording lower computational complexity. This is because the
conventional STA estimation applies averaging in both frequency and time
successively to the DPA estimated channel in (4), such that

$\small\hat{\tilde{\bm{h}}}_{\text{FD}_{i}}[k]=\sum_{\lambda=-\beta}^{\lambda=\beta}\omega_{\lambda}\hat{\tilde{\bm{h}}}_{\text{DPA}_{i}}[k+\lambda],~{}\omega_{\lambda}=\frac{1}{2\beta+1},k\in{\mathcal{K}}_{\text{d}},$
(5)

$\small\hat{\tilde{\bm{h}}}_{\text{STA}_{i}}[k]=(1-\frac{1}{\alpha})\hat{\tilde{\bm{h}}}_{\text{STA}_{i-1}}[k]+\frac{1}{\alpha}\hat{\tilde{\bm{h}}}_{\text{FD}_{i}}[k],k\in{\mathcal{K}}_{\text{on}},$
(6)

where $\beta$ and $\omega_{\lambda}$ refer to the STA frequency averaging
window size and weight respectively, while $\alpha\geq 1$ defines the STA time
averaging weight. The main STA limitation is that the averaging parameters
should be updated according to the real-time channel statistics, that are not
available in practice. Therefore, the STA averaging parameters are fixed,
resulting in a performance degradation especially in high SNR regions and high
mobility vehicular scenarios. However, as discussed in [4], when the
$\hat{\tilde{\bm{h}}}_{\text{STA}_{i}}[k]$ is fed as an input to an STA-DNN
network, more time-frequency channel correlation can be captured, besides
correcting the conventional STA estimation error. Thus, the overall
performance is significantly improved. However, an error floor still appears
in high mobility vehicular scenario, especially in high SNR region.

####  II-B3 TRFI-DNN Estimator

The DPA estimation in (4) can be further improved by applying the TRFI [3],
where the subcarriers of the received OFDM symbol are divided into: (i)
${\mathcal{RS}}_{i}$ set: that includes the reliable subcarriers indices, and
(ii) ${\mathcal{URS}}_{i}$ set: which contains the unreliable subcarriers
indices. Then, the estimated channels for the ${\mathcal{URS}}_{i}$ are
interpolated using the ${\mathcal{RS}}_{i}$ channel estimates. TRFI employs
frequency domain cubic interpolation assuming high correlation between two
successive received OFDM symbols. This procedure can be expressed as follows

  * •

Equalize the previously received OFDM symbol by
${\hat{\tilde{\bm{h}}}_{\text{TRFI}_{i-1}}[k]}$ and
${\hat{\tilde{\bm{h}}}_{\text{DPA}_{i}}[k]}$, such that

$\small\begin{split}{\bm{d^{\prime}}_{i-1}[k]}=\mathfrak{D}\big{(}\frac{\bm{y}_{i-1}[k]}{\hat{\tilde{\bm{h}}}_{\text{DPA}_{i}}[k]}\big{)},~{}{\bm{d^{\prime\prime}}_{i-1}[k]}=\mathfrak{D}\big{(}\frac{\bm{y}_{i-1}[k]}{\hat{\tilde{\bm{h}}}_{\text{TRFI}_{i-1}}[k]}\big{)}.\end{split}$
(7)

  * •

According to the demapping results, the subcarriers are grouped as follows

$\small\left\\{\begin{array}[]{ll}{\mathcal{RS}}_{i}\leftarrow{\mathcal{RS}}_{i}+{k},&\quad\bm{d^{\prime}}_{i-1}[k]=\bm{d^{\prime\prime}}_{i-1}[k]\\\
{\mathcal{URS}}_{i}\leftarrow{\mathcal{URS}}_{i}+{k},&\quad\bm{d^{\prime}}_{i-1}[k]\neq\bm{d^{\prime\prime}}_{i-1}[k]\end{array}\right..$
(8)

  * •

Finally, frequency domain cubic interpolation is employed to estimate the
channels at the ${\mathcal{URS}}_{i}$ as follows

$\small\hat{\tilde{\bm{h}}}_{\text{TRFI}_{i}}[k]=\left\\{\begin{array}[]{ll}\hat{\tilde{\bm{h}}}_{\text{DPA}_{i}}[k],&\quad
k\in{\mathcal{RS}}_{i}\\\ \text{Cubic Interpolation},&\quad
k\in{\mathcal{URS}}_{i}\end{array}\right..$ (9)

In order to outperform the STA-DNN performance limitation in high mobility
vehicular scenarios (high SNR region), the authors in [5], used the same
optimized DNN architecture as in [4], but with
$\hat{\tilde{\bm{h}}}_{\text{TRFI}_{i}}[k]$ as an input instead of
$\hat{\tilde{\bm{h}}}_{\text{STA}_{i}}[k]$. TRFI-DNN corrects the cubic
interpolation error, besides learning the channel frequency domain
correlation, thus improving the performance in high SNR region.

####  II-B4 LSTM-DNN-DPA Estimator

Unlike the recently proposed DNN-based estimators, where the DL processing is
employed after the conventional estimators, the work performed in [6] show
that employing the DL processing before the conventional estimator
(specifically the DPA estimation), could improve significantly the overall
performance. In this context, the authors proposed to use two cascaded LSTM
and DNN networks to estimate the channel for the current OFDM symbol as shown
in Fig. 1. After that, a DPA estimation is applied using the LSTM-DNN
estimated channel. Even though, the LSTM-DNN-DPA estimator can outperform the
recently proposed DNN-based estimators, it suffers from a considerable
computational complexity that rises from the employment of two DL networks.

##  III Proposed LSTM-based Estimation Scheme

In this section, the proposed LSTM based estimator is discussed. First of all,
a brief description of LSTM network is presented. After that, the proposed TA
noise power alleviation is analytically derived.

###  III-A LSTM Overview

LSTM networks are basically proposed to deal with sequential data where the
order of the data matters and there exists a correlation between the previous
and the future data. In this context, LSTM networks are defined with an
appropriate architecture that can learn the data correlation over time, thus
giving the LSTM network the ability to predict the future data based on the
previous observations.

LSTM unit contains computational blocks known as gates which are responsible
for controlling and tracking the information flow over time. The LSTM network
mechanism can be explained in four major steps as follow

##### Forget the irrelevant information

In general, the LSTM unit classify the input data into relevant and irrelevant
information. The first processing step is to eliminate the irrelevant
information that are not important for the future data prediction. This can be
performed through the forget gate that decides which information the LSTM unit
should keep, and which information it should delete. The forget gate
processing is defined as below

$\small{\bm{f}}_{t}={\sigma}(\bm{W}_{f,t}\bar{\bm{x}}_{t}+\bm{W}^{\prime}_{f,t}\bar{\bm{h}}_{t-1}+\bar{\bm{b}}_{f,t}),$
(10)

where ${\sigma}$ is the sigmoid function, $\bm{W}_{f,t}\in\mathbb{R}^{P\times
K_{in}}$, $\bm{W}^{\prime}_{f,t}\in\mathbb{R}^{P\times P}$ and
$\bar{\bm{b}}_{f,t}\in\mathbb{R}^{P\times 1}$ are the forget gate weights and
biases at time $t$, $\bar{\bm{x}}_{t}\in\mathbb{R}^{K_{in}\times 1}$ and
$\bar{\bm{h}}_{t-1}$ denote the LSTM unit input vector of size $K_{in}$, and
the previous hidden state of size $P$ respectively.

##### Store the relevant new information

After classifying the relevant information, the LSTM unit applies some
computations on the selected information through the input gate

$\small{\bar{\bm{i}}_{t}}={\sigma}(\bm{W}_{\bar{\bm{i}},t}\bar{\bm{x}}_{t}+\bm{W}^{\prime}_{\bar{\bm{i}},t}\bar{\bm{h}}_{t-1}+\bar{\bm{b}}_{\bar{\bm{i}},t}),$
(11)
$\small{\tilde{{\bm{c}}}}_{t}=\text{tanh}(\bm{W}_{{\tilde{{\bm{c}}}},t}\bar{\bm{x}}_{t}+\bm{W}^{\prime}_{{\tilde{{\bm{c}}}},t}\bar{\bm{h}}_{t-1}+\bar{\bm{b}}_{{\tilde{{\bm{c}}}},t}).$
(12)

##### Update the new cell state

Now, the LSTM unit should update the current cell state ${{{\bm{c}}}}_{t}$
based on the two previous steps such that

$\small{{{\bm{c}}}}_{t}={\bm{f}}_{t}\odot{\bm{c}}_{t-1}+\bar{\bm{i}}_{t}\odot{\tilde{{\bm{c}}}}_{t},$
(13)

where $\odot$ denotes the Hadamard product.

##### Generate the LSTM unit output

The final processing step is to update the hidden state and generate the
output by the output gate. The output is considered as a cell state filtered
version and can be computed such that

$\small{\bm{o}}_{t}={\sigma}(\bm{W}_{o,t}\bar{\bm{x}}_{t}+\bm{W}^{\prime}_{o,t}\bar{\bm{h}}_{t-1}+\bar{\bm{b}}_{o,t}),$
(14) $\small{\bar{{\bm{h}}}}_{t}={\bm{o}}_{t}\odot\text{tanh}{\bm{c}}_{t}.$
(15)

We note that, in literature there exists several LSTM architecture variants,
where the interactions between the LSTM unit gates are modified. The authors
in [8] performed a nice comparison of popular LSTM architecture variants.
However, for the proposed estimator we focus on the classical LSTM unit
architecture.

Figure 2: LSTM unit architecture.

###  III-B Proposed LSTM-TA Estimator

Unlike the LSTM-DNN-DPA estimator, where the LSTM and DNN networks are used
for channel estimation and noise compensation respectively, the proposed
estimator employs only LSTM. Moreover, the LSTM input dimension is decreased
to include only $K_{on}$ subcarriers, therefore the overall computational
complexity is significantly reduced. The proposed estimator proceeds as
follows:

##### LSTM-based prediction

: The first step is to estimate the channel for the current received OFDM
symbol employing the previous estimated channel
$\hat{\tilde{\bm{h}}}_{\text{DL-TA}_{i-1,d}[k]}$, where the $i$-th LSTM unit
input is denoted by $\tilde{\bar{{\bm{x}}}}_{{i}}\in\mathbb{R}^{2K_{on}\times
1}$, where

$\small\bar{\bm{x}}_{i}=\left\\{\begin{array}[]{ll}\hat{\tilde{\bm{h}}}_{\text{LSTM}_{i-1,d}}[k],&\quad
k\in{\mathcal{K}}_{\text{d}}\\\ \hat{\tilde{\bm{h}}}_{{i-1,p}}[k],&\quad
k\in{\mathcal{K}}_{\text{p}}\end{array}\right..$ (16)

$\tilde{\bar{{\bm{x}}}}_{{i}}$ is obtained by applying complex to real valued
conversion to $\bar{\bm{x}}_{i}$ by stacking its real and imaginary values in
one vector. We note that $\hat{\tilde{\bm{h}}}_{{i-1,p}}[k]$ denotes the least
square (LS) estimated channel at the ${\mathcal{K}}_{\text{p}}$ subcarriers.
After that, $\tilde{\bar{{\bm{x}}}}_{{i}}$ is processed by the LSTM unit, such
that

$\small\hat{\tilde{\bm{h}}}_{\text{LSTM}_{i,d}}=\Omega_{\text{LSTM}}(\tilde{\bar{\bm{x}}}_{i},\Theta),$
(17)

where $\Omega_{\text{LSTM}}$ is the LSTM unit processing with overall weights
denoted by $\Theta$.

##### DPA estimation

The LSTM estimated channel undergoes DPA estimation using the $i$-th received
OFDM symbol as follows

$\small\bm{d}_{\text{LSTM}_{i}}[k]=\mathfrak{D}\big{(}\frac{\bm{y}_{i}[k]}{\hat{\tilde{\bm{h}}}_{\text{LSTM}_{i-1}}[k]}\big{)},~{}\hat{\tilde{\bm{h}}}_{\text{LSTM}_{0}}[k]=\hat{\tilde{\bm{h}}}_{\text{LS}}[k],$
(18)

$\small\hat{\tilde{\bm{h}}}_{\text{LSTM-
DPA}_{i}}[k]=\frac{\bm{y}_{i}[k]}{\bm{d}_{\text{LSTM}_{i}}[k]}.$ (19)

##### TA processing

Finally, in order to alleviate the impact of the AWGN noise, TA processing is
applied to the $\hat{\tilde{\bm{h}}}_{\text{LSTM-DPA}_{i}}[k]$ estimated
channel, such that

$\small\hat{\bar{\bm{h}}}_{\text{DL-
TA}_{i,d}}=(1-\frac{1}{\alpha})\hat{\bar{\bm{h}}}_{\text{DL-
TA}_{i-1,d}}+\frac{1}{\alpha}\hat{\bar{\bm{h}}}_{\text{LSTM-DPA}_{i,d}}.$ (20)

In this paper we used a fixed $\alpha=2$ for simplicity. Therefore, the TA
applied in (20) degrades the AWGN noise power $\sigma^{2}$ iteratively within
the received OFDM frame according to the ratio

$\small\begin{split}{R}_{\text{DL-
TA}_{q}}&=\left(\frac{1}{4}\right)^{(q-1)}+\sum_{j=2}^{q}\left(\frac{1}{4}\right)^{(q-j+1)}=\frac{4^{q-1}+2}{3\times
4^{q-1}}.\end{split}$ (21)

${R}_{\text{DL-TA}_{q}}$ denotes the AWGN noise power ratio of the estimated
channel at the $q$-th estimated channel, where ${1<q<I+1}$ and
${{R}_{\text{DL-TA}_{1}}=1}$ denotes the AWGN noise power ratio at
$\hat{\tilde{\bm{h}}}_{\text{LS}}[k]$. The full derivation of (21) is provided
in Appendix A. It can be seen from the derivation of ${R}_{\text{DL-TA}_{q}}$
that the noise power is decreasing iteratively over the received OFDM frame,
hence the SNR increase which leads to better overall performance.

TABLE I: Proposed LSTM parameters. (LSTM units; Hidden size) | (1;128)
---|---
Activation function | ReLU ($y=\max(0,x)$)
Number of epochs | 500
Training samples | 16000
Testing samples | 2000
Batch size | 128
Optimizer | ADAM
Loss function | MSE
Learning rate | 0.001
Training SNR | 40 dB

(a)  BER performance employing high mobility scenario.

(b)  NMSE performance employing high mobility scenario.

(c)  BER performance employing very high mobility scenario.

(d)  NMSE performance employing very high mobility scenario.

Figure 3: VTV-SDWW vehicular channel model simulation results.

The proposed LSTM training is performed using SNR = 40 dB to achieve the best
performance as observed in [9], due to the fact that when the training is
performed for a high SNR value, the LSTM is able to better learn the channel
statistics, and due to its good generalization ability, it can still perform
well in low SNR regions, where the noise is dominant. Moreover, intensive
experiments are performed using the grid search algorithm [10] in order to
select the best suitable LSTM hyper parameters in terms of both performance
and complexity. Table. I summarizes the proposed LSTM training parameters.

##  IV Simulation Results

LSTM-DNN-DPALSTM-DPA-TA (P=128)LSTM-DPA-TA (P=64)$0$$50$$100$Real-Valued
Operations x $10^{3}$Multiplications/DivisionsSummations/Subtractions Figure
4: Computational complexity of the studied channel estimators.

In this section, BER and NMSE simulations followed by a computational
complexity analysis are conducted in order to evaluate the performance of the
proposed estimator compared to IEEE 802.11p DL-based estimators.

In this paper, we consider the VTV-SDWW tapped delay line (TDL) vehicular
channel model [11] with two different mobility conditions: (i) High mobility:
V = 100 km/hr, with Doppler shift $f_{d}$ = 550 Hz. (ii) Very high mobility: V
= 200 km/hr, with $f_{d}$ = 1100 Hz. VTV-SDWW channel model represents the
communication channel between two vehicles moving on a highway having center
wall between its lanes, and it was obtained by a measurement campaign
implemented in metropolitan Atlanta. Detailed measurement setups are provided
in [12]. Concerning the simulation parameters, 16QAM modulation is employed
over a frame size of $I=50$ OFDM symbols. The used channel coding is
convolutional with half code rate. Moreover, three hidden layer DNN with $15$
neurons each is employed in the STA-DNN and TRFI-DNN estimators, with
$\alpha=\beta=2$ as defined in [4].

###  IV-A BER and NMSE Performances

Fig. 3 depict the BER and NMSE performances of high and very high mobility
vehicular scenarios respectively. As we can notice, the DNN-based estimators
suffer from error floor, especially in high SNR region. Moreover, the LSTM-
DNN-DPA estimator outperforms them in the entire SNR regions. This is
explained by the high ability of the LSTM in capturing the temporal
correlations of the channel more than the DNN network.

On the other hand, the proposed LSTM-DPA-TA estimator is able to outperform
the LSTM-DNN-DPA estimator in high mobility scenario by $7$ dB and $5$ dB
gains in terms of SNR at BER = $10^{-3}$, when $P=128$ and $P=64$ are employed
respectively. We note that employing larger LSTM hidden state size, i.e
$P=128$ achieves better performance than the optimized LSTM unit ($P=64$).
However, in very high mobility scenario, since the temporal correlation
between subsequent channel realizations significantly reduces, the proposed
estimators outperform the LSTM-DNN-DPA estimator by around $3$ dB gains in
terms of SNR at BER = $10^{-3}$. The proposed estimator performance gain in
both scenarios is mainly due to employing the TA processing which reduces the
AWGN noise significantly. Moreover, the LSTM achieves better channel
estimation performance than DNN while significantly reducing the computational
complexity. This can be explained by the high ability of LSTM in learning the
channel time correlations, compared with a simple DNN architecture.

###  IV-B Computational Complexity Analysis

In general, the estimator computational complexity is expressed in terms of
real-valued multiplication/division and summation/subtraction mathematical
operations required to estimate the channel for one received OFDM symbol. We
note that STA-DNN and TRFI-DNN achieve lower complexity compared to the LSTM-
based estimators because LSTM processing requires more operations than DNN
processing. Thus, in the following analysis we will focus on comparing the
proposed LSTM-DPA-TA estimator with the LSTM-DNN-DPA estimator.

In [4], the authors provide a detailed computational complexity analysis of
the DNN-based estimators, where the computational complexity of the DNN
network denoted by $C_{\text{DNN}}$ can be expressed as follows

$\small C_{\text{DNN}}=2\sum_{l=1}^{L+1}{N}_{l-1}{N}_{l},$ (22)

where $L$ is the number of hidden layers within the DNN network with $N_{l}$
neurons each, and $N_{0}$, $N_{L+1}$ denote the input and output DNN network
dimensions respectively.

For the computational complexity of the LSTM unit, it can be calculated in
terms of the required real values operations performed by its four gates,
where each gate applies $P^{2}+PK_{in}$ real-valued multiplications, and
$3P+K_{in}-2$ real-valued summations. In addition to $3P$ real-valued
multiplications, and $P$ real-valued summations required by (13), and (15).
Therefore, the overall computational complexity for the LSTM becomes

$\small C_{\text{LSTM}}=4(P^{2}+PK_{in}+3P+K_{in}-2)+4P.$ (23)

The LSTM-DNN-DPA estimator employs one LSTM unit with $P=128$ and
$K_{in}=112$, followed by one hidden layer DNN network with $N_{1}=40$
neurons. Finally, the LSTM-DNN-DPA estimator applies the DPA estimation which
requires $18K_{d}$ real-valued multiplication/division and $8K_{d}$ real-
valued summation/subtraction. Therefore, the overall computational complexity
of the LSTM-DNN-DPA estimator is $512K_{\text{in}}+98K_{d}+71040$ real-valued
multiplication/division and $4K_{\text{in}}+88K_{d}+6776$ real-valued
summation/subtraction.

For the proposed LSTM-DPA-TA estimator, it employs one LSTM unit with $P=128$
as LSTM-DNN-DPA estimator, or $P=64$ when the optimized LSTM unit architecture
is employed. Moreover, the proposed estimator uses $K_{in}=2K_{on}$, and
applies TA as a noise alleviation technique to the
$\hat{\bar{\bm{h}}}_{\text{LSTM-DPA}_{i,d}}$ estimated channel, that requires
only $2K_{on}$ real-valued multiplication/division and $2K_{on}$ real-valued
summation/subtraction. As a results, the proposed LSTM-DPA-TA estimator
requires $4P^{2}+P(8K_{on}+3)+18K_{d}+2K_{on}$ real-valued
multiplication/division and $13P+10K_{on}+8K_{d}-8$ real-valued
summation/subtraction.

Based on this analysis, the proposed estimator achieves less computational
complexity compared to the LSTM-DNN-DPA estimator. It records $9.73\%$ and
$77.63\%$ computational complexity decrease in the required real-valued
multiplication/division and summation/subtraction respectively, when the LSTM
unit is employed with $P=128$ hidden size. On the other hand, more complexity
reduction can be achieved when the optimized LSTM unit is used with $P=64$
hidden size, where the proposed estimator is able to decrease the complexity
of the required multiplication/division and summation/subtraction by $66.81\%$
and $84.90\%$ respectively. It is worth mentioning that replacing the DNN
network by the TA processing in order to alleviate the AWGN noise is the main
factor in decreasing the overall computational complexity, where the proposed
estimator outperforms the LSTM-DNN-DPA estimator while recording a significant
computational complexity reduction. Fig. 4 shows a detailed computational
analysis of the benchmarked estimators in terms of real-valued operations.

##  V Conclusion

In this paper, we have investigated the channel estimation challenge in
vehicular environments. This challenge arises from the doubly selective nature
of the vehicular channel, especially in high mobility scenarios. The recently
proposed DL-based IEEE 802.11p estimators have been presented and their
limitations have been discussed. In order to overcome these limitations, we
have proposed an LSTM-based estimator, that employs an LSTM unit for channel
estimation, and a TA processing as a noise alleviation technique. Simulation
results have shown the performance superiority of the proposed LSTM-DPA-TA
estimator over the recently proposed DL-based estimators, while recording a
significant reduction in computational complexity.

###  -A TA noise power alleviation ratio

According to the TA processing applied in (20), and assuming that the noise
terms of consecutive symbols are uncorrelated, the noise power for the $q$-th
estimated channel is expressed as follows

$\small{R}_{\text{DL-
TA}_{q}}=\mathrm{E}\left[\left\lVert\frac{\tilde{\bm{v}}_{{q-1}}}{2}+\frac{\tilde{\bm{v}}_{{q}}}{2}\right\rVert^{2}\right]=\frac{\sigma_{{q-1}}^{2}}{4}+\frac{\sigma_{{q}}^{2}}{4}.$
(24)

Where $\tilde{\bm{v}}_{{q}}$ denotes the AWGN noise at the $q$-th received
OFDM symbol. We consider that $\hat{\bar{\bm{h}}}_{\text{DL-
TA}_{1}}=\hat{\tilde{\bm{h}}}_{\text{LS}}$, therefore the noise power of the
first estimated channel is $\sigma^{2}$, and the noise power enhancement ratio
for the successive estimated channels can be computed as follows

$\small{R}_{\text{DL-TA}_{q}}=\left\\{\begin{array}[]{ll}1,&\quad q=1\\\ \\\
\frac{1}{4}+\frac{1}{4}=\frac{1}{2},&\quad q=2\\\ \\\ \frac{\bm{R}_{\text{DL-
TA}_{q-1}}}{4}+\frac{1}{4},&\quad 3<q\leq I+1\end{array}\right.$ (25)

The generalization formula of (25) can be written as a sequence where the
first element ${R}_{\text{DL-TA}_{1}}=1$ as follows

$\small\begin{split}{R}_{\text{DL-TA}_{q}}&=\frac{1}{4}{R}_{\text{DL-
TA}_{q-1}}+\frac{1}{4}=\frac{1}{4}\left({R}_{\text{DL-TA}_{q-1}}+1\right)\\\
&=\frac{1}{4}\left(\frac{1}{4}{R}_{\text{DL-TA}_{q-2}}+\frac{1}{4}+1\right)\\\
&=\frac{1}{4}\left(\frac{1}{4}\left(\frac{1}{4}R_{\text{DL-
TA}_{q-3}}+\frac{1}{4}\right)+\frac{1}{4}+1\right)\\\
&=\frac{1}{4}\left(\frac{1}{4^{(q-1)-1}}{{R}}_{\text{DL-
TA}_{q-(q-1)}}+\frac{1}{4^{(q-1)-1}}+\dots+\frac{1}{4^{0}}\right)\\\
&=\frac{1}{4}\left(\frac{1}{4^{q-2}}{{R}}_{\text{DL-
TA}_{1}}+\frac{1}{4^{q-2}}+\frac{1}{4^{q-3}}+\dots+\frac{1}{4^{0}}\right)\\\
&=\frac{1}{4}\left(\frac{1}{4^{q-2}}+\frac{1}{4^{q-2}}+\frac{1}{4^{q-3}}+\dots+\frac{1}{4^{0}}\right).\end{split}$
(26)

The sequence derived in (26) can be written as follows:

$\small{R}_{\text{DL-
TA}_{q}}=\frac{1}{4}\left(\frac{1}{4^{q-2}}+\sum_{j=2}^{q}\left({\frac{1}{4}}\right)^{q-j}\right).$
(27)

Let $j^{\prime}=q-j$, then (27) can be written in terms of $j^{\prime}$
according to the summation of geometric sequence rule [13] such that

$\small{R}_{\text{DL-
TA}_{q}}=\frac{1}{4}\left(\frac{1}{4^{q-2}}+\sum_{j^{\prime}=0}^{q-2}\left({\frac{1}{4}}\right)^{j^{\prime}}\right)=\frac{4^{q-1}+2}{3\times
4^{q-1}}.$ (28)

## Acknowledgment

Authors acknowledge the CY Initiative of Excellence for the support of the
project through the ASIA Chair of Excellence Grant (PIA/ANR-16-IDEX-0008).

## References

  * [1] P. Alexander, D. Haley, and A. Grant, “Cooperative Intelligent Transport Systems: 5.9-GHz Field Trials,” _Proceedings of the IEEE_ , vol. 99, no. 7, pp. 1213–1235, 2011.
  * [2] J. A. Fernandez, K. Borries, L. Cheng, B. V. K. Vijaya Kumar, D. D. Stancil, and F. Bai, “Performance of the 802.11p Physical Layer in Vehicle-to-Vehicle Environments,” _IEEE Transactions on Vehicular Technology_ , vol. 61, no. 1, pp. 3–14, 2012.
  * [3] Yoon-Kyeong Kim, Jang-Mi Oh, Yoo-Ho Shin, and Cheol Mun, “Time and Frequency Domain Channel Estimation Scheme for IEEE 802.11p,” in _17th International IEEE Conference on Intelligent Transportation Systems (ITSC)_ , 2014, pp. 1085–1090.
  * [4] A. K. Gizzini, M. Chafii, A. Nimr, and G. Fettweis, “Deep Learning Based Channel Estimation Schemes for IEEE 802.11p Standard,” _IEEE Access_ , vol. 8, pp. 113 751–113 765, 2020.
  * [5] A. K. Gizzini, M. Chafii, A. Nimr, and G. Fettweis, “Joint TRFI and Deep Learning for Vehicular Channel Estimation,” in _2020 IEEE Globecom Workshops (GC Wkshps_ , 2020, pp. 1–6.
  * [6] J. Pan, H. Shan, R. Li, Y. Wu, W. Wua, and T. Q. S. Quek, “Channel Estimation Based on Deep Learning in Vehicle-to-everything Environments,” _IEEE Communications Letters_ , pp. 1–1, 2021.
  * [7] A. Abdelgader and L. Wu, “The Physical Layer of the IEEE 802.11 p WAVE Communication Standard: The Specifications and Challenges,” in _The Physical Layer of the IEEE 802.11 p WAVE Communication Standard: The Specifications and Challenges_ , vol. 2, 10 2014.
  * [8] K. Greff, R. K. Srivastava, J. Koutník, B. R. Steunebrink, and J. Schmidhuber, “LSTM: A Search Space Odyssey,” _IEEE Transactions on Neural Networks and Learning Systems_ , vol. 28, no. 10, pp. 2222–2232, 2017.
  * [9] A. K. Gizzini, M. Chafii, A. Nimr, and G. Fettweis, “Enhancing Least Square Channel Estimation Using Deep Learning,” in _2020 IEEE 91st Vehicular Technology Conference (VTC2020-Spring)_ , 2020, pp. 1–5.
  * [10] F. Pontes, G. Amorim, P. Balestrassi, A. Paiva, and J. Ferreira, “Design of Experiments and Focused Grid Search for Neural Network Parameter Optimization,” _Neurocomputing_ , vol. 186, pp. 22 – 34, 2016.
  * [11] G. Acosta-Marum and M. A. Ingram, “Six Time and Frequency Selective Empirical Channel Models for Vehicular Wireless LANs,” _IEEE Vehicular Technology Magazine_ , vol. 2, no. 4, pp. 4–11, 2007.
  * [12] G. Acosta-Marum, “Measurement, Modeling, and OFDM Synchronization for the Wideband Mobile-to-Mobile Channel,” _Ph.D. dissertation, Georgia Inst. Technol., Atlanta, GA_ , 2007.
  * [13] G. Orosi, “The Arithmetico-Geometric Sequence: an Application of Linear Algebra,” _International Journal of Mathematical Education in Science and Technology_ , vol. 47, no. 5, pp. 766–772, 2016.

  *[DL]: deep learning
  *[LSTM]: long short term memory
  *[TA]: temporal averaging
  *[DPA]: data-pilot aided
  *[STA]: spectral temporal averaging
  *[SNR]: signal-to-noise ratio
  *[TRFI]: time domain reliable test frequency domain interpolation
  *[DNN]: deep neural networks
  *[BER]: bit error rate
  *[NMSE]: normalized mean-squared error
  *[SoA]: state-of-the-art
  *[OFDM]: orthogonal frequency-division multiplexing
  *[AWGN]: additive white Gaussian noise
  *[LS]: least square
  *[TDL]: tapped delay line