\documentclass[12pt]{article}
\usepackage{e-jc}

\usepackage{amsmath,amsthm,amssymb}

\newtheorem{theorem}{Theorem}
\newtheorem{conj}[theorem]{Conjecture}
\newtheorem{cor}[theorem]{Corollary}
\newtheorem{definition}[theorem]{Definition}
\newtheorem{example}[theorem]{Example}
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{prop}[theorem]{Proposition}
\newtheorem{remark}[theorem]{Remark}
\newtheorem{guess}[theorem]{Conjecture}
\newtheorem{thma}{Theorem}
\renewcommand{\thethma}{\Alph{thma}}

\newcommand{\Aut}{\operatorname*{Aut}}
\newcommand{\creg}{compact regularization}
\newcommand{\csr}{compact symmetric regularization}
\newcommand{\mcsr}{minimum \csr}
\newcommand{\mcr}{minimum \creg}
\newcommand{\visp}{\vspace{.1875in}}
\newcommand{\vsm}{\vspace{.1in}}
\newcommand{\zah}{\mathbb{Z}}
\newcommand{\beem}[1]{\mbox{$\ ( \bmod\  #1)$}}
\newcommand{\bel}{\mbox{$\ell$}}

\begin{document}

\title{On Compact Symmetric \\ Regularizations of Graphs}
\author{R. Vandell (\texttt {vandellr@ipfw.edu})\\ M. Walsh (\texttt {walshm@ipfw.edu})\\ W. D. Weakley (\texttt {weakley@ipfw.edu})\\
Department of Mathematical Sciences\\
Indiana University -- Purdue University Fort Wayne\\
Fort Wayne, Indiana 46805\\ U.S.A.}
\date{}

\maketitle

\begin{abstract}
Let $G$ be a finite simple graph of order $n$, maximum degree $\Delta$, and minimum degree $\delta$. A \emph{compact regularization} of $G$ is a $\Delta$-regular graph $H$ of which $G$ is an induced subgraph: $H$ is \emph{symmetric} if every automorphism of $G$ can be extended to an automorphism of $H$. The \emph{index} $|H:G|$ of a regularization $H$ of $G$ is the ratio $|V(H)|/|V(G)|$. Let $\mbox{mcr}(G)$ denote the index of a \mcr\ of $G$ and let $\mbox{mcsr}(G)$ denote the index of a \mcsr\ of $G$.

Erd\H{o}s and Kelly proved that every graph $G$ has a compact regularization and $\mbox{mcr}(G) \leq 2$. Building on a result of K\"{o}nig, Chartrand and Lesniak showed that every graph has a compact symmetric regularization and $\mbox{mcsr}(G) \leq 2^{\Delta - \delta}$.  Using a partial Cartesian product construction, we improve this to $\mbox{mcsr}(G) \leq \Delta - \delta + 2$ and give examples to show this bound cannot be reduced below $\Delta - \delta + 1$.
\end{abstract}

\noindent \emph{Keywords:} Graph automorphism; regular graph; regularization.

\section{Definitions and history}

For any simple graph $G$, define the \textit{discrepancy} $d_G$ of $G$ by $d_G = \Delta(G)-\delta(G)$; a regular graph is one with discrepancy 0.  For
any $G$ which is not regular (and hence has positive discrepancy), we say that a \textit{regularization} of $G$ is a regular graph $H$ which contains $G$ as an
induced subgraph.  A regularization $H$ of $G$ is \textit{compact} if $\Delta(H)=\Delta(G)$; it is \textit{symmetric} if every automorphism of $G$ can
be extended to an automorphism of $H$.  The \textit{index} $|H:G|$ of a regularization $H$ of $G$ is the ratio $|V(H)|/|V(G)|$.

In his 1936 book on graph theory \cite{Konig}, K\"onig gave a construction for a compact symmetric regularization of index 2 for any graph $G$: take two isomorphic copies $G_1, G_2$ of $G$, and for any deficient vertex $v\in V(G)$ link its images $v_1\in V(G_1), v_2\in V(G_2)$ with $\Delta(G)-d_G(v)$ parallel edges.  (This is the only place in this paper where parallel edges are allowed.) Chartrand and Lesniak \cite{CL} have a version of this proof (that they attribute to K\"onig) that results in a simple graph at the cost of increasing the index to $2^{d_G}$.

The most important result in regularizations is that of Erd\H{o}s and Kelly \cite{EK1,EK2} who gave conditions for minimum compact regularizations of a graph, and showed that these have index at most 2.  Shastri \cite{Shastri} extended this to regularizations that are not necessarily compact, showing that any graph $G$ on $n$ vertices is an induced subgraph of some regular graph $H$ on at most $2n-2$ vertices where $\Delta(H)\ge \Delta(G)$, and that this is best possible.

In another direction, Akiyama, Era, and Harary \cite{AEH} showed that for each graph $G$ there is a $\Delta(G)$-regular graph $H$ of
index at most $(|V(G)| + \Delta(G) + 2)/|V(G)|$ containing $G$ as a subgraph, and that this bound is best possible.  Here $G$ is not required to be an induced subgraph of $H$.

One may also consider certain graph representations as a variation on this theme; the problem of finding a modular representation (see \cite{evans}) or a Kneser representation (see \cite{HPW}) can be construed as finding a symmetric (though not necessarily compact) regularization $H$ of $G$ where $H$ is vertex-transitive.  In both of the cases above the search is limited to a single family of highly symmetric supergraphs; we are not aware of any results on the general version of the problem.

Our concern in this paper is with improving the Chartrand-Lesniak(-K\"onig?) result on compact symmetric regularizations.  We begin by reviewing Erd\H{o}s and Kelly's result in section 2; in section 3 we give a construction for a broad family of compact symmetric regularizations for a graph $G$, which encompasses the one from \cite{CL}.  At its best, this technique yields an index of $d_G+1$; we show that this is best possible with a family of graphs that asymptotically approaches this bound in section 4.  In the final section we look at some examples of graphs that admit constructions with small indices, and conjecture that $\mbox{mcsr}(G) \leq 2$ for every connected graph $G$.

\section{The Erd\H{o}s-Kelly Theorem}

Let $G$ be a graph.  For each vertex $v$, define the \emph{deficiency} $e_v = \Delta(G)-\deg(v)$; $e_v$ is the
number of edges necessary to join with $v$ in order to bring it up to full degree. Let $m(G)$ be the minimum value of $|V(H)| - |V(G)|$ where $H$ is a \creg\ of $G$.

\begin{theorem} \label{erdk}
Let $G$ be a graph of order $n$ and maximum degree $\Delta$. Let $\Sigma$ be the sum of the deficiencies of the vertices of $G$.  Then $G$ has a \creg\ of order $m + n$ if and only if $m$ satisfies the following conditions:

(A) $m \geq \Sigma/\Delta$;

(B) $m^{2} - (\Delta + 1) m + \Sigma \geq 0$;

(C) $m \geq d_{G}$;

(D) $(m+n)\Delta$ is even.\\
Such an $m$ exists, and the minimum value $m(G)$ satisfies $m(G) \leq n$.
\end{theorem}

In \cite{EK1,EK2}, Erd\H{o}s and Kelly were only concerned with finding $m(G)$, but their proof of Theorem \ref{erdk} makes clear that any value of $m$ satisfying the four conditions is $|V(H)| - |V(G)|$ for some \creg\ $H$ of $G$.  Our construction below follows those of \cite{EK1,EK2} but is more explicit, in the hope that for specific graphs $G$ this will allow the reader to see for which $m$ the construction can be adapted to produce an $H$ to which the automorphisms of $G$ extend.

\begin{proof} (That for any positive integer $m$ satisfying conditions (A)-(D), there is a compact regularization $H$ of order $m+n$.)
Let $h, r$ be integers with $\Sigma = hm + r$ and $0 \leq r < m$.  Let $a_{1}, \ldots, a_{m}$ be new vertices, which we consider to be arranged in a circle.  Fill the deficient vertices of $G$ cyclically; that is, vertex $p_{1}$ of deficiency $d_{1}$ is joined to $a_{1}, a_{2}, \ldots, a_{d_{1}}$, then vertex $p_{2}$ of deficiency $d_{2}$ is joined to $a_{d_{1}+1}, \ldots, a_{d_{1}+d_{2}}$ (addition modulo $m$), and so on. By condition (C), there are no parallel edges, and by (A) each $a_{i}$ will have degree at most $\Delta$ at the end of this process.  In fact $a_{1}, \ldots, a_{r}$ have degree $h+1$ and $a_{r+1}, \ldots , a_{m}$ have degree $h$ at this point. We now have to bring the degrees of the $a_{i}$'s up to $\Delta$.

Set $\bel = \Delta - h$. Using (A), $hm \leq \Sigma \leq m \Delta$ so $l \geq 0$. Then $a_{1}, \ldots, a_{r}$ currently have deficiency $\bel - 1$ and
$a_{r+1}, \ldots , a_{m}$ currently have deficiency $\bel$.  We need two facts to proceed.

Claim 1: $\bel < m$.  To see this, note that by the definition of $r$, $0 > r - m$, so (B) implies $m^{2} - (\Delta + 1)m + \Sigma > r - m$.  Then the claim follows from $\Sigma = hm + r$.

Claim 2: If $\bel$ is even then $r$ is even, and if $\bel$ is odd then $m-r$ is even.  To see this, note that the sum of all vertex degrees of $G$ is $n \Delta - \Sigma$, which thus is even, and $(m+n)\Delta$ is even by (D). Together these imply $m \Delta - \Sigma$ is even, and then the claim follows from the equation $r(\bel - 1) + (m-r)\bel = m \Delta - \Sigma$.

If $\bel$ is even, for each $i$ we join $a_{i}$ to $a_{i \pm k}$ for $1 \leq k \leq \bel/2$, which is possible by Claim 1.  Since $r$ is even by Claim 2, we can remove the matching $a_{1}a_{2}, \ldots, a_{r-1}a_{r}$, and are done.

If $\bel$ is odd, by Claim 2 we can begin by adding the matching $a_{r+1}a_{r+2}, \ldots, \\ a_{m-1}a_{m}$.

If then $m$ is even, by Claim 1 we have $\bel - 1 \leq m - 2$ so no $a_{i}$ need be joined to all the other $a_{j}$'s.  For each $i$ we join $a_{i}$ to
$a_{i \pm k}$ for $2 \leq k \leq (\bel - 1)/2$, to $a_{i + (m/2)}$, and to $a_{i-1}$ if $i$ odd, to $a_{i+1}$ if $i$ even, and are done.

If instead $m$ is odd, then since by Claim 1 we have $\bel \leq m-1$, parity implies $\bel + 1 \leq m - 1$.  So for each $i$, we can join $a_{i}$ to $a_{i \pm k}$ for $2 \leq k \leq (\bel + 1)/2$ and are done.
\end{proof}

In discussions involving $m(G)$ we will sometimes use $M(G)$ to denote the minimum value of $|V(H)| - |V(G)|$ where $H$ is a \csr\ of $G$. Clearly $m(G) \leq M(G)$.  Let $\mbox{mcr}(G)$ denote the index of a \mcr\ of $G$ and let $\mbox{mcsr}(G)$ denote the index of a \mcsr\ of $G$, with index as defined earlier.  Then $\mbox{mcr}(G) = 1 + (m(G)/|V(G)|)$ and $\mbox{mcsr}(G) = 1 + (M(G)/|V(G)|)$.

We will be interested in graphs $G$ for which $M(G) = m(G)$, and can already identify one situation where this occurs.

\begin{prop} \label{equal}
If every deficient vertex of a graph $G$ has deficiency $m(G)$, then every minimum \creg\ of $G$ is a \mcsr, so $M(G) = m(G)$.
\end{prop}

\begin{proof}
Let $H$ be a \mcr\ of $G$, with $u_{1}, \ldots, u_{m(G)}$ the vertices of $H$ not in  $G$. Then every deficient vertex of $G$ is joined to every $u_{i}$, so any automorphism $\theta$ of $G$ can be extended to $H$ by defining $\theta(u_{i}) = u_{i}$ for all $i$. Thus $H$ is a \mcsr\ of $G$.
\end{proof}

\section{Partial Cartesian products of graphs}

Recall that the Cartesian product $G\Box L$ of simple graphs $G$ and $L$ is defined as follows:
\begin{align*}V(G\Box L) &= V(G)\times V(L), \\
E(G\Box L) &= \{(u,v)(u,w) \mbox{ : } vw\in E(L)\} \cup \{(u,w)(v,w) \mbox{ : } uv\in E(G)\}.
\end{align*}

Suppose that $G$ is a graph with positive discrepancy.  Let $E=\{e_v>0 \mbox{ : } v\in V(G)\}$ be the set of positive deficiencies of vertices of $G$.  Find a regular graph $L$ with degree at least $d_G$ which admits a factorization $\mathcal{F} = \{F_1,\ldots, F_k\}$ where $F_i$ is $f_i$-regular and there is a choice function $c$ from $E$ to the power set of $\{ 1, \ldots, k \}$ such that for every $e \in E$, $e = \sum_{i\in c(e)}f_i$.

Then define the \textit{partial Cartesian product} $G\stackrel{\mathcal{F}, c}{\Box}L$ as follows:
\begin{align*}
V(G\stackrel{\mathcal{F}, c }{\Box}L) =& V(G)\times V(L), \\ E(G\stackrel{\mathcal{F}, c}{\Box}L) =& \{(u,v)(u,w) \mbox{ : } \text{ $e_{u}>0$ and }vw\in E(F_i)\text{ for some }i\in c(e_u)\} \\
& \cup \{(u,w)(v,w) \mbox{ : } uv\in E(G)\}.
\end{align*}

\begin{theorem} \label{partialcp}
The graph $H = G\stackrel{\mathcal{F}, c}{\Box}L$ is a compact symmetric regularization of $G$.
\end{theorem}

\begin{proof}
For any $v\in V(L)$, the graph induced in $H$ by the vertices $\{(u,v) \mbox{ : } u\in V(G)\}$ is isomorphic to $G$.  To see that $H$ is regular, note that by
construction each vertex $(u,v)$ has $\deg_G(u)$ neighbors of the form $(w,v)$; its neighbors of the form $(u,w)$ correspond to the edges of the factors $F_i$ where $i\in c(e_{u})$, and by construction there are exactly $e_u = \Delta(G)-\deg_G(u)$ such edges.  Hence $H$ is a regularization of $G$, and since $H$ is $\Delta(G)$-regular it is compact.

To prove symmetry, note that every automorphism of $G$ extends in a natural way to $H$: if $\sigma\in\Aut(G)$ then construct $\sigma':V(H)\to V(H)$
by $\sigma'(u,v) = (\sigma(u),v)$.  If vertices $(u_1,v_1)$ and $(u_2,v_2)$ are adjacent in $H$, then either $u_1=u_2=u$ or $v_1=v_2=v$.  If the
latter, then clearly $(\sigma(u_1),v)$ and $(\sigma(u_2),v)$ are adjacent because they rest in the same induced copy of $G$, and $\sigma$ is an
automorphism of $G$.  If the former, then $u$ and $\sigma(u)$ have the same degree and hence the same deficiency; therefore the edge
$(\sigma(u),v_1)(\sigma(u),v_2)$ comes from the same factor $F_i$ that its pre-image does. Thus $\sigma'$ is an automorphism of~$H$.
\end{proof}

\noindent{\bf Remarks.}
(1) The construction of a \csr\ in \cite{CL} is an instance of this construction, using the hypercube of dimension $d_{G}$ as $L$.

(2) The graph $G\stackrel{\mathcal{F}, c}{\Box}L$ contains $|L|$ disjoint copies of $G$: the graphs $G \Box \{ w \}$ for $w \in V(L)$. If $G$ contains a copy of $K_{\Delta + 1}$, necessarily a connected component, then the corresponding $|L|$ copies of $K_{\Delta + 1}$ in $G\stackrel{\mathcal{F}, c}{\Box}L$ may all be identified to give a smaller compact symmetric regularization of $G$. \vspace{.1in}

The partial Cartesian product gives an upper bound for $\mbox{mcsr}(G)$.

\begin{cor}  \label{boundmcsr}
Let $G$ be a graph with discrepancy $d_{G}$. Then $\mbox{mcsr}(G) \leq d_{G}+2$, and if $d_{G}$ is odd, or $d_{G}$ is even and no vertex of $G$ has odd deficiency, then $\mbox{mcsr}(G) \leq d_{G}+1$.
\end{cor}

\begin{proof}
For a graph $G$, the partial Cartesian product construction described above gives a compact symmetric regularization $H = G\stackrel{\mathcal{F}, c}{\Box}L$; the index of $H$ is $|V(L)|$.

If $d_{G}$ is odd, then we can take $L = K_{d_{G}+1}$, since this complete graph has a 1-factorization.  If $d_{G}$ is even, then $K_{d_{G}+1}$ does not have factors of odd degree, but has a 2-factorization.  So if no vertex of $G$ has odd deficiency, we can take $L = K_{d_{G}+1}$, but if some vertex has odd deficiency then we have to go up to $L = K_{d_{G}+2}$.
\end{proof}

Since the regular graph $L$ used in the partial Cartesian product has degree at least $d_{G}$, $L$ has at least $d_{G}+1$ vertices. Thus this construction cannot produce a compact symmetric regularization of index less than $d_{G} + 1$.

\section{An extremal class of graphs}

In the study of symmetric regularizations, the following lemma is useful in considering neighborhoods and degrees of vertices. For a vertex $v$ of a graph $H$ with subgraph $G$, $N_{G}(v)$ denotes the open neighborhood of $v$ in $G$.

\begin{lemma}  \label{prin1}
Suppose $G$ is an induced subgraph of $H$ and every automorphism of $G$
extends to an automorphism of $H$. Let $\Gamma = \{ \alpha \in \mbox{Aut}(H) \mbox{ : } \alpha(G) = G \}$, a subgroup
of Aut($H$).

(a) For every vertex $v$ of $H$ not in $G$, $\Gamma v$ contains at least
$|\{ \sigma(N_{G}(v)) \mbox{ : } \sigma \in \mbox{Aut}(G) \} |$ vertices (necessarily in $V(H) \setminus V(G)$).

%(b) Let $v_{1}, \ldots, v_{p}$ be representatives of the orbits of $V(H) - V(G)$ under the action of $\Gamma$. Then
%\[ |V(H) - V(G)| \geq \sum_{i=1}^{p} |\{ \sigma(N_{G}(v_{i})) \mbox{ : } \sigma \in \mbox{Aut}(G) \} |. \]

(b) Let $H$ be a compact symmetric regularization of $G$, let $v$ be a vertex of $H$ but not $G$, and let $w \in N_{G}(v)$.
Then $|\{ \sigma(N_{G}(v)) \mbox{ : }\sigma \in \mbox{Aut}(G) \mbox{ and } w \in \sigma(N_{G}(v)) \}|$ cannot
exceed the deficiency of $w$.
\end{lemma}

\begin{proof}
To establish (a), choose $\sigma_{1}, \ldots, \sigma_{k} \in \mbox{Aut}(G)$ such that  the $\sigma_{i}(N_{G}(v))$ are the distinct
images of $N_{G}(v)$ under the automorphisms of $G$. For each $i$, let $\theta_{i}$ be an extension of $\sigma_{i}$
to $H$. If for some $i, j$ with $i \neq j$  we have $\theta_{i}(v) = \theta_{j}(v)$ then $\theta_{j}^{-1}\theta_{i}$ fixes $v$ and fixes
$V(G)$ setwise, so fixes $N_{G}(v) = N_{H}(v) \cap V(G)$. This implies $\sigma_{i}(N_{G}(v)) = \sigma_{j}(N_{G}(v))$, a contradiction.
Thus the $\theta_{i}(v)$'s are distinct.

For (b), choose $\sigma_{1}, \ldots, \sigma_{m} \in \mbox{Aut}(G)$ such that  the $\sigma_{i}(N_{G}(v))$ are the distinct
images of $N_{G}(v)$ (under the automorphisms of $G$) that contain $w$. For each $i$, let $\theta_{i}$ be an
extension of $\sigma_{i}$ to $H$. By the proof of part (a), $\theta_{1}(v), \ldots, \theta_{m}(v)$ are
distinct vertices of $H$ that are not in $G$. For each $i$, $w \in \sigma_{i}(N_{G}(v)) = \theta_{i}(N_{G}(v)) = N_{G}(\theta_{i}(v))$,
so $w$ is adjacent to $\theta_{i}(v)$ for $i = 1, \ldots, m$.
\end{proof} \vsm

We now give examples of graphs $G$ with $\mbox{mcsr}(G)$ arbitrarily close to $d_{G}+1$. \vspace{.05in}

\begin{theorem} \label{exam1}
Let $\Delta, h$ be positive integers. Let $G = G(\Delta, h)$ be the disjoint union of $K_{\Delta + 1}$ with $h$ isolated vertices.
%Write $m_{\Delta, h}$ for $m(G(\Delta, h))$ and $M_{\Delta, h}$ for $M(G(\Delta, h))$.
Then
\[
m(G(\Delta,h)) = \left\{ \begin{array}{ll}
\Delta + 1 \mbox{ if $h < \Delta$}, \Delta \mbox{ odd, and } h \mbox{ even,} \\
\max \{\Delta, h \} \mbox{ otherwise,}
\end{array} \right.
\]
\[
M(G(\Delta,h)) = \left\{ \begin{array}{ll}
m(G(\Delta,h)) \mbox{ if $h \leq \Delta + 1$ or $\Delta = 1$}, \\
h \Delta \mbox{ otherwise.}
\end{array} \right.
\]
If $2 \leq \Delta \leq h-2$, the unique minimum compact symmetric regularization of $G(\Delta, h)$ is isomorphic to the disjoint union of $h+1$ copies of $K_{\Delta + 1}$.
\end{theorem}

\begin{proof}
The graph $G$ has $\Delta + 1 + h$ vertices and maximum degree $\Delta$.  The maximum deficiency of $G$ is $d_{G} = \Delta$  and $\mbox{Aut}(G) \cong {\cal S}_{\Delta + 1} \times {\cal S}_{h}$, a product of symmetric groups.

We use Theorem \ref{erdk} to find $m(G(\Delta,h))$.  Here $d_{G} = \Delta$ and $\Sigma = h \Delta$ so conditions (A) and (C) of Theorem \ref{erdk} together are equivalent to $m \geq \max \{\Delta, h \}$. Any $m \geq \Delta$ satisfies condition (B), so we are left to consider the parity condition (D): $(m + \Delta + 1 + h)\Delta$ must be even. Thus if $h \geq \Delta$ then $m(G(\Delta,h)) = h$. If $h < \Delta$ then $m \geq \Delta$; the parity constraint gives $m(G(\Delta,h)) = \Delta$ unless $\Delta$ is odd and $h$ is even, when $m(G(\Delta,h)) = \Delta + 1$.

It remains to find $M(G(\Delta,h))$. Let $x_{1}, \ldots, x_{h}$ be the isolated vertices of $G(\Delta, h)$.

If $\Delta = 1$ then we must connect each $x_{i}$ to a different new vertex, giving a perfect matching, so $M(G(\Delta,h)) = h = m(G(\Delta,h))$ here. We assume $\Delta \geq 2$ for the remainder of the proof.

Suppose $h < \Delta$, $\Delta$ is odd, and $h$ is even, so $m(G(\Delta,h)) = \Delta + 1$ as determined above. We can take $\Delta$ new vertices $v_{1}, \ldots, v_{\Delta}$ and join each to all the deficient vertices of $G$. Take a further new vertex and join it to $v_{1}, \ldots, v_{\Delta}$. We are left with vertices $v_{1}, \ldots, v_{\Delta}$ each now having deficiency $\Delta - h - 1$, which is even. If $\Delta = h + 1$ we are done; otherwise we can finish by putting the $v_{i}$'s in a circle and joining each $v_{i}$ to the $\Delta - h - 1$ nearest $v_{j}$'s. The resulting graph $H$ is a \csr\ of $G(\Delta, h)$ since any automorphism $\theta$ of $G(\Delta, h)$ can be extended to $H$ by setting $\theta(w) = w$ for any vertex of $H$ not in $G(\Delta, h)$.

If $h \leq \Delta$ but we are not in the situation just discussed then $m(G(\Delta,h)) = \Delta = d_{G(\Delta, h)}$ so $M(G(\Delta,h)) = m(G(\Delta,h))$ by Proposition \ref{equal}.

If $h = \Delta + 1$ then $m(G(\Delta,h)) = h$. We can take new vertices $y_{1}, \ldots, y_{h}$ and join every $x_{i}$ to every $y_{j}$ with $i \neq j$.  This yields a \csr\ so again $M(G(\Delta,h)) = m(G(\Delta,h))$.

Finally we consider the case $2 \leq \Delta \leq h-2$.

Suppose in a compact symmetric regularization $H$ of $G$ some vertex $v$ is adjacent to exactly $j$ of the $x_{i}$'s, where $1 \leq j \leq \Delta$.
Let $\Gamma = \{ \alpha \in \mbox{Aut}(H) \mbox{ : } \alpha(G) = G \}$.
By renumbering the $x_{i}$'s we may assume $N_{G}(v) = \{ x_{1}, \ldots, x_{j} \}$. Lemma \ref{prin1}(a) implies that the orbit of $v$ under the action of $\Gamma$ contains at least $\binom{h}{j}$ vertices, corresponding to images of $\{ x_{1}, \ldots, x_{j} \}$ under automorphisms of $G$. Of these images, $\binom{h-1}{j-1}$ contain $x_{1}$, so by Lemma \ref{prin1}(b) the degree of $x_{1}$ in $H$ is at least $\binom{h-1}{j-1}$, implying $\binom{h-1}{j-1} \leq \Delta$.  Since also $\Delta \leq h-2$, this implies $j=1$.
%If $j-1 \geq (h-1)/2$ then since $j \leq \Delta \leq h-2$ we have $\binom{h-1}{h-3} \leq \binom{h-1}{j-1} \leq \Delta$, so $(h-1)(h-2) \leq 2 \Delta$. %Then $(h-1)/2 \leq \Delta/(h-2) \leq 1$ so $h \leq 3$, and then $2 \leq \Delta \leq h-2$ implies $j=1$.
%If $j-1 < (h-1)/2$ and $j > 2$ then $\binom{h-1}{2} \leq \binom{h-1}{j-1} \leq \Delta$, which implies $(h-1)(h-2) \leq 2 \Delta$, implying as above $j %= 1$, a contradiction here, and $j=2$ gives the contradiction $h-1 \leq \Delta$.
Therefore no $u$ in $V(H)$ is adjacent to more than one of the $x_{i}$'s, so $h \Delta$ vertices of $H$ are required to bring the $x_{i}$'s up to degree $\Delta$.

For each $i, k$ with $1 \leq i \leq h$ and $1 \leq k \leq \Delta$, let $x_{ik}$ be a vertex of $H$ adjacent to $x_{i}$. We may complete all the $x_{ik}$'s by adding edges $x_{ik}x_{im}$ for every $i$ and $1 \leq k < m \leq \Delta$, which proves the last claim.
\end{proof}

In the case $2 \leq \Delta \leq h-2$ of Theorem \ref{exam1}, we can employ the partial Cartesian product with $L = K_{\Delta+1}$ and then identify copies of $K_{\Delta+1}$ as in the second remark after Proposition \ref{partialcp} to reach the compact symmetric regularization $H(\Delta, h)$ just found.

The index of $H(\Delta, h)$ is
\[ |H(\Delta, h) : G(\Delta, h)| = \frac{(h+1)(\Delta + 1)}{\Delta + 1 + h} = \frac{\Delta + 1}{\frac{\Delta}{h+1} + 1}. \]

%For the graphs $G = G(\Delta, h)$ we have $d_{G} = \Delta$, so by letting $h$ grow we obtain $\mbox{mcsr}(G)$  as close to $d_{G} + 1$ as desired.

Fix $\Delta > 2$. We note that for $h = \Delta, \Delta + 1$ we have $\mbox{mcsr}(G(\Delta, h)) = 1 + \frac{h}{\Delta + 1 + h} < 2$. As we go to $h = \Delta + 2$, $\mbox{mcsr}(G(\Delta, h))$ jumps to $\frac{\Delta^{2} + 4 \Delta + 3}{2 \Delta + 3}$, which is not quite $(2 \Delta + 5)/4$. Then as $h$ increases, $\mbox{mcsr}(G(\Delta, h))$ approaches $\Delta + 1$, which is $d_{G} + 1$. This establishes:

\begin{cor}
The bound $\mbox{mcsr}(G)\le d_G+1$ cannot be reduced.
\end{cor}

Note that this bound may not be sufficient, since Theorem~\ref{boundmcsr} allows for the possibility of some graphs $G$ with $d_G+1<\mbox{mscr}(G)\le d_G+2$.  However we have not found any $G$ with $\mbox{mscr}(G)$ in this range.

\section{Some graphs admitting smaller indices}

%We require some ideas about group actions.

%Suppose we have an action of a group $A$ on a set $S$.  For each $x \in S$, the set $Ax = \{ ax \mbox{ : } a \in A \}$ is the \emph{orbit} of $x$ %under $A$. A nonempty subset $T$ of $S$ is a \emph{block} of the action if for every $\sigma \in A$, the sets $T$ and $\sigma \cdot T$ are either %equal or disjoint.

%Let $G$ be a graph and $D$ the set of deficient vertices of $G$.  Under the action of $A = \Aut(G)$ on $D$, let $O_{1}, \ldots, O_{k}$ be the orbits. %For $i = 1, \ldots, k$, let $e_{i}$ be the deficiency of each vertex of $O_{i}$ and let $|O_{i}| = m_{i}$.

%To build a symmetric regularization $H$ of $G$, we seek the subsets of $V(G)$ that will be neighborhoods in $G$ of vertices of $H$. For each $i$, let %$t_{i}$ be the number of vertices of $H$ having neighbors in $O_{i}$, and let $v(i, 1), \ldots, v(i, t_{i})$ be those vertices.  Then for each $j$, $1 %\leq j \leq t_{i}$, let $N_{ij} = N_{G}(v(i, j)) \cap O_{i}$, with $|N_{ij}| = n_{ij}$. Let $f_{ij}$ be the number of distinct images of $N_{ij}$ %under the action of $A$.  Since every vertex of $O_{i}$ occurs the same number of times in these images, together they make an %$(f_{ij}n_{ij}/m_{i})$-fold cover of $O_{i}$. In order to repair the deficiency of the vertices of $G$, we need $\sum_{j=1}^{t_{i}} f_{ij}n_{ij}/m_{i} %= e_{i}$ for each $i$, or equivalently
%\begin{equation}
%\[ \label{repair}
%\sum_{j=1}^{t_{i}} f_{ij}n_{ij} = m_{i}e_{i} \mbox{  for each $i$,}
%\]
%\end{equation}
%where $m_{i}e_{i}$ is the total deficiency of the orbit $O_{i}$.

%We note that it is possible for a vertex of $H$ to have neighbors in more than one orbit of deficient vertices; that is, $v(i_{1}, j_{1}) = v(i_{2}, %automorphic images of $N_{ij}$ are the neighborhoods in $G$ of different vertices of $H$.

%Note that for any $i$, sets $N_{ih}$ and $N_{ij}$ need not be different.

%In the above description, the cover of $O_{i}$ by the distinct images of $N_{ij}$ under the action of $A$ is 1-fold if and only if those images form a %partition of $O_{i}$. This is equivalent to saying that $N_{ij}$ is a block of $O_{i}$ under the action of~$A$. \vspace{.1in}

We have shown that in general the bound of $d_G+1$ cannot be improved; however, in general constructions with much smaller indices can be achieved.

\begin{prop}\label{almostall}
Almost all finite graphs admit \csr s with index at most 2.
\end{prop}

\begin{proof}
Erd\H{o}s and R\'enyi \cite{ER} showed that almost all graphs have trivial automorphism groups; any compact regularization of such a graph is clearly also symmetric.
\end{proof}

Hence, we may distinguish between graphs with relatively small automorphism groups (i.e. the vast majority of graphs) and those with plenty of automorphisms.  In the former case, we can generally manipulate the Erd\H{o}s-Kelly construction to respect the automorphism group; in the latter, we may exploit the symmetries of the graph to organize our addition of vertices.  We give a construction and some examples to illustrate this.

Let $G$ be a graph.  Say that a predicate $Q: V(G) \times V(G) \rightarrow \{ T, F \}$ is \emph{balanced} if for all $a, b \in V(G)$ and all $\eta \in \mbox{Aut}(G)$, $Q(a, b) = Q(b, a)$ and $Q(a, b) = Q(\eta(a), \eta(b))$.

Let $G'$ be  a copy of $G$, $\phi$ an isomorphism from $G$ to $G'$, $Q$ a balanced predicate for $G$, and $H_{Q}$ the disjoint union of $G$ and $G'$ with additional edges: for all $a, b \in V(G)$, if $Q(a, b)$ then we join $a$ to $\phi(b)$ and $\phi(a)$ to $b$.

\begin{prop}  \label{vertedges}
For any graph $G$ and balanced predicate $Q$ on $G$, every automorphism of $G$ extends to an automorphism of $H_{Q}$.
\end{prop}

\begin{proof}
Given $\theta \in \mbox{Aut}(G)$, extend $\theta$ to $\Theta: H_{Q} \rightarrow H_{Q}$ by defining $\Theta(\phi(w)) = \phi(\theta(w))$ for all $w \in V(G)$.  We check that $\Theta$ respects adjacency in $H_{Q}$.  It is clear that $x \leftrightarrow y$ if and only if $\Theta(x) \leftrightarrow \Theta(y)$ for $x, y \in V(G)$ and for $x, y \in V(G')$.  Suppose $x \in V(G)$ and $y \in V(G')$. Then there is $b \in V(G)$ with $y = \phi(b)$.  By the definition of $H_{Q}$, $x \leftrightarrow y$ if and only if $Q(x, b)$, and $\Theta(x) \leftrightarrow \Theta(y)$ if and only if $\theta(x) \leftrightarrow \phi(\theta(b))$, which is true if and only if $Q(\theta(x), \theta(b))$.  Since $Q$ is balanced we are done.
\end{proof}

For a nonregular graph $G$, we can attempt to construct a compact symmetric regularization $H_{Q}$ of index 2 by taking $Q$ to be the disjunction of several balanced predicates, as shown next.

Note that as automorphisms respect vertex degree, there is a natural action of the automorphism group of a graph on the set of deficient vertices of the graph.

\begin{prop}  \label{mirror}
Suppose that $G$ is a graph for which $O_{1}, \ldots, O_{k}$ are the orbits of deficient vertices under the action of Aut($G$), with $|O_{i}| = m_{i}$ for each $i$.  If the deficiency $e_{i}$ of the vertices of $O_{i}$ is a member of $\{ 1, m_{i}-1, m_{i} \}$ for each $i$, then $\mbox{mcsr}(G) \leq 2$.
\end{prop}

\begin{proof}
We use the above construction with the balanced predicate $Q = Q_{1} \lor \cdots \lor Q_{k}$, where $Q_{i}(a, b)$ is ``$a=b$ and $a \in O_{i}$'' if $e_{i} = 1$, is ``$a, b \in O_{i}$'' if $e_{i} = m_{i}$, and is ``$a, b \in O_{i}$ and $a \neq b$'' if $e_{i} = m_{i} - 1$. Then $H_{Q}$ is a compact symmetric regularization of $G$ by Proposition \ref{vertedges}.
%Consider $G$ together with a copy $G'$ of $G$ and an isomorphism $\phi: G \rightarrow G'$. Let $H$ be the disjoint union of $G$ and $G'$ together with %the following edges: for each $i$, if $e_{i} = 1$ we join $v$ to $\phi(v)$ for each $v \in O_{i}$; if $e_{i} = m_{i}$ we join $v$ to $\phi(w)$ for all %$v, w \in O_{i}$; if $e_{i} = m_{i} - 1$ we join $v$ to $\phi(w)$ for all unequal $v, w \in O_{i}$.
%Then any automorphism $\theta$ of $G$ may be extended to an automorphism $\Theta$ of $H$
%by setting $\Theta(\phi(w)) = \phi(\theta(w))$ for every vertex $w$ of $G$, so $H$ is a \csr\ of $G$. Thus $\mbox{mcsr}(G) \leq 2$.
\end{proof}

The graphs in the following example are similar to those of Example \ref{exam1} but have \csr s of much smaller indices.

\begin{example}
Let $d$ and $h$ be positive integers. Let $G$ be the graph consisting of a clique of size $d+1$ and $h$ further vertices, each joined to all members of the clique. Then $\mbox{mcsr}(G) \leq 2$.
\end{example}

\begin{proof}
The graph $G$ has $\Delta(G) = d+h$ and one orbit of deficient vertices, containing $h$ vertices of deficiency $h-1$, so Proposition \ref{mirror} applies.
\end{proof}

%\section{Grid graphs and cylinder graphs}

%We examine two families of graphs with small automorphism groups.

In their proof \cite{EK1,EK2} of Theorem \ref{erdk}, Erd\H{o}s and Kelly gave examples to show that none of the four conditions could be omitted. But
frequently the first condition ($m \geq \Sigma/\Delta$) dominates: $m(G) = \lceil \Sigma/\Delta \rceil$.
It is easily seen that $M(P_{n}) = m(P_{n}) = \lceil \Sigma/\Delta \rceil$, and one may ask whether this property holds for more complex graphs. We show that it holds for grid graphs, and for cylinder graphs of even circumference.

For integers $n \geq 2$, let $P_{n}$ denote a path with $n$ vertices. For integers $n \geq 3$, let $C_{n}$ denote a cycle with $n$ vertices. Let $\zah_{n}$ denote the group of integers modulo $n$.  For $n, k \geq 2$ we say the Cartesian product $P_{n} \times P_{k}$ is a \emph{grid graph}; for $n \geq 3$ and $k \geq 2$, the Cartesian product $C_{n} \times P_{k}$ is a \emph{cylinder graph}.

The constructions required to prove the next two theorems are straightforward extensions of Proposition~\ref{mirror}, and are given in the Appendix.

%We state the following results without proof; the constructions required to demonstrate them are straightforward %extensions of Proposition~\ref{mirror}. \emph{(To the referees: Proofs are given in the Appendix.)}

%Since $P_{2} \times P_{2}$ is 2-regular, $M(P_{2} \times P_{2}) = m(P_{2} \times P_{2}) = 0$. For $k \geq 3$, $P_{2} \times P_{k}$ has four deficient vertices. We can make a \csr\ of $P_{2} \times P_{k}$ by adding vertices $x_{1}$ and $x_{2}$: $x_{1}$ is joined to any two of the deficient vertices, $x_{2}$ is joined to the other two, and $x_{1}$ and $x_{2}$ are joined. Thus $M(P_{2} \times P_{k}) = m(P_{2} \times P_{k}) = 2$.  The remaining possibilities are handled by the following theorem.

\begin{theorem}  \label{gridthm}
For $n, k \geq 3$,
$
M(P_{n} \times P_{k}) = m(P_{n} \times P_{k}) = \left \lceil \frac{n+k}{2} \right \rceil =
\lceil \Sigma/\Delta \rceil.
$
\end{theorem}

%\begin{proof}
%We will denote the vertices of $P_{n} \times P_{k}$ by ordered pairs $(i, j), 1 \leq i \leq n, 1 \leq j \leq k$\,; the vertex $(i, j)$ is adjacent to those vertices $(i \pm 1, j \pm 1)$ that are defined.
%
%Here $\Sigma = 4 \cdot 2 + 2(n-2) + 2(k-2) = 2(n+k)$ and $\Delta = 4$.
%
%Condition (A) of Theorem \ref{erdk} implies $m(P_{n} \times P_{k}) \geq \lceil \Sigma/\Delta \rceil$, so to prove the theorem it suffices to add $\lceil \Sigma/\Delta \rceil$ vertices and appropriate edges to $P_{n} \times P_{k}$ and thereby produce a compact symmetric regularization $H$ of $P_{n} \times P_{k}$. Note that when $n \neq k$, $\Aut(P_{n} \times P_{k}) \cong \zah_{2} \times \zah_{2}$ is the group of symmetries of a rectangle, and $\Aut(P_{n} \times P_{n})$ is isomorphic to the dihedral group of order 8, which is the group of symmetries of a square.  Throughout the remainder of the proof, let $\theta$ denote an arbitrary automorphism of $P_{n} \times P_{k}$.
%
%We start with $\lfloor n/2 \rfloor + \lfloor k/2 \rfloor -2$ new vertices: for each $j$, $2 \leq j \leq \lfloor k/2 \rfloor$, add a new vertex whose neighborhood in $P_{n} \times P_{k}$ is $T_{j} = \{ (1, j), (1, k-j), (n, j), (n, k-j) \}$, and for each $i$, $2 \leq i \leq \lfloor n/2 \rfloor$, add a new vertex whose neighborhood in $P_{n} \times P_{k}$ is  $ S_{i} = \{ (i, 1), (n-i, 1), (i, k), (n-i, k) \}$. If $n \neq k$ then each $T_{j}$ and each $S_{i}$ is an orbit of $V(P_{n} \times P_{k})$ under the action of $\Aut(P_{n} \times P_{k})$ and thus is fixed setwise by $\theta$. If $n = k$ then for each $i$, $2 \leq i \leq \lfloor n/2 \rfloor$, $\{T_{i}, S_{i} \}$ is permuted by $\theta$.
%
%Completing $H$ depends on the parities of $n$ and $k$.
%
%If $n \equiv k \beem{2}$, we add two more vertices, each with neighborhood $C = \{ (1, 1), (n, 1), (1, k), (n, k) \}$ in $P_{n} \times P_{k}$. If $n$ and $k$ are odd, we also add a vertex with neighborhood $M = \{ (1, (k+1)/2), (n, (k+1)/2), ((n+1)/2, 1), ((n+1)/2, k) \}$ in $P_{n} \times P_{k}$. Here $\theta(C) = C$, $\theta(M) = M$, and the total number of new vertices is $(n+k)/2 = \Sigma/\Delta$.
%
%If $n \not \equiv k \beem{2}$, we may assume without loss of generality that $n$ is odd.  We complete $H$ by adding three more vertices. The first vertex has neighborhood $C$ in $P_{n} \times P_{k}$. Then add a second vertex with neighborhood $L = \{ (1, 1), ((n+1)/2, 1), (n, 1) \}$ in $P_{n} \times P_{k}$ and a third vertex with neighborhood $ R = \{ (1, k), ((n+1)/2, k), (n, k) \}$ in $P_{n} \times P_{k}$, and connect the second and third vertices. Here $\theta$ permutes $\{ L, R \}$ and the total number of new vertices is $(n+k+1)/2 = \lceil \Sigma/\Delta \rceil$.
%
%In each case, $H$ is a compact regularization of $P_{n} \times P_{k}$ with the desired number of vertices.  The automorphism $\theta$ induces a permutation of the neighborhoods in $P_{n} \times P_{k}$ of the added vertices, and the corresponding permutation of the set of added vertices gives an extension of $\theta$ to an automorphism of $H$. Thus $H$ is a symmetric regularization.
%\end{proof}
%
%Since $C_{n} \times P_{2}$ is 3-regular, $M(C_{n} \times P_{2}) = m(C_{n} \times P_{2}) = 0$. Otherwise we have the following theorem.

\begin{theorem} \label{cylthm}
For $n, k \geq 3$, $m(C_{n} \times P_{k}) = \lceil n/2 \rceil = \lceil \Sigma/\Delta \rceil$ and
\[ M(C_{n} \times P_{k}) = \left\{ \begin{array}{lll}
n/2 \hspace{.26in} \mbox{       if $n$ is even,} \\
2n/3 \hspace{.18in} \mbox{  if $n$ is an odd multiple of 3,} \\
n \hspace{.4in} \mbox{  otherwise.}
\end{array} \right.
\]
\end{theorem}

%\begin{proof}
%We will denote the vertices of $C_{n} \times P_{k}$ by ordered pairs $(i, j)$, where $i \in \zah_{n}$ and $j$ is an integer with $1 \leq j \leq k$\,; the vertex $(i, j)$ is adjacent to those vertices $(i \pm 1, j \pm 1)$ that are defined.
%
%The graph $C_{n} \times P_{k}$ has $n(k-2)$ vertices of degree 4 and $2n$ vertices of degree 3, so $\Delta = 4$, $d_{C_{n} \times P_{k}} = 1$, $\Sigma = 2n$, and $\Sigma/\Delta = n/2$. The conditions of Theorem \ref{erdk} here become $m \geq n/2$, $m^{2} - 5m  + 2n \geq 0$, $m \geq 1$, and $(m + nk)4$ is even.  The minimum value of $m$ satisfying these is $\lceil n/2 \rceil$, establishing the value of $m(C_{n} \times P_{k})$, so we turn to $M(C_{n} \times P_{k})$.
%
%Each deficient vertex of $C_{n} \times P_{k}$ requires only one new edge. By Lemma \ref{prin1}(b), this implies that for each new vertex $v$ of a \csr\ of $C_{n} \times P_{k}$, no vertex of $C_{n} \times P_{k}$ is contained in more than one image of $N_{G}(v)$ under the automorphisms of $C_{n} \times P_{k}$.  That is, each $N_{G}(v)$ is a \emph{block} of the action of Aut($G$) on the set of deficient vertices of $C_{n} \times P_{k}$:  the images of $N_{G}(v)$ form a partition of the orbit that contains them. This considerably restricts our search. Let $B$ be a block with $|B| \leq \Delta = 4$.
%
%The automorphism group of $C_{n} \times P_{k}$ has order $4n$, and is isomorphic to the product of a dihedral group of order $2n$ (from the automorphism group of $C_{n}$) and a $\zah_{2}$ (from the automorphism group of $P_{n}$).  The second factor yields $\sigma \in \Aut(C_{n} \times P_{k})$ defined by $\sigma(h, l) = (h, k+1-l)$.  From the first factor, for each $i \in \zah_{n}$, there is $\phi_{i} \in \Aut(C_{n} \times P_{k})$ defined by $\phi_{i}(h, l) = (2i-h, l)$.
%
%A useful fact: For any $(i, j) \in B$, since $\phi_{i}(i, j) = (i, j)$, necessarily $\phi_{i}(B)~=~B$.
%
%This fact implies that blocks of size 4 exist if and only if $n$ is even, in which case the sets $F_{i} = \{ (i, 1), (i, k), (i+(n/2), 1), (i+(n/2), k) \}$, $i = 1, \ldots, n/2,$ are four-blocks forming a partition of $D$. We can then make these the neighborhoods in $C_{n} \times P_{k}$ of $n/2$ new vertices.  The resulting graph is a compact regularization $H$ of $C_{n} \times P_{k}$; since each new vertex has all neighbors in $C_{n} \times P_{k}$, no smaller compact regularization is possible.  Any automorphism $\theta$ of $C_{n} \times P_{k}$ induces a permutation of $\{F_{i} \mbox{ : } 1 \leq i \leq n/2 \}$, which gives a permutation of the new vertices, thus defining an extension of $\theta$ to $H$, so $H$ is symmetric.
%
%Assume then that $n$ is odd, so no four-block of the action of $\Aut(C_{n} \times P_{k})$ on $D$ exists.  We look for three-blocks; using the $\phi_{i}$'s as before, we see that three-blocks exist if and only if $n$ is divisible by 3, in which case the sets $E_{i,1} = \{ (i, 1), (i + (n/3), 1), (i+(2n/3), 1) \}$ and $E_{i,k} = \{ (i, k), (i + (n/3), k), (i+(2n/3), k) \}$, $i = 1, \ldots, n/3,$ are three-blocks forming a partition of $D$. For each $i$, $1 \leq i \leq n/3$, we take a vertex $v_{i, 1}$ with neighborhood $E_{i, 1}$ in $C_{n} \times P_{k}$ and a vertex $v_{i, k}$ with neighborhood $E_{i, k}$ in $C_{n} \times P_{k}$, and join $v_{i, 1}$ and $v_{i, k}$.  The result is a compact regularization $H$ of $C_{n} \times P_{k}$, and it has minimum order since no new vertex can cover more than three vertices of $C_{n} \times P_{k}$.
%
%For $i = 1, \ldots, n/3$, $\sigma$ switches $E_{i, 1}$ and $E_{i, k}$, and for these $i$ and all $j \in \zah_{n}$,
%$\phi_{j}(E_{i, g}) = E_{2j-i, g}$ for $g \in \{1, k \}$. Thus we can extend these automorphisms to $H$ as follows: $\overline{\sigma}$ switches  $v_{1, 1}$ and $v_{i, k}$ for all $i \in \zah_{n}$, and $\overline{\phi_{j}}(v_{i, g}) = v_{2j-i, g}$ for all $j \in \zah_{n}$ and $i=1, \ldots, n/3$ in $\zah_{n}$. As $\sigma$ and the $\phi_{i}$'s generate $\Aut(C_{n} \times P_{k})$, this shows $H$ is symmetric as a regularization of $G$.
%
%Finally, assume that $n$ is divisible by neither 2 nor 3. Then the largest blocks possible are two-blocks, and the sets $Z_{i} = \{ (i, 1), (i, k) \}$, $1 \leq i \leq n$, are two-blocks forming a partition of $D$. For each $i \in \zah_{n}$, we may take a vertex $t_{i}$ adjacent to the vertices of $Z_{i}$ and also to $t_{i-1}$ and $t_{i+1}$.  The resulting graph is a compact regularization of $C_{n} \times P_{k}$; it is isomorphic to $C_{n} \times C_{k+1}$ and thus is visibly a symmetric regularization.  Since no new vertex can cover more than two vertices of $C_{n} \times P_{k}$, it has minimum order.
%\end{proof}


%\section{Subdivision graphs of cubic graphs}

Another class of examples that gives small values of $\mbox{mcsr}(G)$ are subdivisions of  regular cubic graphs (where each edge is subdivided once).  The Erd\H{o}s-Kelly construction gives an index of $\frac{6}{5}$ for these graphs; K\"onig's construction for a \csr\ gives an index of 2 in this case.  This is best possible, since subdivisions of $K_{3,3}$, the Tutte-Coxeter graph, and the Heawood graph all require constructions of index 2. (This statement is established in Theorem A of the Appendix.)
%\emph{(To the referees: This statement is established in Theorem A of the appendix.)}

%
%Let $G$ be a graph with minimum degree $\delta(G)$ at least three. The \emph{subdivision graph} of $G$, denoted by $G^{*}$, is the graph obtained by subdividing each edge of $G$ once. So if $G$ has $n$ vertices and $m$ edges, then $G^{*}$ has $n$ vertices of degree at least $\delta(G)$ and $m$ vertices of degree 2, and $2m$ edges. As automorphisms respect degree and take edges to edges, $\mbox{Aut}(G)$ is isomorphic to $\mbox{Aut}(G^{*})$.
%
%%To find a \mcsr\ of $G^{*}$ usually requires examination of the action of $\Aut(G)$ on $V(G)$ and $E(G)$.
%
%%We will mainly consider $G^{*}$ when $G$ is a cubic graph and there is just one orbit of deficient vertices of $G^{*}$.  The latter condition is %equivalent to the graph $G$ being edge-transitive.
%
%\begin{prop}  \label{mandm}
%For a cubic graph $G$, $\mbox{mcr}(G^{*}) = 6/5$ and $\mbox{mcsr}(G^{*}) \leq 2$.
%\end{prop}
%
%\begin{proof}
%We use Theorem \ref{erdk} to find $\mbox{mcr}(G^{*})$. Since each vertex of $G$ has degree 3, there is a positive integer $l$ such that $G$ has $2l$ vertices and $3l$ edges. Then $G^{*}$ has $5l$ vertices and $6l$ edges. The discrepancy of $G^{*}$ is one and $\Sigma = 3l$. The four conditions of Theorem \ref{erdk} then reduce to $m \geq l$, $m^{2} - 4m + 3l \geq 0$, $m \geq 1$, and $(m+5l)3$ is even. It is easily seen that $m = l$ is the least integer satisfying the conditions, so $\mbox{mcr}(G^{*}) = 6l/5l = 6/5$.
%
%Since $d_{G^{*}} = 1$, Corollary \ref{boundmcsr} implies $\mbox{mcsr}(G^{*}) \leq 2$.
%\end{proof}
%
%%\noindent The complete graph {\boldmath $K_{4}$}. \vspace{.2in}
%
%%\noindent The complete bipartite graph {\boldmath $K_{3, 3}$}.  The graph $K_{3, 3}^{*}$ has nine deficient vertices.  \ldots minimum compact %symmetric regularization of size $2$. The unique minimum compact symmetric regularization here is the one supplied by Propositions \ref{partialcp} or %\ref{mirror}. \vspace{.2in}
%
%Next we show that the upper bound of 2 for $\mbox{mcsr}(G^{*})$ in Proposition \ref{mandm} is achieved by some cubic graphs $G$ with large automorphism groups. This requires some definitions.
%
%For a nonnegative integer $t$, a \emph{$t$-arc} of a graph $G$ is a sequence $(v_{0}, v_{1}, \ldots, v_{t})$ of $t+1$ vertices of $G$ such that $v_{i-1}v_{i} \in E(G)$ for $1 \leq i \leq t$ and $v_{i-1} \neq v_{i+1}$ for $1 \leq i \leq t-1$.  We say $G$ is \emph{$t$-transitive} if $\Aut(G)$ acts transitively on the set of $t$-arcs in $G$ but does not act transitively on the set of $(t+1)$-arcs in $G$.
%
%The graph $G$ is \emph{symmetric} if $\Aut(G)$ acts transitively on the set of 1-arcs of $G$.  Thus if $G$ is $t$-transitive for some $t \geq 1$ then $G$ is symmetric.
%
%The \emph{girth} of $G$ is the number of edges in a smallest cycle of $G$.
%
%The \emph{line graph} of $G$ is the graph $L(G)$ whose vertex set is $E(G)$; two edges of $G$ are adjacent in $L(G)$ if they share a vertex in $G$.
%
%The \emph{Heawood graph} may be briefly described as follows: its vertex set is $\{ 0, 1, \ldots, 13 \}$ and (using addition modulo 14) its edge set is $\{ \{i, i+1\}: 0 \leq i \leq 13 \} \cup \{ \{2i, 2i + 5 \}: 0 \leq i \leq 6 \}$ (addition modulo 14). More can be found at \cite{Hea}.
%
%A short description of the \emph{Tutte-Coxeter graph}: vertex set $\{0, 1, \ldots, 29 \}$ and (using addition modulo 30) edge set  $\{\{i, i+1\}: 0 \leq i \leq 29 \} \cup \{\{6m, 13 + 6m \}, \{3+6m, 10+6m \}, \{17 + 6m, 26+6m \}: 0 \leq m \leq 4 \}$. More can be found at \cite{Tcox}.
%
%\begin{theorem}  \label{symcubic}
%Let $G$ be a connected cubic $t$-transitive graph for some integer $t \geq 1$. If $t > d = \mbox{diam}(L(G))$ then $t = d + 1$, $|V(G)| = 2^{t} - 2$, $\mbox{mcsr}(G^{*}) = 2$, and $G$ is isomorphic to one of $K_{3, 3}$, the Heawood graph, and the Tutte-Coxeter graph.
%\end{theorem}
%
%\begin{proof}
%Fix an edge $e$ of $G$ and for $i = 0, 1, \ldots, d = \mbox{diam}(L(G))$, let $S_{i}$ denote the set of edges at distance $i$ from $e$. Let $G'$ be the subgraph of $G$ induced by $\cup_{i=0}^{t-2}S_{i}$.  Since $G$ is $t$-transitive, \cite[Proposition 17.2]{Biggs} says that the girth $g$ of $G$ is at least $2(t-1)$, which implies $G'$ is a tree.  As $G$ is cubic, induction on distance from $e$ shows $|S_{i}| = 2^{i+1}$ for $1 \leq i \leq t-2$. Thus $G'$ has $2^{t-1}$ vertices of degree one, each of which is incident in $G$ to one edge of $S_{t-2}$ and two edges of $S_{t-1}$. To count $S_{t-1}$, we require the following.
%
%Claim. No vertex of $G$ is incident to three edges of $S_{t-1}$.
%
%Proof of claim: Suppose there is such a vertex, say $x$, with edges $w_{1}x$, $w_{2}x$, $w_{3}x \in S_{t-1}$. Each $w_{i}x$ is the last edge in a $t$-arc $A_{i}$ whose first edge is $e = \{y, z\}$. As there are three edges incident at $x$ and only two ends of $e$, at least two $A_{i}$'s must have the same initial 1-arc; we may assume that for $j = 2, 3$, $A_{j} = [y_{1} = y, z, y_{j}, \ldots]$.
%
%If $A_{1}$ also began with $y_{1}$, then since $\deg z = 3$ we would have two $(t-2)$-arcs with the same initial vertex ending in $x$, and these would be distinct as they would pass through different $w_{i}$'s. This would imply $g \leq 2t-4$, a contradiction.
%Thus $A_{1} = [z, y_{1}, \ldots]$.
%
%As $G$ is $t$-transitive, there is an automorphism $\theta$ of $G$ with $\theta(A_{2}) = A_{1}$. Then $\theta(w_{2}) = w_{1}$ so $\theta(w_{3}) = w_{j}$ for some $j \in  \{ 2, 3 \}$. Omitting the end edges of $\theta(A_{3})$ gives a path of length $t-2$ from $y_{1}$ to $w_{j}$, and $A_{j}$ includes a path of length $t-1$ from $y_{1}$ to $w_{j}$. Together these imply the existence of a cycle of odd length at most $2t-3$, contradicting $g \geq 2(t-1)$. This completes the proof of the claim.
%
%The claim implies that each edge in $S_{t-1}$ is incident at each end to one edge in $S_{t-2}$ and one edge in $S_{t-1}$. An edge in $S_{t-2}$ cannot be incident only to edges in $S_{t-1}$, so the subgraph of $G$ induced by $S_{t-1}$ is a disjoint union of cycles, with each vertex of each cycle incident in $G$ to one edge in $S_{t-2}$. It follows that $|S_{t-1}| = |S_{t-2}| = 2^{t-1}$. As $d \leq t-1$ we have accounted for all edges of $G$, and $d = t-1$. Then $|E(G)| = \sum_{i=0}^{t-1} |S_{i}| = 1 + \sum_{i=1}^{t-2} 2^{i+1} + 2^{t-1} = 3 \cdot 2^{t-1} - 3$. Since $G$ is a cubic graph, $|V(G)| = (2/3)|E(G)| = 2^{t} - 2$.
%
%Let $H$ be a \csr\ of $G^{*}$. We first show that each vertex in $H$ but not $G^{*}$ is adjacent to at most one vertex of $G^{*}$.  If not, then since $G$ is $t$-transitive we may assume that the vertex $v_{0}$ that subdivides edge $e_{0} = e$ of $G$ and the vertex $v_{1}$ that subdivides another edge $e_{1}$ of $G$ are adjacent to a vertex $w$ of $H$. For some $i$, $1 \leq i \leq t-1$, the distance from $e_{0}$ to $e_{1}$ in $L(G)$ is $i$, and we have shown $|S_{i}| \geq 4$. Then since $G$ is $t$-transitive, the automorphisms of $G$ that fix $e_{0}$ carry $e_{1}$ to at least three other edges of $G$. Thus if $B$ is a block of the action of $\mbox{Aut}(G^{*})$ on $V(G^{*})$ and $v_{0}, v_{1} \in B$ then $|B| \geq 5$. But then $|N_{G^{*}}(w)| \geq 5$, contrary to $H$ being a cubic graph.
%
%It follows that we may define a one-to-one function $f: E(G) \rightarrow (V(H) \setminus V(G^{*}))$ by saying $f(xy)$ is the unique vertex of $H$ but not $G^{*}$ adjacent to the vertex of $G^{*}$ that subdivides $xy$. We next show that there are no edges among vertices of $f(E(G))$. If there is such an edge, the $t$-transitivity of $G$ allows us to assume that $H$ has an edge $f(e_{0})f(e_{2})$ for some edge $e_{2}$ of $G$. As before, the automorphisms of $G$ that fix $e_{0}$ carry $e_{2}$ to at least three other edges of $G$. Since these automorphisms extend to $H$, the vertex $f(e_{0})$ is adjacent to at least four vertices of $H$, again contradicting $H$ being a cubic graph.
%
%Thus the $|E(G)|$ vertices in $f(E(G))$ each require two more edges having one end in neither $V(G^{*})$ nor $f(E(G))$.  Therefore $H$ has at least $2|E(G)|/3 = |V(G)|$ vertices beyond those in $V(G^{*}) \cup f(E(G))$, so $|V(H)| \geq 2|V(G^{*})|$. Then Proposition \ref{mandm} implies $\mbox{mcsr}(G^{*}) = 2$.
%
%Finally, the conclusion $d = t - 1$ reached above implies $t \geq 3$ and Tutte has shown \cite{Tutte} that there are no cubic $t$-transitive graphs for $t>5$, so $t \in \{ 3, 4, 5 \}$. The Foster census of symmetric cubic graphs (\cite{Foster1} or \cite{Foster2}) contains for each of $t = 3, 4, 5$ exactly one graph with $2^{t}-2$ vertices: $K_{3, 3}$ for $t=3$, the Heawood graph for $t=4$, and the Tutte-Coxeter graph for $t=5$.  Each satisfies $d = t-1$. \end{proof}
%
%If we relax one of the hypotheses of Theorem \ref{symcubic} to $t \geq d = \mbox{diam}(L(G))$, the conclusion $\mbox{mcsr}(G^{*}) = 2$ can fail.  This is most easily seen with $G = K_{4}$, where $t=d=2$.  Here $\Aut(K_{4}^{*}) \cong \Aut(K_{4}) \cong {\cal S}_{4}$ and
%the graph $K_{4}^{*}$ has six deficient vertices. Under the action of $\Aut(K_{4}^{*})$ these divide into three blocks of size two: each block may be regarded as the subdivisions of opposite edges of a regular tetrahedron.  We take three new vertices, adjoining each to the vertices of a block.  A fourth new vertex is adjoined to the previous three, giving $\mbox{mcsr}(K_{4}^{*}) = 7/5$.
%
%A more interesting example, with $t=d=3$, is the Petersen graph $P$. The following implies $\mbox{mcr}(P^{*}) = \mbox{mcsr}(P^{*}) = 6/5$.
%
%%\noindent The 3-dimensional cube {\boldmath $Q_{3}$}. The graph $Q_{3}^{*}$ has twelve deficient vertices. Under the action of $\Aut(Q_{3}^{*})$, the %only nontrivial blocks of deficient vertices having size at most three are pairs of subdivisions of opposite edges of the cube.  We take six new %vertices, each adjoined to such a pair.  We can complete those vertices by joining them in pairs, where each pair covers the subdivisions of four %parallel edges of the cube. Thus $\mbox{mcsr}(Q_{3}^{*}) = 13/10$. \vspace{.2in}
%
%\begin{example}  \label{kneser}
%For $k \geq 2$, let $R_{k}$ denote the Kneser graph $KG(3k-1, k)$. (Thus $R_{2}$ is isomorphic to the Petersen graph.) Then
%\[ \mbox{mcr}(R_{k}^{*}) = \mbox{mcsr}(R_{k}^{*}) = \frac{2}{1 + \frac{2}{\binom{2k-1}{k}}}. \]
%\end{example}
%
%\begin{proof}
%By the definition of Kneser graph, the vertices of $R_{k}$ are the $k$-element subsets of $\{1, \ldots, 3k-1 \}$. Two vertices are adjacent if they are disjoint, so $R_{k}$ is regular with degree $\binom{2k-1}{k}$ and has $\frac{1}{2}\binom{3k-1}{k}\binom{2k-1}{k}$ edges.  Thus $R_{k}^{*}$ has $\binom{3k-1}{k} + \frac{1}{2}\binom{3k-1}{k}\binom{2k-1}{k}$ vertices, of which $\frac{1}{2}\binom{3k-1}{k}\binom{2k-1}{k}$ are deficient, each of deficiency $\binom{2k-1}{k} - 2$.
%
%We may label each deficient vertex of $R_{k}^{*}$ with the set of $k-1$ indices not occurring in either vertex of the edge of $R_{k}$ that it subdivides. There are then $\binom{3k-1}{k-1}$ labels, each occurring on $\frac{1}{2}\binom{2k}{k}$ vertices of $R_{k}^{*}$. As $\frac{1}{2}\binom{2k}{k} = \binom{2k-1}{k}$, we can make a compact regularization $H(k)$ of $R_{k}^{*}$
%as follows. For each label $L$, take new vertices $v_{L, i}$ for $1 \leq i \leq \binom{2k-1}{k} - 2$ and connect each $v_{L, i}$ to all vertices of $R_{k}^{*}$ with label $L$. This completes all vertices of $R_{k}^{*}$ and no two new vertices are adjacent, so $H(k)$ is a \mcr.
%
%As shown in \cite[Corollary 7.8.2]{Godsil}, $\Aut(R_{k})$ may be identified with the symmetric group ${\cal S}_{3k-1}$, acting in the natural way on the vertices of $R_{k}$. We may also identify $\Aut(R_{k}^{*})$ with ${\cal S}_{3k-1}$.  For $\theta \in \Aut(R_{k}^{*})$ and a deficient vertex $v$ of $R_{k}^{*}$ with label $L$, the vertex $\theta(v)$ has label $\theta(L)$. Thus we may extend $\theta$ to an automorphism $\Theta$ of $H(k)$ by setting $\Theta(v_{L, i}) = v_{\theta(L), i}$ for all $L$ and $i$, so $H(k)$ is a \mcsr\ of $R_{k}^{*}$.
%
%Finally, the index claimed for $H(k)$ follows from the fact that the number $N$ of vertices added to $R_{k}^{*}$ satisfies $N  \binom{2k-1}{k} = \frac{1}{2}\binom{3k-1}{k}\binom{2k-1}{k}  \left[\binom{2k-1}{k} - 2 \right]$.
%\end{proof}
%
%%\noindent The Kneser graph {\boldmath $KG_{5, 2}$}. (Also known as the Petersen graph and as the odd graph $O_{3}$.) The graph $KG_{5, 2}^{*}$ has %fifteen deficient vertices. The vertex set of $KG_{5, 2}$ may be seen as the set of two-element subsets of $\{ 1, 2, 3, 4, 5 \}$; two vertices are %adjacent if disjoint. We may label each subdivision vertex $w$ in $KG_{5, 2}^{*}$ with the unique index in $\{ 1, \ldots, 5 \}$ that does not appear %in either of the vertices of $KG_{5, 2}^{*}$ adjacent to $w$.  Each index is then the label of 3 deficient vertices, which we now join to a new %vertex. As $\Aut(KG_{5, 2}^{*})$ may be identified with the symmetric group ${\cal S}_{5}$, acting in the natural way on subsets of $\{ 1, \ldots, 5 %\}$, these five new vertices give a \mcsr\ of $KG_{5, 2}^{*}$.  Its size is $6/5$.  \vspace{.2in}

These examples represent occasionally clever uses of combining Erd\H{o}s-Kelly with knowledge of a graph's automorphism group, but they do not seem particularly atypical.  We have yet to find any examples of connected graphs that require constructions with indices higher than 2, which leads us to the following.

\begin{guess}
For any connected graph $G$, $\mbox{mcsr}(G) \leq 2$.
\end{guess}

Moreover, if we follow Shastri's lead and allow ourselves the option of increasing the maximum degree to achieve regularity we need to double the order at most:

\begin{theorem}
Every graph $G$ on $n$ vertices admits a symmetric regularization $H$ on $2n$ vertices with regularity $n-1$.
\end{theorem}

\begin{proof}
Apply the construction given before Proposition \ref{vertedges} to $G$ with the balanced predicate $Q(x, y)$ being ``$x$ is neither equal nor adjacent to $y$''.
%Construct $H$ by taking two copies $G_1, G_2$ of $G$ and adding the edges $u_1v_2$ where $u_1\in V(G_1), v_2\in V(G_2)$ precisely when $u,v\in V(G)$ %are distinct and nonadjacent.
By Proposition \ref{vertedges}, any automorphism of $G$ extends naturally to an automorphism of $H_{Q}$, which is clearly $(n-1)$-regular.
\end{proof}

Of course if $G$ contains a ``mastermind'' vertex with degree $n-1$ then this regularization is also compact.

\begin{thebibliography}{9}

\bibitem{AEH} J. Akiyama, H. Era, and F. Harary, Regular graphs containing a given graph, \textit{Elem. Math.} {\bf 38}(1983), no. 1, 15--17.

\bibitem{Biggs} N. Biggs, \textit{Algebraic Graph Theory}, Second edition, Cambridge University Press, Cambridge, 1993.

\bibitem{CL} G. Chartrand and L. Lesniak, \textit{Graphs and Digraphs}, Fourth edition, Chapman \& Hall/CRC, Boca Raton, 2005.

\bibitem{EK1} P. Erd\H{o}s and P. Kelly, Mathematical notes: The minimal regular graph containing a given graph,  \textit{Amer. Math. Monthly} {\bf 70}(1963), no. 10, 1074--1075.

\bibitem{EK2} P. Erd\H{o}s and P. Kelly, The minimal regular graph containing a given graph, in \textit{A seminar on graph theory}, 65--69, Holt, Rinehart and
    Winston, New York, 1967.

\bibitem{ER} P. Erd\H{o}s and A. R\'enyi, Asymmetric graphs, \textit{Acta Math. Acad. Sci. Hungarica} {\bf 14}(1963), 295--315.

\bibitem{evans} A. B. Evans, D. A. Narayan, and J. Urick, Representations of graphs modulo $n$: some problems,  \textit{Bull. Inst. Combin. Appl.} {\bf 56}(2009), 85--97.

\bibitem{Foster1} I.Z. Bouwer, W.W. Chernoff, B. Monson and Z. Star, \textit{The Foster Census: R. M. Foster's census of connected symmetric trivalent graphs}, Charles Babbage Research Centre, Winnipeg, 1988.

\bibitem{Foster2} http://school.maths.uwa.edu.au/$\sim$gordon/remote/foster/

%\bibitem{Godsil} C. Godsil and G. Royle, \textit{Algebraic Graph Theory}, Springer-Verlag, New York, 2001.

%\bibitem{Hea} http://mathworld.wolfram.com/HeawoodGraph.html

\bibitem{HPW} P. Hamburger, A. Por, and M. Walsh, Kneser representations of graphs, \textit{SIAM J. Discrete Math.} {\bf 23}(2009), no. 2, 1071--1081.

\bibitem{Konig} D. K\"{o}nig, \textit{Theorie der endlichen und unendlichen Graphen},  Akademische Verlagsgesellschaft, Leipzig, 1936.

\bibitem{Shastri} A. Shastri, Minimal regular graph containing a given graph,  \textit{Appl. Math. Lett.} {\bf 5}(1992), no. 1, 3--5.

\bibitem{Tutte} W. Tutte, A family of cubical graphs, \emph{Proc. Cambridge Philos. Soc.} {\bf 43}(1947), 459--474.

%\bibitem{Tcox} http://mathworld.wolfram.com/LeviGraph.html

\end{thebibliography}

\appendix
\section{Some proofs}

%What follows is intended for the referees, not for publication.

\begin{proof} (of Theorem \ref{gridthm})
We will denote the vertices of $P_{n} \times P_{k}$ by ordered pairs $(i, j), 1 \leq i \leq n, 1 \leq j \leq k$\,; the vertex $(i, j)$ is adjacent to those vertices $(i \pm 1, j \pm 1)$ that are defined.

Here $\Sigma = 4 \cdot 2 + 2(n-2) + 2(k-2) = 2(n+k)$ and $\Delta = 4$.

Condition (A) of Theorem \ref{erdk} implies $m(P_{n} \times P_{k}) \geq \lceil \Sigma/\Delta \rceil$, so to prove the theorem it suffices to add $\lceil \Sigma/\Delta \rceil$ vertices and appropriate edges to $P_{n} \times P_{k}$ and thereby produce a compact symmetric regularization $H$ of $P_{n} \times P_{k}$. Note that when $n \neq k$, $\Aut(P_{n} \times P_{k}) \cong \zah_{2} \times \zah_{2}$ is the group of symmetries of a rectangle, and $\Aut(P_{n} \times P_{n})$ is isomorphic to the dihedral group of order 8, which is the group of symmetries of a square.  Throughout the remainder of the proof, let $\theta$ denote an arbitrary automorphism of $P_{n} \times P_{k}$.

We start with $\lfloor n/2 \rfloor + \lfloor k/2 \rfloor -2$ new vertices: for each $j$, $2 \leq j \leq \lfloor k/2 \rfloor$, add a new vertex whose neighborhood in $P_{n} \times P_{k}$ is $T_{j} = \{ (1, j), (1, k-j), (n, j), (n, k-j) \}$, and for each $i$, $2 \leq i \leq \lfloor n/2 \rfloor$, add a new vertex whose neighborhood in $P_{n} \times P_{k}$ is  $ S_{i} = \{ (i, 1), (n-i, 1), (i, k), (n-i, k) \}$. If $n \neq k$ then each $T_{j}$ and each $S_{i}$ is an orbit of $V(P_{n} \times P_{k})$ under the action of $\Aut(P_{n} \times P_{k})$ and thus is fixed setwise by $\theta$. If $n = k$ then for each $i$, $2 \leq i \leq \lfloor n/2 \rfloor$, $\{T_{i}, S_{i} \}$ is permuted by $\theta$.

Completing $H$ depends on the parities of $n$ and $k$.

If $n \equiv k \beem{2}$, we add two more vertices, each with neighborhood $C = \{ (1, 1), (n, \\ 1), (1, k), (n, k) \}$ in $P_{n} \times P_{k}$. If $n$ and $k$ are odd, we also add a vertex with neighborhood $M = \{ (1, (k+1)/2), (n, (k+1)/2), ((n+1)/2, 1), ((n+1)/2, k) \}$ in $P_{n} \times P_{k}$. Here $\theta(C) = C$, $\theta(M) = M$, and the total number of new vertices is $(n+k)/2 = \Sigma/\Delta$.

If $n \not \equiv k \beem{2}$, we may assume without loss of generality that $n$ is odd.  We complete $H$ by adding three more vertices. The first vertex has neighborhood $C$ in $P_{n} \times P_{k}$. Then add a second vertex with neighborhood $L = \{ (1, 1), ((n+1)/2, 1), (n, 1) \}$ in $P_{n} \times P_{k}$ and a third vertex with neighborhood $ R = \{ (1, k), ((n+1)/2, k), (n, k) \}$ in $P_{n} \times P_{k}$, and connect the second and third vertices. Here $\theta$ permutes $\{ L, R \}$ and the total number of new vertices is $(n+k+1)/2 = \lceil \Sigma/\Delta \rceil$.

In each case, $H$ is a compact regularization of $P_{n} \times P_{k}$ with the desired number of vertices.  The automorphism $\theta$ induces a permutation of the neighborhoods in $P_{n} \times P_{k}$ of the added vertices, and the corresponding permutation of the set of added vertices gives an extension of $\theta$ to an automorphism of $H$. Thus $H$ is a symmetric regularization.
\end{proof}

\begin{proof} (of Theorem \ref{cylthm})
We will denote the vertices of $C_{n} \times P_{k}$ by ordered pairs $(i, j)$, where $i \in \zah_{n}$ and $j$ is an integer with $1 \leq j \leq k$\,; the vertex $(i, j)$ is adjacent to those vertices $(i \pm 1, j \pm 1)$ that are defined.

The graph $C_{n} \times P_{k}$ has $n(k-2)$ vertices of degree 4 and $2n$ vertices of degree 3, so $\Delta = 4$, $d_{C_{n} \times P_{k}} = 1$, $\Sigma = 2n$, and $\Sigma/\Delta = n/2$. The conditions of Theorem \ref{erdk} here become $m \geq n/2$, $m^{2} - 5m  + 2n \geq 0$, $m \geq 1$, and $(m + nk)4$ is even.  The minimum value of $m$ satisfying these is $\lceil n/2 \rceil$, establishing the value of $m(C_{n} \times P_{k})$, so we turn to $M(C_{n} \times P_{k})$.

Each deficient vertex of $C_{n} \times P_{k}$ requires only one new edge. By Lemma \ref{prin1}(b), this implies that for each new vertex $v$ of a \csr\ of $C_{n} \times P_{k}$, no vertex of $C_{n} \times P_{k}$ is contained in more than one image of $N_{G}(v)$ under the automorphisms of $C_{n} \times P_{k}$.  That is, each $N_{G}(v)$ is a \emph{block} of the action of Aut($G$) on the set of deficient vertices of $C_{n} \times P_{k}$:  the images of $N_{G}(v)$ form a partition of the orbit that contains them. This considerably restricts our search. Let $B$ be a block with $|B| \leq \Delta = 4$.

The automorphism group of $C_{n} \times P_{k}$ has order $4n$, and is isomorphic to the product of a dihedral group of order $2n$ (from the automorphism group of $C_{n}$) and a $\zah_{2}$ (from the automorphism group of $P_{n}$).  The second factor yields $\sigma \in \Aut(C_{n} \times P_{k})$ defined by $\sigma(h, l) = (h, k+1-l)$.  From the first factor, for each $i \in \zah_{n}$, there is $\phi_{i} \in \Aut(C_{n} \times P_{k})$ defined by $\phi_{i}(h, l) = (2i-h, l)$.

A useful fact: For any $(i, j) \in B$, since $\phi_{i}(i, j) = (i, j)$, necessarily $\phi_{i}(B)~=~B$.

This fact implies that blocks of size 4 exist if and only if $n$ is even, in which case the sets $F_{i} = \{ (i, 1), (i, k), (i+(n/2), 1), (i+(n/2), k) \}$, $i = 1, \ldots, n/2,$ are four-blocks forming a partition of $D$. We can then make these the neighborhoods in $C_{n} \times P_{k}$ of $n/2$ new vertices.  The resulting graph is a compact regularization $H$ of $C_{n} \times P_{k}$; since each new vertex has all neighbors in $C_{n} \times P_{k}$, no smaller compact regularization is possible.  Any automorphism $\theta$ of $C_{n} \times P_{k}$ induces a permutation of $\{F_{i} \mbox{ : } 1 \leq i \leq n/2 \}$, which gives a permutation of the new vertices, thus defining an extension of $\theta$ to $H$, so $H$ is symmetric.

Assume then that $n$ is odd, so no four-block of the action of $\Aut(C_{n} \times P_{k})$ on $D$ exists.  We look for three-blocks; using the $\phi_{i}$'s as before, we see that three-blocks exist if and only if $n$ is divisible by 3, in which case the sets $E_{i,1} = \{ (i, 1), (i + (n/3), 1), (i+(2n/3), 1) \}$ and $E_{i,k} = \{ (i, k), (i + (n/3), k), (i+(2n/3), k) \}$, $i = 1, \ldots, n/3,$ are three-blocks forming a partition of $D$. For each $i$, $1 \leq i \leq n/3$, we take a vertex $v_{i, 1}$ with neighborhood $E_{i, 1}$ in $C_{n} \times P_{k}$ and a vertex $v_{i, k}$ with neighborhood $E_{i, k}$ in $C_{n} \times P_{k}$, and join $v_{i, 1}$ and $v_{i, k}$.  The result is a compact regularization $H$ of $C_{n} \times P_{k}$, and it has minimum order since no new vertex can cover more than three vertices of $C_{n} \times P_{k}$.

For $i = 1, \ldots, n/3$, $\sigma$ switches $E_{i, 1}$ and $E_{i, k}$, and for these $i$ and all $j \in \zah_{n}$,
$\phi_{j}(E_{i, g}) = E_{2j-i, g}$ for $g \in \{1, k \}$. Thus we can extend these automorphisms to $H$ as follows: $\overline{\sigma}$ switches  $v_{1, 1}$ and $v_{i, k}$ for all $i \in \zah_{n}$, and $\overline{\phi_{j}}(v_{i, g}) = v_{2j-i, g}$ for all $j \in \zah_{n}$ and $i=1, \ldots, n/3$ in $\zah_{n}$. As $\sigma$ and the $\phi_{i}$'s generate $\Aut(C_{n} \times P_{k})$, this shows $H$ is symmetric as a regularization of $G$.

Finally, assume that $n$ is divisible by neither 2 nor 3. Then the largest blocks possible are two-blocks, and the sets $Z_{i} = \{ (i, 1), (i, k) \}$, $1 \leq i \leq n$, are two-blocks forming a partition of $D$. For each $i \in \zah_{n}$, we may take a vertex $t_{i}$ adjacent to the vertices of $Z_{i}$ and also to $t_{i-1}$ and $t_{i+1}$.  The resulting graph is a compact regularization of $C_{n} \times P_{k}$; it is isomorphic to $C_{n} \times C_{k+1}$ and thus is visibly a symmetric regularization.  Since no new vertex can cover more than two vertices of $C_{n} \times P_{k}$, it has minimum order.
\end{proof}

The following theorem establishes the claim in the last sentence of the paragraph following Theorem \ref{cylthm}.

\begin{thma}  \label{symcubic}
Let $G$ be a connected cubic $t$-transitive graph for some integer $t \geq 1$. If $t > d = \mbox{diam}(L(G))$ then $t = d + 1$, $|V(G)| = 2^{t} - 2$, $\mbox{mcsr}(G^{*}) = 2$, and $G$ is isomorphic to one of $K_{3, 3}$, the Heawood graph, and the Tutte-Coxeter graph.
\end{thma}

\begin{proof}
Fix an edge $e$ of $G$ and for $i = 0, 1, \ldots, d = \mbox{diam}(L(G))$, let $S_{i}$ denote the set of edges at distance $i$ from $e$. Let $G'$ be the subgraph of $G$ induced by $\cup_{i=0}^{t-2}S_{i}$.  Since $G$ is $t$-transitive, \cite[Proposition 17.2]{Biggs} says that the girth $g$ of $G$ is at least $2(t-1)$, which implies $G'$ is a tree.  As $G$ is cubic, induction on distance from $e$ shows $|S_{i}| = 2^{i+1}$ for $1 \leq i \leq t-2$. Thus $G'$ has $2^{t-1}$ vertices of degree one, each of which is incident in $G$ to one edge of $S_{t-2}$ and two edges of $S_{t-1}$. To count $S_{t-1}$, we require the following.

Claim. No vertex of $G$ is incident to three edges of $S_{t-1}$.

Proof of claim: Suppose there is such a vertex, say $x$, with edges $w_{1}x$, $w_{2}x$, $w_{3}x \in S_{t-1}$. Each $w_{i}x$ is the last edge in a $t$-arc $A_{i}$ whose first edge is $e = \{y, z\}$. As there are three edges incident at $x$ and only two ends of $e$, at least two $A_{i}$'s must have the same initial 1-arc; we may assume that for $j = 2, 3$, $A_{j} = [y_{1} = y, z, y_{j}, \ldots]$.

If $A_{1}$ also began with $y_{1}$, then since $\deg z = 3$ we would have two $(t-2)$-arcs with the same initial vertex ending in $x$, and these would be distinct as they would pass through different $w_{i}$'s. This would imply $g \leq 2t-4$, a contradiction.
Thus $A_{1} = [z, y_{1}, \ldots]$.

As $G$ is $t$-transitive, there is an automorphism $\theta$ of $G$ with $\theta(A_{2}) = A_{1}$. Then $\theta(w_{2}) = w_{1}$ so $\theta(w_{3}) = w_{j}$ for some $j \in  \{ 2, 3 \}$. Omitting the end edges of $\theta(A_{3})$ gives a path of length $t-2$ from $y_{1}$ to $w_{j}$, and $A_{j}$ includes a path of length $t-1$ from $y_{1}$ to $w_{j}$. Together these imply the existence of a cycle of odd length at most $2t-3$, contradicting $g \geq 2(t-1)$. This completes the proof of the claim.

The claim implies that each edge in $S_{t-1}$ is incident at each end to one edge in $S_{t-2}$ and one edge in $S_{t-1}$. An edge in $S_{t-2}$ cannot be incident only to edges in $S_{t-1}$, so the subgraph of $G$ induced by $S_{t-1}$ is a disjoint union of cycles, with each vertex of each cycle incident in $G$ to one edge in $S_{t-2}$. It follows that $|S_{t-1}| = |S_{t-2}| = 2^{t-1}$. As $d \leq t-1$ we have accounted for all edges of $G$, and $d = t-1$. Then $|E(G)| = \sum_{i=0}^{t-1} |S_{i}| = 1 + \sum_{i=1}^{t-2} 2^{i+1} + 2^{t-1} = 3 \cdot 2^{t-1} - 3$. Since $G$ is a cubic graph, $|V(G)| = (2/3)|E(G)| = 2^{t} - 2$.

Let $H$ be a \csr\ of $G^{*}$. We first show that each vertex in $H$ but not $G^{*}$ is adjacent to at most one vertex of $G^{*}$.  If not, then since $G$ is $t$-transitive we may assume that the vertex $v_{0}$ that subdivides edge $e_{0} = e$ of $G$ and the vertex $v_{1}$ that subdivides another edge $e_{1}$ of $G$ are adjacent to a vertex $w$ of $H$. For some $i$, $1 \leq i \leq t-1$, the distance from $e_{0}$ to $e_{1}$ in $L(G)$ is $i$, and we have shown $|S_{i}| \geq 4$. Then since $G$ is $t$-transitive, the automorphisms of $G$ that fix $e_{0}$ carry $e_{1}$ to at least three other edges of $G$. Thus if $B$ is a block of the action of $\mbox{Aut}(G^{*})$ on $V(G^{*})$ and $v_{0}, v_{1} \in B$ then $|B| \geq 5$. But then $|N_{G^{*}}(w)| \geq 5$, contrary to $H$ being a cubic graph.

It follows that we may define a one-to-one function $f: E(G) \rightarrow (V(H) \setminus V(G^{*}))$ by saying $f(xy)$ is the unique vertex of $H$ but not $G^{*}$ adjacent to the vertex of $G^{*}$ that subdivides $xy$. We next show that there are no edges among vertices of $f(E(G))$. If there is such an edge, the $t$-transitivity of $G$ allows us to assume that $H$ has an edge $f(e_{0})f(e_{2})$ for some edge $e_{2}$ of $G$. As before, the automorphisms of $G$ that fix $e_{0}$ carry $e_{2}$ to at least three other edges of $G$. Since these automorphisms extend to $H$, the vertex $f(e_{0})$ is adjacent to at least four vertices of $H$, again contradicting $H$ being a cubic graph.

Thus the $|E(G)|$ vertices in $f(E(G))$ each require two more edges having one end in neither $V(G^{*})$ nor $f(E(G))$.  Therefore $H$ has at least $2|E(G)|/3 = |V(G)|$ vertices beyond those in $V(G^{*}) \cup f(E(G))$, so $|V(H)| \geq 2|V(G^{*})|$. Since $d_{G^{*}} = 1$, Corollary \ref{boundmcsr} implies $\mbox{mcsr}(G^{*}) \leq 2$, so $\mbox{mcsr}(G^{*}) = 2$.

Finally, the conclusion $d = t - 1$ reached above implies $t \geq 3$ and Tutte has shown \cite{Tutte} that there are no cubic $t$-transitive graphs for $t>5$, so $t \in \{ 3, 4, 5 \}$. The Foster census of symmetric cubic graphs (\cite{Foster1} or \cite{Foster2}) contains for each of $t = 3, 4, 5$ exactly one graph with $2^{t}-2$ vertices: $K_{3, 3}$ for $t=3$, the Heawood graph for $t=4$, and the Tutte-Coxeter graph for $t=5$.  Each satisfies $d = t-1$. \end{proof}



\end{document}