%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%  FINAL VERSION SUBMITTED TO ELECTRONIC JOURNAL OF COMBINATORICS %%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\documentclass[12pt]{article}

\usepackage{epsfig}
\usepackage{amsthm,amsmath,amssymb}
\usepackage{e-jc}
\specs{P62}{20(1)}{2013}

\newcommand{\ZZ}{{\mathbb Z}}
\newcommand{\NN}{{\mathbb N}}
\newcommand{\CC}{{\mathbb C}}
\newcommand{\Ga}{\Gamma}
\newcommand{\G}{\Gamma}
\newcommand{\D}{\Delta}
\newcommand{\ov}{\overline}
\newcommand{\la}{\langle}
\newcommand{\ra}{\rangle}
\newcommand{\wtg}{\widetilde{\G}_1}
\newcommand{\wtd}{\tilde{d}}
\newcommand{\cay}{\hbox{Cay}}
\newcommand{\doi}[1]{\href{http://dx.doi.org/#1}{\texttt{doi:#1}}}


\theoremstyle{plain}
\newtheorem{theorem}{Theorem}
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{corollary}[theorem]{Corollary}
\newtheorem{proposition}[theorem]{Proposition}
\newtheorem{fact}[theorem]{Fact}
\newtheorem{observation}[theorem]{Observation}
\newtheorem{claim}[theorem]{Claim}

\theoremstyle{definition}
\newtheorem{definition}[theorem]{Definition}
\newtheorem{example}[theorem]{Example}
\newtheorem{conjecture}[theorem]{Conjecture}
\newtheorem{open}[theorem]{Open Problem}
\newtheorem{problem}[theorem]{Problem}
\newtheorem{question}[theorem]{Question}

\theoremstyle{remark}
\newtheorem{remark}[theorem]{Remark}
\newtheorem{note}[theorem]{Note}


\title{\bf Edge regular graph products}

\author{
Bo\v{s}tjan Frelih\\
\small UP IAM and UP FAMNIT \\[-0.8ex]
\small University of Primorska\\[-0.8ex]
\small Muzejski trg 2, 6000 Koper, Slovenia \\
\small \tt bostjan.frelih@upr.si\\
\and
\v Stefko Miklavi\v c\thanks{Supported in part by ``Agencija za raziskovalno dejavnost Republike Slovenije'',
                             research program P1-0285 and research project J1-4010.}\\
\small UP IAM and UP FAMNIT \\[-0.8ex]
\small University of Primorska\\[-0.8ex]
\small Muzejski trg 2, 6000 Koper, Slovenia \\
\small \tt stefko.miklavic@upr.si}

\date{\dateline{Oct 18, 2012}{Mar 11, 2013}{Mar 24, 2013}\\
\small Mathematics Subject Classifications: 05C76}


\begin{document}
\maketitle

\begin{abstract}
A regular nonempty graph $\G$ is called {\em edge regular}, whenever there exists a nonegative integer $\lambda_{\G}$,
such that any two adjacent vertices of $\G$ have precisely $\lambda_{\G}$ common neighbours. An edge regular graph $\G$
with at least one pair of vertices at distance $2$ is called
{\em amply regular}, whenever there exists a nonegative integer $\mu_{\G}$, such that any two vertices at distance $2$ have
precisely $\mu_{\G}$ common neighbours. In this paper we classify edge regular graphs, which can be obtained as a strong product, or a lexicographic product,
or a deleted lexicographic product, or a co-normal product of two graphs. As a corollary we determine which of these graphs are amply regular.
\bigskip\noindent \textbf{Keywords:} edge regular graph; strong product; lexicographic product; deleted lexicographic product; co-normal product
\end{abstract}


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\section{Introductory remarks}
\label{sec:intro}
\indent

In this paper, the interplay between the concept of graph products and the concept of regularity of graphs
is studied (see Section \ref{sec:pre} for formal definitions).
Both concepts recieved considerable attention in the mathematical literature.
The interplay between these two concepts was studied, for example, in \cite{Agg, Song, stevo},
where distance-regular graphs, which can be obtained as a cartesian, tensor or strong product, were classified.
In this paper we turn our attention to a larger class of graphs, namely edge regular and amply regular graphs.
A regular nonempty graph $\G$ is called {\em edge regular}, whenever there exists a nonegative integer $\lambda_{\G}$,
such that any two adjacent vertices of $\G$ have precisely $\lambda_{\G}$ common neighbours. An edge regular graph $\G$
with at least one pair of vertices at distance $2$ is called
{\em amply regular}, whenever there exists a nonegative integer $\mu_{\G}$, such that any two vertices at distance $2$ have
precisely $\mu_{\G}$ common neighbours. Note that distance-regular graphs are also amply regular (provided that their diameter is at least 2).

It is quite easy to see, that the cartesian or tensor product is edge regular if and only if both factors are.
Therefore, in this paper we turn our attention to other graph products.
We classify edge regular graphs, which can be obtained as a
strong product, a lexicographic product, a deleted lexicographic product or a co-normal product of two graphs.
As a corollary we determine which of these graphs are amply regular.
%We would like to mention, that in \cite{stevo}, the properties of the above number $\mu$ were used for the classification of
%distance-regular graphs, which can be obtained as a strong product.

After some preliminaries in Section \ref{sec:pre}, we consider the case of strong product in Section \ref{sec:str},
the case of lexicographic product in Section \ref{sec:lexpro},
the case of deleted lexicographic product in Section \ref{sec:dellexpro}, and the case of
co-normal product in Section \ref{sec:conopro}.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\section{Preliminaries}
\label{sec:pre}
\indent

In this section we review basic definitions and facts about edge regular
graphs and graph products that we will need latter.
Throughout this paper all graphs are assumed to be finite, undirected and without loops or multiple edges.
For a graph $\G$ we let $V(\G)$, $E(\G)$ and $\partial_{\G}$ denote the vertex set, the edge set
and the path length distance function, respectively.
The {\em diameter} $\max \{\partial_{\G}(x,y) | x,y \in V(\G)\}$ of $\G$ will be denoted by $D_{\G}$.

For a positive integer $n$ we denote by $K_n$ ($E_n$, respectively) the complete (empty, respectively)
graph on $n$ vertices. We will denote a disjoint union of $t$ copies of $K_n$ by $t\times K_{n}$.
A complete multipartite graph with $t$ partite sets each with $n$ vertices (that is, the complement of $t\times K_{n}$)
will be denoted by $K_{t\times n}$.

For a vertex $x$ of a graph $\G$, let $N_{\G}(x)$ denote a set of vertices adjacent to $x$.
If the number $|N_{\G}(x)|$ is independent of the choice of a vertex $x\in \G$, then we call this number the valency of $\G$ and we denote it by $k_{\G}$.
In this case we say that $\G$ is {\em regular with valency} $k_{\G}$. Further degrees of regularity of $\G$, namely edge regularity and amply regularity,
can be defined as follows. Assume $\G$ is nonempty.
If $|N_{\G}(x) \cap N_{\G}(y)|$ is constant for every pair of adjacent vertices $x,y\in V(\G)$, then we denote this common value
with $\lambda_{\G}$ and we say that the parameter $\lambda_{\G}$ {\em exists} in $\G$.
Assume now that there is at least one pair of vertices of $\G$ which are at distance $2$.
If $|N_{\G}(x) \cap N_{\G}(y)|$ is constant for every pair of vertices $x,y\in V(\G)$ with $\partial_{\G}(x,y)=2$, then we denote this common value
with $\mu_{\G}$ and we say that the parameter $\mu_{\G}$ {\em exists} in $\G$.
A regular nonempty graph $\G$ is called {\em edge regular} if the parameter $\lambda_{\G}$ exists in $\G$.
An edge regular graph $\G$ is called {\em amply regular} if it contains a pair of vertices at distance $2$, and if the parameter $\mu_{\G}$ exists in $\G$.
The following are well-known facts (see, for example, \cite[page 3]{BCN}).

\begin{proposition}
\label{prop:ar}
\begin{itemize}
\item[{\rm (i)}]
Assume that $\G$ is edge regular graph with $k_{\G} = \lambda_{\G} + 1$. Then $\G$ is $t \times K_n$ for some $t \ge 1$ and $n \ge 2$.
\item[{\rm (ii)}]
Assume that $\G$ is a regular graph, such that any two nonadjacen vertices have no common neighbours.
Then $\G$ is $t \times K_{n}$ for some positive integers $t,n$.
\item[{\rm (iii)}]
Assume that $\G$ is a regular graph, such that any two nonadjacen vertices have exactly $k_{\G}$ common neighbours.
Then $\G$ is $K_{t \times n}$ for some positive integers $t,n$.
\end{itemize}
\end{proposition}

We now define a strong product, a lexicographic product, a deleted lexicographic product, and a co-normal product of
graphs $G$ and $H$. In all four cases, the vertex set of the product is $V(G) \times V(H)$.
Pick vertices $(g_1,h_1)$ and $(g_2, h_2)$ in $V(G) \times V(H)$.
In the {\em strong product} of $G$ and $H$, denoted by $G \boxtimes H$,
$(g_1,h_1)$ and $(g_2, h_2)$ are adjacent if and only if $g_1=g_2$ and $h_1, h_2$ are adjacent in $H$,
or $h_1=h_2$ and $g_1, g_2$ are adjacent in $G$, or $g_1, g_2$ are adjacent in $G$ and $h_1, h_2$ are adjacent in $H$.
Note that strong product is commutative.

In the {\em lexicographic product} of $G$ and $H$, denoted by $G[H]$,
$(g_1,h_1)$ and $(g_2, h_2)$ are adjacent if and only if $g_1=g_2$ and $h_1, h_2$ are adjacent in $H$,
or $g_1, g_2$ are adjacent in $G$.

Let $n = |V(H)|$.
In the {\em deleted lexicographic product} of $G$ and $H$, denoted by $G[H]-nG$,
$(g_1,h_1)$ and $(g_2, h_2)$ are adjacent if and only if $g_1=g_2$ and $h_1, h_2$ are adjacent in $H$,
or $g_1, g_2$ are adjacent in $G$ and $h_1 \ne h_2$.

In the {\em co-normal product} of $G$ and $H$,
$(g_1,h_1)$ and $(g_2, h_2)$ are adjacent if and only if $g_1, g_2$ are adjacent in $G$,
or $h_1, h_2$ are adjacent in $H$. Note that co-normal product is commutative.
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\section{Strong product}
\label{sec:str}
\indent

Throughout this section let $G$ and $H$ be graphs and let $\Gamma = G \boxtimes H$ be the strong product of $G$ and $H$.
We will classify graphs $G$ and $H$ for which $\G$ is connected edge regular graph.
Note that $\Gamma$ is connected if and only if $G$ and $H$ are connected.
For the rest of this section we will assume that $\Gamma$ is connected (and thus also $G$ and $H$ are connected).
To avoid trivialities we also assume that $|V(G)| \ge 2$ and $|V(H)| \ge 2$.

\begin{lemma}
\label{lem:reg_str}
$\G$ is regular if and only if both $G$ and $H$ are regular.
In this case the valency $k_{\G}=k_G + k_H + k_G k_H$.
\end{lemma}
%
\begin{proof} Assume $\G$ is regular graph of valency $k_{\G}$. For an arbitrary vertex $g \in V(G)$ take vertices $(g, h_1), (g, h_2) \in V(\G)$.
By the definition of $\G$ we have
$$
  k_{\G}=|N_{\G}((g,h_1))|= |N_G(g)| + |N_H(h_1)| + |N_G(g)||N_H(h_1)|,
$$
and
$$
  k_{\G}=|N_{\G}((g,h_2))|= |N_G(g)| + |N_H(h_2)| + |N_G(g)||N_H(h_2)|.
$$
It follows that $|N_H(h_1)|=|N_H(h_2)|$, so $H$ is regular.
The proof that $G$ is regular is analogous.

Conversely, if both $G$ and $H$ are regular, then $\G$ is obviously a regular graph, as
$$
|N_{\G}((g, h))|= |N_G(g)| + |N_H(h)| + |N_G(g)||N_H(h)| = k_G + k_H + k_G k_H
$$
for every $(g, h) \in V(\G)$. \end{proof}

\begin{lemma}
\label{lem1_str}
Assume that $\G$ is edge regular. Then $G$ and $H$ are also edge regular.
\end{lemma}
%
\begin{proof}
Recall that $G$ and $H$ are regular by Lemma \ref{lem:reg_str}.
Pick adjacent vertices $g_1, g_2$ of $G$. For an arbitrary vertex $h \in V(H)$ consider
$u = (g_1, h), v = (g_2, h) \in V(\G)$. Note that, by the definition of $\G$,
$\partial_{\G}(u, v)=1$. We now count the number of common neighbours of $u$ and $v$. Note that we have
\begin{eqnarray*}
  N_{\G}(u) \cap N_{\G}(v) &=& \{ (g,h) \mid g \in N_G(g_1) \cap N_G(g_2) \} \cup \\
                           & & \{ (g_1,h_1), (g_2,h_2) \mid h_1, h_2 \in N_H(h) \} \cup \\
                           & & \{ (g_3, h_3) \mid g_3 \in N_{G}(g_1) \cap N_{G}(g_2), h_3 \in N_H(h) \}.
\end{eqnarray*}
Therefore
\begin{equation}
\label{lam_str}
  |N_{\G}(u) \cap N_{\G}(v)| = |N_G(g_1) \cap N_G(g_2)| + 2 k_H + k_H |N_G(g_1) \cap N_G(g_2)|.
\end{equation}
Since $\lambda_{\G} = |N_{\G}(u) \cap N_{\G}(v)|$, it follows that
$$
  |N_G(g_1) \cap N_G(g_2)| = \frac{\lambda_{\G} - 2 k_H}{k_H+1}.
$$
Therefore, the number of common neighbours of two adjacent vertices of $G$ is independent of the choice of these vertices,
and thus $\lambda_G$ exists. The commutativity of the strong product implies the proof for $H$. \end{proof}

\begin{corollary}
\label{lambda_str}
If $\G$ is edge regular, then
$$
  \lambda_{\G} = 2 k_H + (k_H+1) \lambda_G = 2 k_G + (k_G+1) \lambda_H = \lambda_H \lambda_G + 2\lambda_G + 2\lambda_H + 2.
$$
\end{corollary}
%
\begin{proof}
Observe thet by Lemma \ref{lem:reg_str} and Lemma \ref{lem1_str}, $G$ and $H$ are both edge regular, so
$\lambda_G$ and $\lambda_H$ exist. The first equality now follows
from \eqref{lam_str}. The second equality is obtained by reversing the roles of $G$ and $H$.
To prove the third equality, pick adjacent vertices $g_1, g_2$ of $G$ and adjacent vertices $h_1, h_2$ of $H$.
Consider vertices $u = (g_1, h_1), v = (g_2, h_2) \in V(\G)$. Note that, by the definition of $\G$,
$\partial_{\G}(u, v)=1$. We now count the number of common neighbours of $u$ and $v$.

Two of them are $(g_1, h_2)$ and $(g_2, h_1)$. There is $2 \lambda_G$ common neighbours whose second coordinate is
$h_1$ (and first coordinate is not $g_2$) or $h_2$ (and first coordinate is not $g_1$),
namely vertices of the form $(x,h_1)$ and $(x,h_2)$, where $x \in N_G(g_1) \cap N_G(g_2)$.
Similarly, there is $2 \lambda_H$ common neighbours whose first coordinate is
$g_1$ (and second coordinate is not $h_2$) or $g_2$ (and second coordinate is not $h_1$).
Finaly, there is $\lambda_G \lambda_H$ common neighbours whose first coordinate is not $g_1$ or $g_2$,
and whose second coordinate is not $h_1$ or $h_2$. These vertices are vertices of the form
$(x,y)$, where $x \in  N_G(g_1) \cap N_G(g_2)$ and $y \in  N_H(h_1) \cap N_H(h_2)$.
The result follows.\end{proof}

\begin{theorem}
\label{str:main}
$\Gamma = G \boxtimes H$ is edge regular if and only if
$G = K_n$ and $H = K_m$ for some $n,m \ge 2$.
\end{theorem}
%
\begin{proof}
Assume that $\Gamma$ is edge regular. By Corollary \ref{lambda_str} we have
$2 k_G + (k_G + 1) \lambda_H = \lambda_H \lambda_G + 2\lambda_G + 2\lambda_H + 2$,
implying that
$$
  (k_G - \lambda_G) (\lambda_H + 2) = \lambda_H + 2.
$$
It follows that $k_G = \lambda_G + 1$. By Proposition \ref{prop:ar}(i) and since $G$ is connected,
$G = K_n$ for some $n \ge 2$. Similarly we prove that $H = K_m$ for some $m \ge 2$.

Assume now that $G = K_n$ and $H = K_m$ for some $n,m \ge 2$. Note that in this case
$\G$ is $K_{mn}$, which is clearly edge regular. \end{proof}

\begin{corollary}
$\Gamma = G \boxtimes H$ is never amply regular.
\end{corollary}
%
\begin{proof}
Assume that $\G$ is amply regular. Since in this case $\G$ is also edge regular,
$G=K_n$ and $H=K_m$ for some $n,m \ge 2$ by Theorem \ref{str:main}. But then $\G$ is
$K_{mn}$, which is not amply regular (since no two vertices are at distance 2), a contradiction. \end{proof}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\section{Lexicographic product}
\label{sec:lexpro}
\indent

Throughout this section let $G$ and $H$ be graphs and let $\Gamma = G[H]$ be the lexicographic product of $G$ and $H$.
We will classify graphs $G$ and $H$ for which $\G$ is connected edge regular graph.
Note that $\Gamma$ is connected if and only if $G$ is connected.
For the rest of this section we will assume that $\Gamma$ is connected (and thus $G$ is also connected).
To avoid trivialities we also assume that $|V(G)| \ge 2$ and $|V(H)| \ge 2$.


\begin{lemma}
\label{lem:reg}
$\G$ is regular if and only if both $G$ and $H$ are regular.
In this case the valency $k_{\G}=k_H + k_G|V(H)|$.
\end{lemma}
%
\begin{proof}
Assume $\G$ is regular graph of valency $k_{\G}$. For an arbitrary vertex $g \in V(G)$ take vertices $(g, h_1), (g, h_2) \in V(\G)$.
By the definition of $\G$ we have
$$
  k_{\G}=|N_{\G}((g,h_1))|= |N_H(h_1)| + |N_G(g)||V(H)|,
$$
and
$$
  k_{\G}=|N_{\G}((g,h_2))|= |N_H(h_2)| + |N_G(g)||V(H)|.
$$
It follows that $|N_H(h_1)|=|N_H(h_2)|$, so $H$ is regular.
Now we also have that
$$
  k_{\G}=|N_{\G}((g,h_1))|= |N_G(g)||V(H)| + k_H.
$$
It follows that $|N_G(g)| = (k_{\G} - k_H)/|V(H)|$, so $G$ is regular.

Conversely, if both $G$ and $H$ are regular, then $\G$ is obviously regular, as
$$
|N_{\G}((g, h))|= |N_H(h)| + |N_G(g)||V(H)| = k_H + k_G|V(H)|
$$
for every $(g, h) \in V(\G)$. \end{proof}

\begin{lemma}
\label{lem1}
Assume that $\G$ is edge regular. Then the following {\rm (i), (ii)} hold.
\begin{itemize}
\item[{\rm (i)}]
$G$ is edge regular.
\item[{\rm (ii)}]
Either $H=E_m$ for some positive integer $m$, or $H$ is edge regular.
\end{itemize}
\end{lemma}
%
\begin{proof}
Recall that $G$ and $H$ are regular by Lemma \ref{lem:reg}.

\noindent
(i) Pick a pair of adjacent vertices $g_1, g_2$ of $G$. For an arbitrary vertex $h \in V(H)$ consider
$u = (g_1, h), v = (g_2, h) \in V(\G)$. Note that, by the definition of $\G$,
$\partial_{\G}(u, v)=1$.
We now count the number of common neighbours of $u$ and $v$. Observe that
\begin{eqnarray*}
  N_{\G}(u) \cap N_{\G}(v) &=& \{(g_1,h'), (g_2, h') \mid h' \in N_H(h) \} \cup \\
                           & & \{(g',h') \mid g' \in N_G(g_1) \cap N_G(g_2),h'\in V(H) \}.
\end{eqnarray*}
Therefore
\begin{equation}
\label{lam}
  |N_{\G}(u) \cap N_{\G}(v)| = 2|N_H(h)| + |N_G(g_1) \cap N_G(g_2)||V(H)|.
\end{equation}
Since $\lambda_{\G} = |N_{\G}(u) \cap N_{\G}(v)|$, it follows that
$$
  |N_G(g_1) \cap N_G(g_2)| = \frac{\lambda_{\G} - 2k_H}{|V(H)|}.
$$
Therefore, the number of common neighbours of two adjacent vertices of $G$ is independent of the choice of these vertices,
and thus $\lambda_G$ exists. The result follows.

\medskip \noindent
(ii) Assume that $H$ is nonempty.
Pick a pair of adjacent vertices $h_1, h_2$ of $H$.
For an arbitrary vertex $g \in V(G)$ consider vertices $u = (g, h_1), v = (g, h_2) \in V(\Gamma)$.
Note that, by the definition of $\G$, $\partial_{\G}(u, v)=1$.
We now count the number of common neighbours of $u$ and $v$ in $\G$. Observe that
$$
  N_{\G}(u) \cap N_{\G}(v) = \{ (g,h) \mid h \in N_H(h_1) \cap N_H(h_2) \} \cup \{ (g', h') \mid g' \in N_G(g),h' \in V(H) \}.
$$
Therefore
\begin{equation}
\label{la}
|N_{\G}(u) \cap N_{\G}(v)| = |N_H(h_1) \cap N_H(h_2)| + |N_G(g)||V(H)|.
\end{equation}
Since $\lambda_{\G} = |N_{\G}(u) \cap N_{\G}(v)|$, it follows that
$$
  |N_H(h_1) \cap N_H(h_2)| = \lambda_{\G} - k_G|V(H)|.
$$
Therefore, the number of common neighbours of two adjacent vertices in $H$ is independent of the choice of these two vertices,
and thus $\lambda_H$ exists. The result follows. \end{proof}

\begin{corollary}
\label{lambda}
If $\G$ is edge regular and $H$ is nonempty, then
$$
  \lambda_{\G} = 2k_H + \lambda_G |V(H)| = k_G|V(H)| + \lambda_H.
$$
\end{corollary}
%
\begin{proof}
Observe that by Lemma \ref{lem:reg}, $G$ and $H$ are both regular.
By Lemma \ref{lem1}, $\lambda_G$ and $\lambda_H$ exist. The result now follows
from equalities \eqref{lam} and \eqref{la}. \end{proof}

\begin{theorem}
\label{lex:main}
$\Gamma = G[H]$ is edge regular if and only if one of the following holds:
\begin{itemize}
\item[{\rm (i)}]
$H=E_m$ for some $m \geq 2$ and $G$ is edge regular.
\item[{\rm (ii)}]
$G=K_n$ and $H = K_{t \times m}$ for some $n, t \geq 2$ and $m \ge 1$.
\end{itemize}
\end{theorem}
%
\begin{proof}
Assume that $\Gamma$ is edge regular. By Lemma \ref{lem:reg} and Lemma \ref{lem1}, $G$ is edge regular
and $H$ is regular. If $H$ is an empty graph $E_m$ for some $m \ge 2$, then we are done.
Assume now that $H$ is nonempty. By Corollary \ref{lambda},
$k_G|V(H)| + \lambda_H = 2k_H + \lambda_G |V(H)|$. It follows that
$$
  |V(H)| (k_G - \lambda_G) = 2 k_H - \lambda_H.
$$
Since obviously $\lambda_G < k_G$ and $k_H < |V(H)|$ we have that $k_G - \lambda_G = 1$ and that $2k_H - \lambda_H = |V(H)|$.
By Proposition \ref{prop:ar}(i) and since $G$ is connected, $G$ is a complete graph.
Furthermore, note that in the complement of $H$, every two nonadjacent vertices have exactly $|V(H)|-2k_H+\lambda_H = 0$
common neighbours. Since the complement of $H$ is also regular, Proposition \ref{prop:ar}(ii) implies that the complement of $H$
is isomorphic to $t \times K_m$ for some $t, m \ge 1$.
It follows that $H = K_{t \times m}$ for some $t, m \ge 1$. Since $H$ is nonempty, we also have that $t \ge 2$.

Assume now that (i) or (ii) of the Theorem holds. Then $\G$ is regular by Lemma \ref{lem:reg}.
It is now an easy exercise to show that if (i) holds, then $\lambda_{\G} = \lambda_G |V(H)|$,
and that if (ii) holds, then $\G = K_{tn \times m}$, which is clearly edge regular with $\lambda_{\G} = tnm - 2m$.\end{proof}

\begin{corollary}
$\Gamma = G[H]$ is amply regular if and only if one of the following holds:
\begin{itemize}
\item[{\rm (i)}]
$H=E_m$ for some $m \geq 2$ and $G = K_{t \times n}$ for some $t \ge 2$, $n \ge 1$.
\item[{\rm (ii)}]
$G=K_n$ and $H = K_{t \times m}$ for some $n, m, t \geq 2$.
\end{itemize}
\end{corollary}
%
\begin{proof}
Assume that $\G$ is amply regular.
Let first consider case (i) of Theorem \ref{lex:main}, that is the case when $H=E_m$ for some $m \geq 2$ and $G$ is edge regular.
If $G$ is a complete graph, then (i) above holds. Therefore assume that $G$ is not a complete graph.
Pick $g \in V(G)$ and $h_1, h_2 \in V(H)$.
Abbreviate $u=(g,h_1)$, $v=(g,h_2)$ and note that $\partial_{\G}(u,v) = 2$.
It is also clear that
$$
  |N_{\G}(u) \cap N_{\G}(v)| = k_G |V(H)|.
$$
Next pick arbitrary $g_1, g_2 \in V(G)$ with $\partial_G(g_1, g_2)=2$, and arbitrary $h \in V(H)$.
Abbreviate $w=(g_1,h)$, $z=(g_2,h)$ and note that $\partial_{\G}(w,z) = 2$.
In this case we have
$$
  |N_{\G}(w) \cap N_{\G}(z)| = |N_G(g_1) \cap N_G(g_2)||V(H)|.
$$
If $\G$ is amply regular, then we clearly have
$$
  k_G |V(H)| = |N_G(g_1) \cap N_G(g_2)||V(H)|,
$$
which implies $k_G = |N_G(g_1) \cap N_G(g_2)|$. Therefore, $\mu_G$ exists and is equal to $k_G$.
Note that this implies that for $x,y \in V(G)$ we have $\partial_G(x,y) \le 2$ (since in $G$ there is no induced path of length 3),
and so by Proposition \ref{prop:ar}(iii), $G$ is $K_{t \times n}$ for some positive integers $t,n$.
As $G$ is connected, we clearly have that $t \ge 2$.

\medskip \noindent
Let us now consider case (ii) of Theorem \ref{lex:main}, that is
$G=K_n$ and $H = K_{t \times m}$ for some $n, t \geq 2$ and $m \ge 1$.
Since $\G$ is not a complete graph, we have $m \ge 2$.

\medskip \noindent
Conversely, if (i) above holds, then $\G = K_{t \times mn}$, and if (ii) above holds, then
$\G=K_{tn \times m}$. In both cases $\G$ is an amply graph. \end{proof}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\section{Deleted lexicographic product}
\label{sec:dellexpro}
\indent

Throughout this section let $G$ and $H$ be graphs and let $\G = G[H]-nG$ be the deleted lexicographic product of $G$ and $H$,
where $n=|V(H)|$. We will classify graphs $G$ and $H$ for which $\G$ is connected edge regular graph.
To avoid trivialities we assume that $|V(G)| \ge 2$ and $|V(H)| \ge 2$.

\begin{lemma}
\label{lem:condel}
\begin{itemize}
\item[{\rm (i)}]
If $H=E_2$, then $\G$ is connected if and only if $G$ is connected and nonbipartite.
\item[{\rm (ii)}]
If $H\neq E_2$, then $\G$ is connected if and only if $G$ is connected.
\end{itemize}
\end{lemma}
%
\begin{proof}
(i) Note that, if $H=E_2$, then $\G$ is isomorphic to the tensor product $G \times K_2$ (for the definition of tensor product see \cite[Section 5.3]{ImKl}).
The result now follows from \cite[Theorem 5.29]{ImKl}.

\medskip \noindent
(ii) Assume now that $H\neq E_2$. If $G$ is not connected, then $\G$ is obviously not connected. Conversely, assume that $G$ is connected.
Pick two arbitrary vertices $(g_1, h_1), (g_2, h_2)$ of $\G$. We claim that there exist a path in $\G$ between $(g_1, h_1), (g_2, h_2)$.
Since $G$ is connected, there exists a path between $g_1$ and $g_2$ in $G$.
It follows that there exists a path between $(g_1, h_1)$ and $(g_2, h)$ for some vertex $h\in H$.
If $h=h_2$ or if $h, h_2$ are adjacent in $H$, then we are done.
Now if $h \ne h_2$ and $h, h_2$ are not adjacent in $H$, then $H$ is not $K_2$.
Since $H$ is also not $E_2$, this shows that $|V(H)| \ge 3$.
Now pick a neighbour $g$ of $g_2$ in $G$ and $h' \in V(H) \setminus \{h_2,h\}$.
Note that $(g,h')$ is a common neighbour of $(g_2,h_2)$ and $(g_2,h)$ in $\G$.
This verifies the claim and thus $\G$ is connected. \end{proof}

\begin{lemma}
\label{lem:regdel}
$\G$ is regular if and only if both $H$ and $G$ are regular. In this case the valency $k_{\G}=k_H + k_G(|V(H)|-1)$.
\end{lemma}
%
\begin{proof}
Assume $\G$ is regular graph of valency $k_{\G}$. For an arbitrary vertex $g\in V(G)$ take vertices $(g, h_1), (g, h_2)\in V(\G)$. By the definition of $\G$ we have
$$
k_{\G}=|N_{\G}((g, h_1))|= |N_H(h_1)| + |N_G(g)|(|V(H)|-1)
$$
and
$$
k_{\G}=|N_{\G}((g, h_2))|= |N_H(h_2)| + |N_G(g)|(|V(H)|-1).
$$
It follows that $|N_H(h_1)|=|N_H(h_2)|$, so $H$ is regular.
We now also have
$$
  k_{\G}=|N_{\G}((g,h_1))| = k_H + |N_G(g)|(|V(H)|-1).
$$
It follows that $|N_G(g)| = (k_{\G} - k_H)/(|V(H)|-1)$, so $G$ is regular.

Conversely, if both $G$ and $H$ are regular, then $\G$ is obviously a regular graph, as
$$
|N_{\G}((g, h))|= |N_H(h)| + |N_G(g)|(|V(H)|-1) = k_H + k_G(|V(H)|-1)
$$
for every $(g, h) \in V(\G)$. \end{proof}

For the rest of this section we will assume that $\Gamma$ is connected (and thus $G$ is also connected).

\subsection{The case $|V(H)|=2$}

Recall that $\G = G[H]-nG$ is the deleted lexicographic product of $G$ and $H$,
where $n=|V(H)|$. In this subsection we consider the case $|V(H)|=2$.

\begin{theorem}
\label{H2del}
Assume that $|V(H)|=2$. Then $\G$ is edge regular if and only if one of the the following {\rm (i), (ii)} holds.
\begin{itemize}
\item[{\rm (i)}]
$H=E_2$ and $G$ is regular and nonbipartite.
\item[{\rm (ii)}]
$H=K_2$ and $G$ is regular.
\end{itemize}
\end{theorem}
%
\begin{proof} Observe that since $|V(H)|=2$, $\G$ is bipartite. Therefore, if $\G$ is edge regular, then $\lambda_{\G} = 0$.

Assume $\G$ is edge regular. In particular, $\G$ is regular and connected.
If $H=E_2$, then $G$ is nonbipartite by Lemma \ref{lem:condel}(i) and regular by Lemma \ref{lem:regdel}. If $H=K_2$, then $G$ is regular by Lemma \ref{lem:regdel}.

Conversely, if (i) or (ii) holds, then $\G$ is regular by Lemma \ref{lem:regdel}. Since $\G$ is bipartite, we have $\lambda_{\G} = 0$. \end{proof}

Let us now determine in which cases of Theorem \ref{H2del} the graph $\G$ is amply regular.
Assume first that $H=E_2$. As already mentioned in the proof of Lemma \ref{lem:condel},
in this case $\G$ is isomorphic to the tensor product $G \times K_2$, and it is also called a
{\em bipartite double} of $G$, see \cite[Section 1.11]{BCN}. Recall also that $\lambda_{\G} = 0$.
By \cite[Theorem 1.11.1 (ii)]{BCN}, $\G$ is amply regular if and only if $G$ is regular nonbipartite graph,
in which any two distinct vertices have either 0 or $\mu_{\G}$ common neighbours.
Let us now turn our attention to the case when $H=K_2$.

\begin{lemma}
\label{H2del-complete}
Assume that $H=K_2$ and that $\G$ is amply regular. Then the following {\rm (i)-(iii)} hold.
\begin{itemize}
\item[{\rm (i)}]
$G$ is edge regular.
\item[{\rm (ii)}]
Either $G$ is a complete graph or $G$ is amply regular.
\item[{\rm (iii)}]
If $G$ is not a complete graph, then $\lambda_G + 2 = \mu_G = \mu_{\G}$.
\end{itemize}
\end{lemma}
%
\begin{proof}
Set $V(H)=\{h_1,h_2\}$.

\smallskip \noindent

(i) Pick adjacent vertices $g_1, g_2$ of $G$.
Consider vertices $u=(g_1,h_1)$ and $v=(g_2,h_1)$ of $\G$. Note that $\partial_{\G}(u,v)=2$.
Let us count the number of common neighbours of $u$ and $v$. Note that $z=(g,h)$ is a common neighbour
of $u$ and $v$ if and only if $h=h_2$, and either $g \in \{g_1,g_2\}$ or $g$ is a common neighbor of $g_1, g_2$ in $G$.
Therefore,
\begin{equation}
\label{H2del:eq1}
  \mu_{\G} = |N_{\G}(u) \cap N_{\G}(v)| = 2 + |N_G(g_1) \cap N_G(g_2)|.
\end{equation}
It follows that the number of common neighbours of two adjacent vertices in $G$ is independent of the choice of these two vertices,
and thus $\lambda_G$ exists.

\smallskip \noindent
(ii) Assume that $G$ is not a complete graph, and pick vertices $g_1, g_2$ of $G$ such that $\partial_G(g_1,g_2)=2$.
Consider vertices $u=(g_1,h_1)$ and $v=(g_2,h_1)$ of $\G$. Note that $\partial_{\G}(u,v)=2$.
Let us count the number of common neighbours of $u$ and $v$. Note that $z=(g,h)$ is a common neighbour
of $u$ and $v$ if and only if $h=h_2$ and $g$ is a common neighbor of $g_1, g_2$ in $G$.
Therefore,
\begin{equation}
\label{H2del:eq2}
  \mu_{\G} = |N_{\G}(u) \cap N_{\G}(v)| = |N_G(g_1) \cap N_G(g_2)|.
\end{equation}
It follows that the number of common neighbours of two vertices of $G$ which are at distance 2 is independent of the choice of these two vertices,
and thus $\mu_G$ exists.

\smallskip \noindent
(iii) This follows from \eqref{H2del:eq1} and \eqref{H2del:eq2}. \end{proof}

\begin{theorem}
\label{thm:H2del-complete}
Assume that $H=K_2$. Then $\G = G[H]-nG$ is amply regular if and only if either $G$ is a complete graph,
or $G$ is an amply regular graph with $\lambda_G + 2 = \mu_G$.
\end{theorem}
%
\begin{proof}
Assume first that $\G$ is an amply regular graph and that $G$ is not a complete graph.
Then $G$ is amply regular with $\lambda_G + 2 = \mu_G$ by Lemma \ref{H2del-complete}(iii).

\smallskip \noindent
Conversly, assume first that $G$ is a complete graph $K_m$.
Then $\G$ is isomorphic to the complete bipartite graph $K_{m,m}$,
which is clearly amply regular.
Assume now that $G$ is an amply regular graph with $\lambda_G + 2 = \mu_G$.
Since $\G$ is bipartite, $\G$ is edge regular with $\lambda_{\G}=0$.
Now pick vertices $u=(g_1,h_1),v=(g_2,h_2)$ of $\G$ such that $\partial_{\G}(u,v)=2$. Note that we have two possibilities:
\begin{itemize}
\item[(i)]
$h_1=h_2$ and $g_1, g_2$ are adjacent in $G$. In this case $u$ and $v$ have $2+\lambda_G$ common neighbours.
\item[(ii)]
$h_1=h_2$ and $\partial_G(g_1,g_2)=2$. In this case $u$ and $v$ have $\mu_G$ common neighbours.
\end{itemize}
As $\lambda_G+2=\mu_G$, the number of common neighbours of $u$ and $v$ is independent on the choice of these two vertices.
This shows that $\mu_{\G}$ exists and so $\G$ is amply regular. \end{proof}

\subsection{Case $|V(H)| \ge 3$}

Let us now turn our attention to the case $|V(H)| \ge 3$.

\begin{lemma}
\label{Hdel}
If $\G$ is edge regular, then either $H=E_n$ or $H=K_n$ for some $n \ge 3$.
\end{lemma}
%
\begin{proof}
Assume that $\G$ is edge regular and that $H \ne E_n, H \ne K_n$.
Then there exist (distinct) vertices $h_1, h_2, h_3 \in V(H)$, such that $\partial_H(h_1, h_2)=1$ and
$\partial_H(h_1, h_3) \neq 1$. Pick adjacent vertices $g_1, g_2 \in V(G)$ and consider vertices $u=(g_1,h_1)$, $v=(g_2,h_2)$ and $z=(g_2,h_3)\in V(\G)$. Note that, by the definition of $\G$, $\partial_{\G}(u, v)=1$ and $\partial_{\G}(u, z)=1$. Now count the number of common neighbours of adjacent vertices $u,v$ and $u,z$ of $\G$.
Observe that we have
\begin{eqnarray*}
  N_{\G}(u) \cap N_{\G}(v) &=& \{ (g_1,h) \mid h \in N_H(h_1) \setminus \{h_2\}\} \cup \\
                           & & \{ (g_2,h) \mid h \in N_H(h_2) \setminus \{h_1\}\} \cup \\
                           & & \{ (g,h) \mid g \in N_G(g_1) \cap N_G(g_2), h \in V(H) \setminus \{h_1, h_2\} \}
\end{eqnarray*}
and
\begin{eqnarray*}
  N_{\G}(u) \cap N_{\G}(z) &=& \{ (g_1,h) \mid h \in N_H(h_1)\} \cup \\
                           & & \{ (g_2,h) \mid h \in N_H(h_3)\} \cup \\
                           & & \{ (g,h) \mid g \in N_G(g_1) \cap N_G(g_2), h \in V(H) \setminus \{h_1, h_3\} \}.
\end{eqnarray*}
Therefore
$$
  |N_{\G}(u) \cap N_{\G}(v)| = 2(k_H-1) + |N_G(g_1) \cap N_G(g_2)|(|V(H)|-2),
$$
and
$$
  |N_{\G}(u) \cap N_{\G}(z)| = 2k_H + |N_G(g_1) \cap N_G(g_2)|(|V(H)|-2).
$$
Obviously
$$|N_{\G}(u) \cap N_{\G}(v)|\neq |N_{\G}(w) \cap N_{\G}(z)|,$$
a contradiction with assumption that $\lambda_{\G}$ exists. It follows that either $H=E_n$ or $H=K_n$. \end{proof}

\begin{lemma}
\label{lem:lamdel}
Assume that $\G$ is edge regular. Then $G$ is edge regular.
\end{lemma}
%
\begin{proof}
Recall that $G$ is regular by Lemma \ref{lem:regdel}. Recall also that either $H=E_n$ or $H=K_n$ by Lemma \ref{Hdel}, where $n=|V(H)|$.
Pick a pair of adjacent vertices $g_1, g_2$ of $G$. For arbitrary vertices $h_1, h_2 \in V(H) \; (h_1 \ne h_2)$ consider
$u = (g_1, h_1), v = (g_2, h_2) \in V(\G)$. Note that, by the definition of $\G$,
$\partial_{\G}(u, v)=1$.
We now count the number of common neighbours of $u$ and $v$. Observe that
\begin{eqnarray*}
  N_{\G}(u) \cap N_{\G}(v) &=& \{ (g_1,h) \mid h \in N_H(h_1) \setminus \{h_2\}\} \cup \\
                           & & \{ (g_2,h) \mid h \in N_H(h_2) \setminus \{h_1\}\} \cup \\
                           & & \{ (g,h) \mid g \in N_G(g_1) \cap N_G(g_2), h \in V(H) \setminus \{h_1, h_2\} \}.
\end{eqnarray*}
Therefore
\begin{equation}
\label{lamdel2}
  |N_{\G}(u) \cap N_{\G}(v)| = 2t + |N_G(g_1) \cap N_G(g_2)|(n-2),
\end{equation}
where $t=0$ if $H=E_n$ and $t=n-2$ if $H=K_n$.
Since $\lambda_{\G} = |N_{\G}(u) \cap N_{\G}(v)|$, it follows that
$$
  |N_G(g_1) \cap N_G(g_2)| = \frac{\lambda_{\G}-2t}{n-2}.
$$
Therefore, the number of common neighbours of two adjacent vertices of $G$ is independent of the choice of these vertices,
and thus $\lambda_G$ exists. \end{proof}

\begin{corollary}
\label{dellambda}
If $\G$ is edge regular and $H=K_n$ for some $n \geq 3$, then
$$
  \lambda_{\G} = (\lambda_G + 2)(n-2) = (k_G + 1)(n-2).
$$
\end{corollary}
%
\begin{proof}
Observe that $\lambda_{\G} = (\lambda_G + 2)(n-2)$ follows from \eqref{lamdel2}.
To prove that $\lambda_{\G} = (k_G + 1)(n-2)$, pick $g \in V(G)$ and $h_1,h_2 \in V(H)$, $h_1 \neq h_2$.
Consider vertices $u=(g,h_1)$ and $v=(g,h_2)$. Note that $\partial_{\G}(u,v)=1$.
Let us now count the number of common neighbours of $u$ and $v$. Obviously we have
$$
  N_{\G}(u) \cap N_{\G}(v) = \{(g_1,h) \mid g_1 \in N_G(g) \cup \{g\}, h \in V(H) \setminus \{h_1, h_2\}\}.
$$
It follows
$$
  \lambda_{\G} = |N_{\G}(u) \cap N_{\G}(v)| = (k_G+1)(n-2).
$$
\end{proof}

\begin{theorem}
\label{dellex:main}
$\G = G[H]-nG$ is edge regular if and only if one of the following {\rm (i), (ii)} holds:
\begin{itemize}
\item[{\rm (i)}]
$H=E_n$ for some $n \geq 3$ and $G$ is edge regular.
\item[{\rm (ii)}]
$H=K_n$ for some $n \geq 3$ and $G=K_m$ for some $m \geq 2$.
\end{itemize}
\end{theorem}
%
\begin{proof} Assume that $\G$ is edge regular.
Recall that $H=E_n$ or $H=K_n$ by Lemma \ref{Hdel}. Furthermore, $G$ is edge regular by Lemma \ref{lem:lamdel}.
Assume now that $H=K_n$ for some $n \ge 3$. By Corollary \ref{dellambda} we have $\lambda_G + 1 = k_G$.
By Proposition \ref{prop:ar}(i) and since we suppose that $G$ is connected, we have that $G=K_m$ for some $m \ge 2$.

\smallskip \noindent
Conversly, assume first that $H=E_n$ for some $n \geq 3$ and that $G$ is edge regular.
Pick adjacent vertices $u=(g_1, h_1)$ and $v=(g_2, h_2)$ of $\G$. Note that
$g_1, g_2$ are adjacent in $G$ and that $h_1 \ne h_2$. Moreover,
$$
  N_{\G}(u) \cap N_{\G}(v) = \{(g,h) \mid g \in N_G(g_1) \cap N_G(g_2), h \in V(H) \setminus \{h_1, h_2\} \}.
$$
Therefore
$$
  |N_{\G}(u) \cap N_{\G}(v)| = \lambda_G (n-2),
$$
so $\G$ is edge regular.

\smallskip \noindent
Assume now that $H=K_n$ for some $n \geq 3$ and $G=K_m$ for some $m \geq 2$.
Observe that $\G$ is isomorphic to $K_{n \times m}$, which is clearly edge regular. \end{proof}


\begin{lemma}
\label{delmu}
If $\G$ is amply regular, then $G=K_m$ for some $m \geq 2$.
\end{lemma}

\begin{proof}
Assume $\G$ is amply regular and that $G\neq K_m$. By Theorem \ref{dellex:main}, $H=E_n \; (n \ge 3)$, where $n = |V(H)|$.
Pick $g_1, g_2 \in V(G)$ such that $\partial_G(g_1, g_2) = 2$.
Pick $h_1, h_2 \in H \; (h_1 \ne h_2)$ and consider vertices $u=(g_1,h_1)$, $v=(g_2,h_1)$, $z=(g_2,h_2) \in V(\G)$.
Note that, by the definition of $\G$, $\partial_{\G}(u, v) = \partial_{\G}(u,z) = 2$.
Now count the number of common neighbours of vertices $u,v$ and $u,z$ in $\G$.
Note that
$$
  N_{\G}(u) \cap N_{\G}(v)  = \{(g,h) \mid g \in N_G(g_1) \cap N_G(g_2), h \in V(H) \setminus \{h_1\} \},
$$
and that
$$
  N_{\G}(u) \cap N_{\G}(z)  = \{(g,h) \mid g \in N_G(g_1) \cap N_G(g_2), h \in V(H) \setminus \{h_1, h_2\} \}.
$$
Therefore we have
$$
  |N_{\G}(u) \cap N_{\G}(v)| = |N_G(g_1) \cap N_G(g_2)|(|V(H)|-1)
$$
and
$$
  |N_{\G}(u) \cap N_{\G}(z)| = |N_G(g_1) \cap N_G(g_2)|(|V(H)|-2)
$$
Since $\G$ is amply regular and $N_G(g_1) \cap N_G(g_2) \ne \emptyset$, it follows that
$|V(H)|-1 = |V(H)|-2$, a contradiction. Therefore, $G = K_m$ for some $m \ge 2$.
\end{proof}

\begin{theorem}
$\G = G[H]-nG$ is amply regular if and only if one of the following {\rm (i), (ii)} holds:
\begin{itemize}
\item[{\rm (i)}]
$H=E_n$ for some $n \geq 3$ and either $G=K_2$ or $G=K_n$.
\item[{\rm (ii)}]
$H=K_n$ for some $n \geq 3$ and $G=K_m$ for some $m \geq 2$.
\end{itemize}
\end{theorem}
%
\begin{proof} Assume that $\G$ is amply regular.
By Lemma \ref{Hdel}, $H=E_n$ or $H=K_n$ for some $n \ge 3$.
By Lemma \ref{delmu}, $G=K_m$ for some $m \ge 2$. It remains to show that if
$H=E_n$ and $G=K_m$ with $m \ge 3$, then $m=n$.
Pick $g_1, g_2 \in V(G) \; (g_1 \ne g_2)$ and $h_1, h_2 \in V(H) \; (h_1 \ne h_2)$.
Consider vertices $u=(g_1,h_1)$, $v=(g_2, h_1)$ and $z = (g_1, h_2)$ of $\G$.
Since $n, m \ge 3$ we have $\partial_{\G}(u,v) = \partial_{\G}(u,z) = 2$. Furthermore, it is easy to see that
$|N_{\G}(u) \cap N_{\G}(v)| = (m-2)(n-1)$ and that $|N_{\G}(u) \cap N_{\G}(z)| = (m-1)(n-2)$.
It follows that $m=n$.

\smallskip \noindent
Conversly, assume that $H=E_n$ for some $n \geq 3$ and $G=K_m$ for $m \in \{2,n\}$.
If $m=2$, then $\G$ is isomorphic to $K_{n,n} - nK_2$, a complete bipartite graph minus 1-matching, which is clearly amply regular.
If $m=n$, then it is easy to see that $\G$ is amply regular with $\lambda_{\G} = (n-2)^2$ and $\mu_{\G} = (n-2)(n-1)$.
Note that this graph is isomorphic to a complement of the $n \times n$ {\em Rook's graph}, the Cartesian product $K_n \square K_n$.
Finally, if $H=K_n$ for some $n \geq 3$ and $G=K_m$ for some $m \geq 2$, then $\G$ is isomorphic to the complete multipartite graph
$K_{n \times m}$, which is clearly amply regular. \end{proof}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\section{Co-normal product}
\label{sec:conopro}
\indent

Throughout this section let $G$ and $H$ be graphs and let $\G$ be the co-normal product of $G$ and $H$. We will classify graphs $G$ and $H$ for which $\G$ is connected edge regular graph.
To avoid trivialities we assume that $|V(G)| \ge 2$ and $|V(H)| \ge 2$.

\begin{lemma}
\label{lem:con_cn}
$\G$ is connected if and only one of the following holds:
\begin{itemize}
\item[{\rm (i)}]
$H=E_n$ for some $n \geq 2$ and $G$ is connected.
\item[{\rm (ii)}]
$G=E_n$ for some $n \geq 2$ and $H$ is connected.
\item[{\rm (iii)}]
$G$ and $H$ are nonempty and at least one of $G$ or $H$ is without isolated vertices.
\end{itemize}
\end{lemma}
%
\begin{proof}
Assume that one of (i), (ii), (iii) above holds and pick vertices $(g_1,h_1)$ and $(g_2,h_2)$ of $\G$.
We will show that $\G$ is connected by displaying a walk between $(g_1,h_1)$ and $(g_2,h_2)$.
Assume first that (i) above holds. If $g_1=g_2$ then pick a neighbour $g$ of $g_1$ in $G$, and observe that
$((g_1,h_1), (g,h_2), (g_1,h_2))$ is a walk between $(g_1,h_1)$ and $(g_2,h_2)$. If $g_1 \ne g_2$ then pick a path
$(g_1,z_1, z_2, \ldots, z_i, g_2)$ between $g_1$ and $g_2$ in $G$. Note that in this case
$((g_1,h_1), (z_1,h_1), (z_2,h_1), \ldots, (z_i,h_1), (g_2,h_2))$ is a walk between $(g_1,h_1)$ and $(g_2,h_2)$.

\smallskip \noindent
If (ii) above holds then clearly $\G$ is connected since co-normal product is commutative.

\smallskip \noindent
Assume now that (iii) above holds. Since co-normal product is commutative, we could assume that
$G$ is without isolated vertices. As $H$ is nonempty, it contains adjacent vertices $c,d$.
Pick $z \in N_G(g_1)$ and $w \in N_G(g_2)$.
Then $((g_1,h_1), (z,c), (w,d), (g_2,h_2))$ is a walk between $(g_1,h_1)$ and $(g_2,h_2)$.

\smallskip \noindent
We will now show that if $\G$ is connected, then one of (i), (ii), (iii) above holds.
If $H$ is empty, then clearly $G$ is connected. Indeed, if G is not connected, then
pick $g_1, g_2 \in V(G)$ which are in different components and pick $h \in V(H)$. Note that
there is no path between $(g_1,h)$ and $(g_2,h)$, so $\G$ is not connected, a contradiction.
If $G$ is empty, then $H$ is connected from the commutativity of the co-normal product.

\smallskip \noindent
Finally, assume that none of $G, H$ is empty. Assume also that $g \in V(G)$ and $h \in V(H)$ are
isolated vertices. Then $(g,h)$ is an isolated vertex of $\G$, a contradiction. Therefore,
at least one of $G$, $H$ is without isolated vertices, and so (iii) above holds. \end{proof}

\begin{lemma}
\label{lem:reg_cn}
$\G$ is regular if and only if both $G$ and $H$ are regular.
In this case the valency $k_{\G}=k_G |V(H)| + k_H |V(G)| - k_G k_H$.
\end{lemma}
%
\begin{proof}
Assume $\G$ is regular graph of valency $k_{\G}$. For an arbitrary vertex $g \in V(G)$ take vertices $(g, h_1), (g, h_2) \in V(\G)$.
By the definition of $\G$ we have
$$
  k_{\G}=|N_{\G}((g,h_1))|= |N_G(g)| |V(H)| + |N_H(h_1)| |V(G)| - |N_G(g)||N_H(h_1)|,
$$
and
$$
  k_{\G}=|N_{\G}((g,h_2))|= |N_G(g)| |V(H)| + |N_H(h_2)| |V(G)| - |N_G(g)||N_H(h_2)|.
$$
It follows that $|N_H(h_1)|=|N_H(h_2)|$, so $H$ is regular.
$G$ is regular for the commutativity of the co-normal product.

Conversely, if both $G$ and $H$ are regular, then $\G$ is obviously a regular graph, as
$$
|N_{\G}((g, h))|= |N_G(g)| |V(H)| + |N_H(h)| |V(G)| - |N_G(g)||N_H(h)|,
$$
so
$$
|N_{\G}((g, h))|= k_G |V(H)| + k_H |V(G)| - k_G k_H
$$
for every $(g, h) \in V(\G)$. \end{proof}

\begin{lemma}
\label{edge_cn}
Assume that $\G$ is edge regular. Then the following {\rm (i), (ii)} hold.
\begin{itemize}
\item[{\rm (i)}]
Either $G=E_m$ for some positive integer $m$, or $G$ is edge regular.
\item[{\rm (ii)}]
Either $H=E_m$ for some positive integer $m$, or $H$ is edge regular.
\end{itemize}
\end{lemma}
%
\begin{proof}
Recall that $G$ and $H$ are regular by Lemma \ref{lem:reg_cn}.

\noindent
(i) Assume that $G$ is nonempty. Pick a pair of adjacent vertices $g_1, g_2$ of $G$. For an arbitrary vertex $h \in V(H)$ consider
$u = (g_1, h), v = (g_2, h) \in V(\G)$. Note that, by the definition of $\G$,
$\partial_{\G}(u, v)=1$.
We now count the number of common neighbours of $u$ and $v$. Observe that
\begin{eqnarray*}
  N_{\G}(u) \cap N_{\G}(v) &=& \{(g',h') \mid g' \in N_G(g_1) \cap N_G(g_2), h' \in V(H) \} \cup \\  
                           & & \{(g',h') \mid g' \in V(G), h' \in N_H(h) \}.
\end{eqnarray*}
Therefore
\begin{equation}
\label{lam_cn}
  |N_{\G}(u) \cap N_{\G}(v)| = |N_G(g_1) \cap N_G(g_2)||V(H)| + |N_H(h)||V(G)| - |N_G(g_1) \cap N_G(g_2)||N_H(h)|.
\end{equation}
Since $\lambda_{\G} = |N_{\G}(u) \cap N_{\G}(v)|$, it follows that
$$
  |N_G(g_1) \cap N_G(g_2)| = \frac{\lambda_{\G} - k_H|V(G)|}{|V(H)|- k_H}.
$$
Therefore, the number of common neighbours of two adjacent vertices of $G$ is independent of the choice of these vertices,
and thus $\lambda_G$ exists. The result follows.

\medskip \noindent
(ii) This follows from the commutativity of the co-normal product. \end{proof}

\begin{corollary}
\label{lambda_cn}
If $\G$ is edge regular and $G,H$ are nonempty, then
\begin{eqnarray*}
  \lambda_{\G} &=& \lambda_G |V(H)| + k_H|V(G)| - \lambda_G k_H \\
               &=& \lambda_H |V(G)| + k_G|V(H)| - \lambda_H k_G \\
               &=& \lambda_G |V(H)| + 2k_H(k_G - \lambda_G) + \lambda_H(|V(G)| - 2k_G + \lambda_G) \\
               &=& \lambda_H |V(G)| + 2k_G(k_H - \lambda_H) + \lambda_G(|V(H)| - 2k_H + \lambda_H).
\end{eqnarray*}
%$$
 % \lambda_{\G} = \lambda_G |V(H)| + k_H|V(G)| - \lambda_G k_H = \lambda_G |V(H)| + 2k_H(k_G - \lambda_G) + \lambda_H(|V(G) - 2k_G + %\lambda_G|).
%$$
\end{corollary}
%
\begin{proof}
Observe that by Lemma \ref{lem:reg_cn} and Lemma \ref{edge_cn}, $G$ and $H$ are both edge regular, so
$\lambda_G$ and $\lambda_H$ exist. The first equality now follows
from \eqref{lam_cn}. To prove the third equality, pick adjacent vertices $g_1, g_2$ of $G$ and adjacent vertices $h_1, h_2$ of $H$.
Consider vertices $u = (g_1, h_1), v = (g_2, h_2) \in V(\G)$. Note that, by the definition of $\G$,
$\partial_{\G}(u, v)=1$. We now count the number of common neighbours of $u$ and $v$. Note that we have
\begin{eqnarray*}
  N_{\G}(u) \cap N_{\G}(v) &=& \{ (g,h) \mid g \in N_G(g_1) \cap N_G(g_2), h \in V(H) \} \cup \\
                           & & \{ (g,h), \mid g \in N_G(g_1) \setminus N_G(g_2), h \in N_H(h_2) \} \cup \\
                           & & \{ (g,h), \mid g \in N_G(g_2) \setminus N_G(g_1), h \in N_H(h_1) \} \cup \\
                           & & \{ (g,h), \mid g \in V(G) \setminus (N_G(g_1) \cup N_G(g_2)), h \in N_H(h_1) \cap N_H(h_2)\}.
\end{eqnarray*}
Therefore
\begin{eqnarray*}
%\label{lam_str}
  |N_{\G}(u) \cap N_{\G}(v)| &=& |N_G(g_1) \cap N_G(g_2)||V(H)| + \\
                             & &(|N_G(g_1)| - |N_G(g_1) \cap N_G(g_2)|) |N_H(h_2)| + \\
                             & & (|N_G(g_2)| - |N_G(g_1) \cap N_G(g_2)|) |N_H(h_1)| + \\
                             & & (|V(G)| - |N_G(g_1) \cup N_G(g_2)|) |N_H(h_1) \cap N_H(h_2)|.
\end{eqnarray*}
The result follows.

The second and the fourth equality are obtained by reversing the roles of $G$ and $H$. \end{proof}

\begin{theorem}
\label{cn:main}
$\G$ is edge regular if and only if one of the following {\rm (i)--(iii)} holds:
\begin{itemize}
\item[{\rm (i)}]
$H=E_m$ for some $m \geq 2$ and $G$ is edge regular.
\item[{\rm (ii)}]
$G=E_m$ for some $m \geq 2$ and $H$ is edge regular.
\item[{\rm (iii)}]
$H=K_{s\times m}$ and $G=K_{t\times n}$ for some $s,t \geq 2$ and $m,n \geq 1$.
\end{itemize}
\end{theorem}
%
\begin{proof} Assume that $\G$ is edge regular. If $H=E_m$ ($G=E_m$, respectively) for some $m \geq 2$ then we are done, since $G$ ($H$, respectively)
is edge regular by Lemma \ref{edge_cn}. Assume now that $G, H$ are nonempty. By Corollary \ref{lambda_cn},
$$
\lambda_G |V(H)| + k_H|V(G)| - \lambda_G k_H = \lambda_G |V(H)| + 2k_H(k_G - \lambda_G) + \lambda_H(|V(G)| - 2k_G + \lambda_G).
$$
It follows that
$$
k_H(|V(G)| - 2k_G + \lambda_G) = \lambda_H(|V(G)| - 2k_G + \lambda_G).
$$
Since obviously $k_H \neq \lambda_H$ we have $2k_G - \lambda_G = |V(G)|$. Note that in the complement of $G$, every two nonadjacent vertices have exactly $|V(G)|-2k_G+\lambda_G = 0$
common neighbours. Since the complement of $G$ is also regular, Proposition \ref{prop:ar}(ii) implies that the complement of $G$
is isomorphic to $t \times K_n$ for some $t, n \ge 1$.
It follows that $G = K_{t \times n}$ for some $t, n \ge 1$. Since $G$ is nonempty, we also have that $t \ge 2$. The proof that $H=K_{s\times m}$ for some $s \geq 2$ and $m \geq 1$ follows from commutativity of the co-normal product.

Assume now that (i), (ii) or (iii) of the Theorem holds. Then $\G$ is regular by Lemma \ref{lem:reg_cn}.
It is now an easy exercise to show that if (i) ((ii), respectively) holds, then $\lambda_{\G} = \lambda_G |V(H)|$ ($\lambda_{\G} = \lambda_H |V(G)|$, respectively), 
and so $\G$ is edge regular. If (iii) holds, then $\G=K_{st \times mn}$, which is also edge regular.\end{proof}

\begin{corollary}
$\G$ is amply regular if and only if one of the following {\rm (i)--(iii)} holds:
\begin{itemize}
\item[{\rm (i)}]
$H=E_m$ for some $m \geq 2$ and $G = K_{t \times n}$ for some $t \ge 2$, $n \ge 1$.
\item[{\rm (ii)}]
$G=E_m$ for some $m \geq 2$ and $H = K_{t \times n}$ for some $t \ge 2$, $n \ge 1$.
\item[{\rm (iii)}]
$H=K_{s\times m}$ and $G=K_{t\times n}$ for some $s,t \geq 2$, and either $m \geq 2$ or $n \geq 2$.
\end{itemize}
\end{corollary}
%
\begin{proof}
Assume that $\G$ is amply regular.
Let first consider case (i) of Theorem \ref{cn:main}, that is the case when $H=E_m$ for some $m \geq 2$ and $G$ is edge regular.
If $G$ is a complete graph, then (i) above holds. Therefore assume that $G$ is not a complete graph.
Pick $g \in V(G)$ and $h_1, h_2 \in V(H)$.
Abbreviate $u=(g,h_1)$, $v=(g,h_2)$ and note that $\partial_{\G}(u,v) = 2$.
It is also clear that
$$
  |N_{\G}(u) \cap N_{\G}(v)| = k_G |V(H)|.
$$
Next pick arbitrary $g_1, g_2 \in V(G)$ with $\partial_G(g_1, g_2)=2$, and arbitrary $h \in V(H)$.
Abbreviate $w=(g_1,h)$, $z=(g_2,h)$ and note that $\partial_{\G}(w,z) = 2$.
In this case we have
$$
  |N_{\G}(w) \cap N_{\G}(z)| = |N_G(g_1) \cap N_G(g_2)||V(H)|.
$$
Since $\G$ is amply regular, we clearly have
$$
  k_G |V(H)| = |N_G(g_1) \cap N_G(g_2)||V(H)|,
$$
which implies $k_G = |N_G(g_1) \cap N_G(g_2)|$. Therefore, $\mu_G$ exists and is equal to $k_G$.
Note that this implies that for $x,y \in V(G)$ we have $\partial_G(x,y) \le 2$ (since in $G$ there is no induced path of length 3),
and so by Proposition \ref{prop:ar}(iii), $G$ is $K_{t \times n}$ for some positive integers $t,n$.
As $G$ is connected, we clearly have that $t \ge 2$.

\medskip \noindent
Part (ii) follows from the commutativity of the co-normal product.

\medskip \noindent
Let us now consider case (iii) of Theorem \ref{cn:main}, that is
$H=K_{s\times m}$ and $G=K_{t\times n}$ for some $s,t \geq 2$ and $m,n \geq 1$.
Since $\G$ is not a complete graph, we have either $m \ge 2$ or $n \ge 2$.

\medskip \noindent
Conversely, if (i) or (ii) above holds, then $\G = K_{t \times mn}$, and if (iii) above holds, then
$\G=K_{st \times mn}$. In both cases $\G$ is an amply graph. 
\end{proof}

\begin{thebibliography}{10}

\bibitem{Agg}
S.~Aggarwal, P.~K.~Jha, and M.~Vikram. \newblock
Distance Regularity in Direct-Product Graphs. \newblock
{\em Appl. Math. Letters} 13(1):51--55, 2000.

\bibitem{BCN}
A.~E.~Brouwer, A.~M.~Cohen and A.~Neumaier. \newblock
{\em Distance-regular graphs}. \newblock 
Springer-Verlag, New York, 1998.

\bibitem{ImKl}
W.~Imrich, and S.~Klav\v zar. \newblock
{\em Product graphs}. \newblock 
Wiley-Interscience, New York, 2000.

\bibitem{Song}
S.~Y.~Song. \newblock 
Products of distance-regular graphs. \newblock 
{\em Util. Math.} 29:173--175, 1986.

\bibitem{stevo}
D.~Stevanovi\'c. \newblock
Distance regularity of compositions of graphs. \newblock
{\em Appl. Math. Letters} 17(3):337--343, 2004.
\end{thebibliography}
\end{document}