Upper bounds for the regularity of powers of edge ideals of graphs
Let $G$ be a finite simple graph and $I(G)$ denote the corresponding edge ideal. In this paper, we obtain upper bounds for the Castelnuovo-Mumford regularity of $I(G)^q$ in terms of certain combinatorial invariants associated with $G$. We also prove a weaker version of a conjecture by Alilooee, Banerjee, Beyarslan and Hà on an upper bound for the regularity of $I(G)^q$ and we prove the conjectured upper bound for the class of vertex decomposable graphs. Using these results, we explicitly compute the regularity of $I(G)^q$ for several classes of graphs.
\section{Introduction}
Let $I$ be a homogeneous ideal of a polynomial ring 
$R = \K[x_1,\ldots,x_n]$ over a field $\K$ with usual grading.
In \cite{BEL91}, Bertram, Ein and Lazarsfeld  
have initiated  the study of the Castelnuovo-Mumford regularity of $I^q$
as  a function of $q$ by  proving that if $I$ is the defining ideal of a smooth complex 
projective variety, then $\reg(I^q)$ is bounded by a linear function of $q$. 
Then, Chandler \cite{Cha97} and Geramita, Gimigliano and Pitteloud \cite{GGP95} proved that
if $\dim(R/I)\leq 1$, then $\reg(I^q) \leq q.\reg(I)$ for all $q\geq 1$. 
However, Swanson \cite{Swa97} proved that there exists $k \geq 1$ such that
for all $q \geq 1$, $\reg(I^q)\leq kq$. Thereafter, Cutkosky, Herzog and Trung, \cite{CHT}, 
and independently Kodiyalam \cite{vijay}, proved that for a homogeneous ideal 
$I$ in a polynomial ring,  $\reg(I^q)$ is a linear 
function for $q \gg 0$ i.e., 
there exist non negative integers $a$ and $b$ depending on $I$ such that
$\reg(I^q)=aq+b \text{ for all $q \gg 0$}.$
While the coefficient $a$ is well-understood (\cite{CHT}, \cite{vijay}, \cite{TW}), 
the free constant $b$ and the stabilization index $q_0=\min\{q' \mid \reg(I^q)=aq+b, 
\text{ for all } q \geq q'\}$ are quite mysterious.
Therefore, the attention has been to identify classes for which the linear
polynomial can be computed or bounded using invariants associated to $I$.
There have been some attempts on computing the free constant and stabilization index
for several class of ideals. For instance, if $I$  is a equigenerated homogeneous ideal, then 
$b$ is related to the regularity of fibers of certain projection map 
(see for example, \cite{Romer2001}). If
$I$ is $(x_1,\ldots,x_n)$-primary, then $q_0$ can be related to partial
regularity of the Rees algebra of $I$ (see for example, \cite{Berle}).
In this paper, we study the regularity
of powers of edge ideals associated to finite simple graphs.

Let $G$ be a finite simple graph on the vertex set $\{x_1, \ldots,
x_n\}$ and $I(G) := (\{x_ix_j \mid \{i,j\} \in E(G)\}) \subset \K[x_1,
\ldots, x_n]$ be the edge ideal corresponding to the graph $G$.
It is known that
$\reg(I(G)^q) = 2q + b$ for some $b$ and $q \geq q_0$. 
There are very few classes of graphs for which $b$ and $q_0$ are known. We
refer the reader to \cite{BBH17} and the references cited there for a
review of results in the literature in this direction.
While the aim is to obtain the linear polynomial corresponding to
$\reg(I(G)^q)$, it seems unlikely that a single combinatorial invariant
will represent the constant term for all graphs. This naturally give
rise to two directions of research. One, to obtain linear polynomials
for particular classes of graphs. Two, to obtain upper and
lower bounds for $\reg(I(G)^q)$ using combinatorial invariants
associated to the graph $G$. It was proved by Beyarslan, H\`a and Trung that $2q + \nu(G) -
1 \leq \reg(I(G)^q)$ for all $q \geq 1$, where $\nu(G)$ denotes the
induced matching number of $G$, \cite{selvi_ha}. In \cite{jayanthan},
the authors along with Narayanan proved that for a bipartite graph
$G$, $\reg(I(G)^q) \leq 2q + \cochord(G) - 1$ for all $q \geq 1$,
where $\cochord(G)$ denote the co-chordal cover number of $G$. 
There is no general upper bound known for powers of edge ideals of
arbitrary graphs. Therefore, one may ask:
\begin{enumerate}
 \item[Q1.] Does there exist a graph invariant of $G$, say $\rho(G)$, such
   that $\reg(I(G)^q) \leq 2q + \rho(G)$ for all $q \geq 1$?
 \item[Q2.] Can one obtain the linear polynomial corresponding to
   $\reg(I(G)^q)$ for various classes of graphs?
\end{enumerate}
This paper evolves around these two questions.

The first main result of the paper answers Question Q1. 
H\`a and Woodroofe
\cite{HaWood} defined an invariant in terms of star
packing, denoted by $\zeta(G)$ (see Section \ref{reg-pow} for
definition), and proved that $\reg(I(G)) \leq \zeta(G) + 1$.  In this
paper, we extend H\'a and Woodroofe's bound to include all powers of
$I(G)$. We prove:
\vskip 2mm \noindent
\textbf{Theorem \ref{main-first}.}
{\em If $G$ is a graph, then for all $q \geq 1$,}
  $$\reg(I(G)^q) \leq 2q+\zeta(G)-1.$$
  
  
So far, in the literature, for the
classes of graphs for which the regularity of powers of edge ideals
have been computed, they satisfy either $\reg(I(G)^q) = 2q + \nu(G) -
1$ or $\reg(I(G)^q) = 2q + \cochord(G) - 1$, for all $q \geq 2$. In \cite{jayanthan}, the
authors raised the question whether there exists a graph $G$ with
\[2q + \nu(G) - 1 < \reg(I(G)^q) < 2q + \cochord(G) - 1, \text{ for $q \gg 0$.}\] As a
consequence of our investigation, we obtain a class of graphs which
attain the upper bound in Theorem \ref{main-first} and the above
strict inequalities are satisfied.

Another way of bounding the function $\reg(I(G)^q)$, than using
combinatorial invariants, is to relate it to the regularity of $G$
itself. It was conjectured by Alilooee, Banerjee, Beyarslan and H\`a,
\cite[Conjecture 7.11(2)]{BBH17}: 

\begin{conj}\label{ABBH-conj}
If $G$ is a graph, then for all $q \geq 1$,
$\reg(I(G)^q) \leq 2q + \reg(I(G)) - 2.$
\end{conj}
There are some classes of graphs for which this conjecture is known to
be true, see \cite{BBH17}. As a consequence of the techniques that we have
developed, we prove the conjecture with an additional hypothesis:
\vskip 2mm \noindent
\textbf{Theorem \ref{weak-conj1}.} {\em
Let $G$ be a graph. If every induced subgraph $H$ of 
$G$ has a vertex $x$ with $\reg(I(H \setminus N_H[x]))+1 \leq
\reg(I(H))$, then for all $q \geq 1$,}
\[
 \reg(I(G)^q) \leq 2q+\reg(I(G))-2.
\]


We then move on to study regularity of powers of vertex decomposable graphs.
A graph $G$ is said to be vertex decomposable if $\Delta(G)$ is a vertex decomposable, 
where $\Delta(G)$ denotes the independence complex of $G$ 
(see Section \ref{reg-vertex} for definition).
Vertex decomposability was first introduced by Provan and Billera \cite{ProvLouis},
in the case when all the maximal faces are of equal cardinality, and
extended to the arbitrary case by Bj\"orner and Wachs \cite{BjWachs}.
We have the chain of implications:
\begin{equation*}
 \text{vertex decomposable}\Longrightarrow \text{shellable} \Longrightarrow \text{sequentially
 Cohen-Macaulay,}
\end{equation*} 
where a graph $G$ is shellable if $\Delta(G)$ is a shellable
simplicial complex and $G$ is sequentially Cohen-Macaulay if $R/I(G)$
is sequentially Cohen-Macaulay.
Both the above implications are known to be strict.
Recently, a number of authors have
been interested in classifying or identifying vertex decomposable graphs $G$ in
terms of the combinatorial properties of $G$, \cite{BFH15, DochEng09, Wood2}. 
We prove the Conjecture \ref{ABBH-conj}, for vertex decomposable graphs.
\vskip 2mm \noindent
\textbf{Theorem \ref{upper-ver}.}
{\em Let $G$ be a vertex decomposable graph. Then for all
$q \geq 1$,} \[
             \reg(I(G)^q) \leq 2q+\reg(I(G))-2.
            \] 
As a consequence, we obtain the linear polynomial corresponding to
$\reg(I(G)^s)$ for several classes of graphs such as 
$C_5$-free vertex decomposable, chordal, sequentially Cohen-Macaulay bipartite
graphs and certain whiskered graphs.


Our paper is organized as follows. In the Section \ref{pre}, we collect the terminology
and preliminary results that are essential for the rest of the paper. 
We prove, in Section \ref{tech}, several technical lemmas which are
needed for the proof of our main results which appear in Sections \ref{reg-pow} and
\ref{reg-vertex}.

\section{Preliminaries}\label{pre}

Throughout this article, $G$ denotes a finite simple graph without
isolated vertices.
For a graph $G$, $V(G)$ and $E(G)$ denote the set of all
vertices and the set of all edges of $G$ respectively.
The \textit{degree} of a vertex $x \in V(G),$ denoted by 
$\deg_G(x),$ is the number of edges incident to $x.$
A subgraph $H \subseteq G$  is called \textit{induced} if for $u, v
\in V(H)$, $\{u,v\} \in
E(H)$ if and only if $\{u,v\} \in E(G)$.
For $\{u_1,\ldots,u_r\}  \subseteq V(G)$, let $N_G(u_1,\ldots,u_r) = \{v \in V (G)\mid \{u_i, v\} \in E(G)~ 
\text{for some $1 \leq i \leq r$}\}$
and $N_G[u_1,\ldots,u_r]= N_G(u_1,\ldots,u_r) \cup \{u_1,\ldots,u_r\}$. 
For $U \subseteq V(G)$, denote by $G \setminus U$ 
the induced subgraph of $G$ on the vertex set $V(G) \setminus U$.


A subset $X$ of $V(G)$ is called \textit{independent} if there is no edge $\{x,y\} \in E(G)$ 
for $x, y \in X$. 
A \textit{matching} in a graph $G$ is a subgraph consisting of pairwise disjoint edges. 
The largest size of a   matching in $G$ is called its matching number.
If the subgraph is an induced subgraph, the matching is an \textit{induced matching}. The largest size of an induced matching in $G$ is called its induced 
matching number and denoted by $\nu(G)$. 

The \textit{complement} of a graph $G$, denoted by $G^c$, is the graph on the same
vertex set in which $\{u,v\}$ is an edge of $G^c$ if and only if it is not an edge of $G$.
A graph $G$ is \textit{chordal} if every induced
cycle in $G$ has length $3$, and is co-chordal if the complement graph $G^c$ is chordal.
The co-chordal cover number, denoted $\cochord(G)$, is the
minimum number $n$ such that there exist co-chordal subgraphs
$H_1,\ldots, H_n$ of $G$ with $E(G) = \bigcup_{i=1}^n E(H_i)$.

One important tool in the study of regularity of powers of edge ideals
is even-connections.
We recall the concept of \textit{even-connectedness} from \cite{banerjee}. 

\begin{definition}\label{even_connected} Let $G$ be a graph. Two vertices $u$ and $v$ ($u$ may be same as $v$) are said to be even-connected with respect to an $s$-fold 
products $e_1\cdots e_s$, where $e_i$'s are edges of $G$, not necessarily distinct, if there is a path $p_0p_1\cdots p_{2k+1}$, $k\geq 1$ in $G$ such that:
\begin{enumerate}
 \item $p_0=u,p_{2k+1}=v.$
 \item For all $0 \leq l \leq k-1,$ $p_{2l+1}p_{2l+2}=e_i$ for some $i$.
 \item For all $i$, $ \mid\{l \geq 0 \mid p_{2l+1}p_{2l+2}=e_i \}\mid
   ~ \leq  ~ \mid \{j \mid e_j=e_i\} \mid$.
 \item For all $0 \leq r \leq 2k$, $p_rp_{r+1}$ is an edge in $G$.
\end{enumerate}
\end{definition}

\begin{remark} For convenience, we set an edge to be trivially
  even-connected, i.e., we get the even-connection by setting $k = 0$
  in the above definition.
\end{remark}
The following theorem due to Banerjee is used repeatedly throughout this paper:
\begin{theorem}\label{even_connec_equivalent}\cite[Theorem 6.1 and Theorem 6.7]{banerjee} Let $G$ be a graph with edge ideal
$I = I(G)$, and let $s \geq 1$ be an integer. Let $M$ be a minimal generator of $I^s$.
Then $(I^{s+1} : M)$ is minimally generated by monomials of degree 2, and $uv$ ($u$ and $v$ may
be the same) is a minimal generator of $(I^{s+1} : M )$ if and only if either $\{u, v\} \in E(G) $ or $u$ and $v$ are even-connected with respect to $M$.
 \end{theorem}

Polarization is a process that creates a squarefree monomial ideal (in
a possibly different polynomial ring) from a given monomial ideal,
\cite[Section 1.6]{Herzog'sBook}.
In this paper, we repeatedly use one of the important properties of the
polarization, namely:
\begin{corollary} \cite[Corollary 1.6.3(a)]{Herzog'sBook}\label{pol_reg} Let $I$ be a monomial 
ideal in $\K[x_1, \ldots, x_n].$ Then
$$\reg(I)=\reg(\widetilde{I}).$$
\end{corollary}

\section{Technical Lemmas}\label{tech}

In this section, we prove several technical results concerning the
graph associated with $(\widetilde{I(G)^{s+1} : e_1 \cdots e_s})$ and
some of its induced subgraphs. We begin by fixing the notation for the
most of our results. 

\begin{notation}\label{esetup}
Let $G$ be a graph with $V(G)=\{x_1,\ldots,x_n\}$ and $e_1,\ldots,e_s$, $s \geq 1,$ be some edges of $G$ which are not
necessarily distinct. 
By Theorem \ref{even_connec_equivalent} and Corollary \ref{pol_reg}, $\widetilde{(I(G)^{s+1}:e_1 \cdots e_s)}$ is a
quadratic squarefree monomial ideal in an appropriate polynomial ring. Let
$G'$ be the graph associated to $\widetilde{(I(G)^{s+1}:e_1 \cdots e_s)}$.
\end{notation}

One of the key ingredients in the proof of the main results is a new
graph, $G'$, obtained from a given graph $G$ by joining even-connected
vertices by an edge. Our main aim in this section is to get an upper
bound for regularity of certain induced subgraphs of $G'$ which in
turn will help us in bounding $\reg(I(G'))$. For this purpose, we need
to understand the structure of the graph $G'$ in more detail. First we
show that whiskers can be ignored while taking even-connections.
\begin{lemma}\label{even_obs2}
 Let $G$ be a graph with $e_1,\ldots,e_s \in E(G)$, $s \geq 1$ and $N_G(x)=\{y\}$. If $e_i=\{x,y\}$, for some $1 \leq i \leq s$,
 then $$(I(G)^{s+1}:e_1 \cdots e_s)=(I(G)^s:\prod_{j\neq i}e_j)$$
\end{lemma}
\begin{proof}
Clearly $(I(G)^s:\prod_{j\neq i}e_j) \subseteq (I(G)^{s+1}:e_1 \cdots e_s)$.
Let $uv \in (I(G)^{s+1}:e_1 \cdots e_s)$. For $k \geq 0$, let $(u=p_0) \cdots (p_{2k+1}=v)$
be an even-connection in $G$ with respect to  $e_1 \cdots e_s$. 
For $0 \leq r \leq k-1$, set $e_{i_r}=\{p_{2r+1},p_{2r+2}\}$. If $k=0$, then 
$uv \in (I(G)^s:\prod_{j\neq i}e_j)$. Assume $k\geq 1$.
If $e_i \neq e_{i_r}$, for all $0 \leq r \leq k-1$, then $u$ is an even-connected to $v$ in $G$
with respect to $e_1 \cdots e_{i-1}e_{i+1} \cdots e_s$. Suppose $e_i=e_{i_r}$, for some
$0 \leq r \leq k-1$. Since $N_G(x)=\{y\}$, $p_{2r+1}=p_{2r+3}$. Then
$(u=p_0)p_1 \cdots (p_{2r+1}=p_{2r+3})p_{2r+4} \cdots (p_{2k+1}=v)$ gives an even-connection
in $G$ with respect to $e_1 \cdots e_{i-1}e_{i+1} \cdots e_s$.
Hence $uv \in (I(G)^s:\prod_{j\neq i}e_j)$.
\end{proof}

The following result shows that if a vertex has no intersection with a
set of edges, then removing such a vertex and taking even-connection
with respect to the set of those edges commute with each other.


\begin{lemma}\label{single_vertex} Let the notation be as in \ref{esetup}.
If for $x \in V(G)$, $\{x\} \cap e_i=\emptyset$, for all $1 \leq i \leq s$, then 
$$I(G' \setminus x)=(\widetilde{I(G \setminus x)^{s+1}:e_1 \cdots e_s}).$$ 
\end{lemma}
\begin{proof}
Clearly $(I(G \setminus x)^{s+1}:e_1 \cdots e_s) \subseteq I(G'
\setminus x)$.  Suppose $\{u,v\} \in E(G' \setminus x)$. 
Let $(u=p_0)p_1 \cdots p_{2k}(p_{2k+1}=v)$ be an even-connection
in $G$ with respect to $e_1 \cdots e_s$.  Since $e_i \cap
\{x\}=\emptyset$, for all $1 \leq i \leq s$, $u$ is even-connected to
$v$ in $G \setminus x$ with respect to $e_1 \cdots e_s$. 
\end{proof}


The next result talks about new even-connections made out of a given
even-connection and the neighbors of some of the vertices in the
even-connection.
\begin{lemma}\label{even_obs} Let the notation be as in  \ref{esetup}.  
Suppose $(u=p_0)p_1 \cdots p_{2k}(p_{2k+1}=v)$ is an even-connection in $G$ with respect to
$e_1 \cdots e_s$, for some $k \geq 1$. If $\{w,p_i\} \in E(G')$, for some 
$0 \leq i \leq 2k+1$, then either $\{u,w\} \in E(G')$ or $\{v,w\} \in E(G')$.
 \end{lemma}
\begin{proof}
If $i=0,2k+1$, then we are done. 
Assume that $i=2j+1$, for some $j \geq 0$.
Let
$(w=q_0)q_1 \cdots (q_{2j+1}=p_i)$ be an even-connection with respect to $e_1 \cdots e_s$ 
in $G$. If $\{q_{2\alpha+1},q_{2\alpha+2}\}$ and $\{p_{2\beta+1},p_{2 \beta+2}\}$ do not have
a common vertex, for 
all $0 \leq \alpha \leq j-1$, $j \leq \beta \leq k-1$, then 
$(w=q_0)q_1 \cdots (q_{2j+1}=p_i)p_{i+1} \cdots (p_{2k+1}=v)$
is an even-connection with respect to $e_1 \cdots e_s$ in $G$.
Therefore, $wv \in I(G')$.
If $\{q_{2\alpha+1},q_{2\alpha+2}\}$ and $\{p_{2\beta+1},p_{2 \beta+2}\}$ 
have a common vertex,
for some $0 \leq \alpha \leq j-1$, $j \leq \beta \leq k-1$, then
by \cite[Lemma 6.13]{banerjee},
$w$ is  even-connected either to $u$ or to $v$ in $G$. 
Therefore either $wu\in I(G')$ or $wv \in I(G')$.
If $i = 2j+2$, then proof is similar.
\end{proof}




The following lemma, which throws more light into the structure of
$G'$, is very useful for the induction process.

\begin{lemma}\label{tech_lemma} Let the notation be as in  \ref{esetup}.
Let $y \in V(G)$ and $H=G \setminus N_G[y]$. 
If $\{e_1,\ldots,e_s\} \cap E(H) = \{e_{i_1},\ldots,e_{i_t}\}$ and $H'$ is the 
graph associated to $\widetilde{(I(H)^{t+1}:e_{i_1} \cdots e_{i_t})}$, then 
$G' \setminus N_{G'}[y]$ is an induced subgraph of $H'$.
In particular, $$\reg(I(G' \setminus N_{G'}[y])) \leq \reg(I(H')).$$
\end{lemma}

\begin{proof} 
Let $\{u,v\} \in E(G' \setminus N_{G'}[y])$. 
Let $(u=p_0)p_1 \cdots (p_{2k+1}=v)$
be an even-connection in $G$ with respect to $e_1 \cdots e_s$ for some
$k \geq 0$. If $p_i \in N_{G'}[y]$, for some $0 \leq i \leq 2k+1$, then by Lemma \ref{even_obs}, $y$
is even-connected either to $u$ or to $v$. This contradicts the
assumption that $\{u,v\} \in G' \setminus N_{G'}[y]$. Therefore, for
each $0 \leq i \leq 2k+1$, $p_i \notin N_{G'}[y]$. Hence $\{u,v\} \in E(H')$, which
proves that $G' \setminus N_{G'}[y]$ is a subgraph of $H'$.
If $a,b \in V(G' \setminus
N_{G'}[y])$ is such that $\{a,b\} \in E(H)$,
then $\{a,b\} \in E(G' \setminus N_{G'}[y])$. Hence 
$G' \setminus N_{G'}[y]$ is an induced subgraph of $H$.
The assertion on the regularity follows from \cite[Proposition
4.1.1]{sean_thesis}.  
\end{proof}

In the following results, we show that the even-connections in a
parent graph with respect to edges coming from an induced subgraph,
induces an even-connection in the induced subgraph.
\begin{lemma}\label{ind-reg}
Let $G$ be a graph and $H$ be an induced subgraph of $G$. If for any $e_1,\ldots,e_s \in E(H)$,
$s \geq 1$, then $H'$ is an induced subgraph of $G'$, where
$H'$ and $G'$ are the graph associated to $\widetilde{(I(H)^{s+1}:e_1 \cdots e_s)}$
and $\widetilde{(I(G)^{s+1}:e_1 \cdots e_s)}$ respectively. 
In particular, $$\reg(I(H')) \leq \reg(I(G')).$$
\end{lemma}
\begin{proof}
Let $\{a,b\} \in E(H')$. For some $k \geq 0$, let $(a=p_0)p_1 \cdots p_{2k}(p_{2k+1}=b)$ be an
even-connection in $G$ with respect to $e_1 \cdots e_s$. Since
$H$ is an induced subgraph of $G$ and $\{p_{2r+1},p_{2r+2}\} \in E(H)$, for all $0 \leq r \leq k-1$,
$(a=p_0)p_1 \cdots p_{2k}(p_{2k+1}=b)$ is an even-connection in $G$ with respect to 
$e_1 \cdots e_s$. Therefore, $\{a,b\}\in E(G')$. 
Hence $H'$ is the subgraph of $G'$.
As in the previous lemma, it can be seen that the subgraph is an induced subgraph.
\end{proof}


Let the notation be as in  \ref{esetup}. For some $1 \leq i \leq s$, set $e_i =
\{x,y\}$. We further explore the even-connections between $N_{G'}[y]$ and
$N_{G'}(x)$. If $(u=p_0)p_1\cdots p_{2k}(p_{2k+1}=y)$ ($u$ may be equal to $y$) be an even-connection in $G$ with respect 
to  $e_1 \cdots e_s$, for some $k \geq 0$, then there are three possibilities:
\begin{enumerate}
  \item $\{p_{2\lambda+1}, p_{2\lambda+2}\} \neq e_i$ for any $0 \leq
	\lambda \leq k-1$;
  \item There exists $0 \leq \lambda \leq k-1$ with $\{p_{2\lambda+1},
	p_{2\lambda+2}\} = e_i$ and  $p_{2\lambda+1} = y, p_{2\lambda+2} =
	x$;
  \item For some $0 \leq \lambda \leq k-1$, $p_{2\lambda+1}=x$ and $p_{2\lambda+2}=y$ whenever
  $\{p_{2\lambda+1},p_{2\lambda+2}\}=e_i$;
\end{enumerate}
Note that, fixing an even-connection between $u$ and $y$, $(1), (2)$
and $(3)$ are mutually exclusive. Let 
\begin{equation}\label{nota_nbd}
\begin{split}
  X_1=&~\Big \{u \in N_{G'}[y] \mid (u=p_0)p_1\cdots p_{2k}(p_{2k+1}=y)
  \text{ satisfies either (1) or (2)}\Big\};\\
 X_2=&~ \Big\{u \in (N_{G'}[y]) \setminus X_1 \mid (u=p_0)p_1\cdots p_{2k}(p_{2k+1}=y)
  \text{ satisfies (3)}\Big\}.
 \end{split}
\end{equation}
\begin{lemma}\label{even-lemma} Following the notation set above, let
  $E(G\setminus N_G[u,x]) \cap \{e_1, \ldots, e_s\} = \{e_{j_1},
  \ldots, e_{j_t}\}$ and $(G \setminus N_G[u,x])'$ denote the graph
  associated to $\widetilde{(I(G \setminus N_G[u,x])^{t+1}:e_{j_1} \cdots e_{j_t})}$.
\begin{enumerate}
 \item If $u \in X_1$, then $G' \setminus N_{G'}[u] \text{ is an
   induced subgraph of } (G \setminus N_{G}[u,x])'.$  In particular,
   $$\reg(I(G' \setminus N_{G'}[u]))\leq \reg(I((G \setminus N_{G}[u,x])')).$$
  \item Set $G_1'=G' \setminus X_1$. If $u \in X_2$, then $G_1'
	\setminus N_{G_1'}[u]$ is an induced subgraph of $(G \setminus
	N_{G}[u,x])'$. 
	$$\reg(I(G_1'\setminus N_{G_1'}[u]))\leq \reg(I((G \setminus N_{G}[u,x])')).$$
\end{enumerate} 
\end{lemma}
\begin{proof}
 (1) Set $H=G' \setminus N_{G'}[u]$ and $K=(G \setminus N_{G}[u,x])'$. Let
$\{a,b\} \in E(H)$ and $(a=q_0)q_1 \cdots (q_{2l+1}=b)$ be an
even-connection in $G$ with respect to $e_1 \cdots e_s$, for some $l \geq 0$. We show that
$\{a,b\} \in E(K)$. Note that by Lemma \ref{even_obs}, $q_i \notin N_{G'}[u]$, for all $0 \leq i \leq 2l+1$.
Suppose
$q_i \in N_{G}[x]$, for some $0 \leq i \leq 2k+1$. Since $u \in X_1$, then
$\{u,q_i\} \in E(G')$. By Lemma \ref{even_obs}, $u$ is an even-connected either to
$a$ or to $b$ in $G$ with respect to $e_1 \cdots e_s$. This is a contradiction to
$\{a,b\} \in E(H)$.
Therefore, $q_i \notin N_{G}[x]$, for all $0 \leq i \leq 2l+1$. Hence 
$a$ is even-connected to $b$ in $G \setminus N_G[u,x]$ with respect to
$e_{j_1} \cdots e_{j_t}$. Therefore, $\{a,b\} \in E(K)$. 
\vskip 1mm \noindent
$(2)$ Set $H=G_1' \setminus N_{G_1'}[u]$ and $K=(G \setminus
N_{G}[u,x])'$. Let $\{a,b\} \in E(H)$ and $(a=q_0)q_1 \cdots
(q_{2l+1}=b)$ be an even-connection in $G$ with respect to $e_1 \cdots
e_s$, for some $l \geq 0$.  If $\{p_{2\alpha+1},p_{2\alpha+2}\}$ and
$\{q_{2\beta+1},q_{2\beta+2}\}$ have a common vertex, for some $0 \leq
\alpha \leq k-1$, $0 \leq \beta \leq l-1$, then by \cite[Lemma
6.13]{banerjee}, $u$ is even-connected either to $a$ or to $b$ in
$G$ with respect to $e_1 \cdots e_s$. This is a contradiction to our
assumption that 
$\{a,b\} \in E(H)$. Therefore, for all $0 \leq \alpha \leq k-1$ and $0
\leq \beta \leq l-1$, $\{p_{2\alpha+1},p_{2\alpha+2}\}$ and
$\{q_{2\beta+1},q_{2\beta+2}\}$ do not have a common vertex.  Note
that by Lemma \ref{even_obs}, $q_i \notin N_{G'}[u]$, for all $0 \leq
i \leq 2l+1$.  Suppose $q_i \in N_{G}[x]$, for some $0 \leq i \leq
2l+1$. Since $u \in X_2$, there exists $0 \leq \lambda \leq k-1$ with
$p_{2\lambda+1}=x$  and $p_{2\lambda+2}=y$. Therefore,
$(p_{2k+1}=y)p_{2k} \cdots p_{2\lambda+1} p_{2\lambda+2}q_i$ is an
even-connection in $G$ with respect to $e_1 \cdots e_s$.  By Lemma
\ref{even_obs}, $y$ is even-connected either to $a$ or to $b$ in $G$
with respect to $e_1 \cdots e_s$. Since
for all $0 \leq \alpha \leq k-1$ and $0
\leq \beta \leq l-1$, $\{p_{2\alpha+1},p_{2\alpha+2}\}$ and
$\{q_{2\beta+1},q_{2\beta+2}\}$ do not have a common vertex,
either $a \in X_1$ or $b
\in X_1$.  This is a contradiction to our assumption that $\{a,b\} \in E(H)$.  Hence $q_i
\notin N_G[x]$, for all $0 \leq i \leq 2l+1$ so that $\{a,b\}$ is an
even-connection in $G \setminus N_{G}[u,x]$ with respect to
$e_{j_1}\cdots e_{j_t}$. Therefore $\{a,b\} \in E(K)$.

As in the previous lemma, it can be seen that the subgraphs
considered in (1) and (2) are induced subgraphs.
The assertion on the regularity in (1) and (2) follows from \cite[Proposition
4.1.1]{sean_thesis}.  
\end{proof}

\section{Regularity powers of graphs}\label{reg-pow}

In this section, we obtain a general upper bound for the regularity
powers of edge ideals of graphs. We first recall the
definition of the invariant $\zeta(G)$, introduced in \cite{HaWood}.

Let $v_1 \in V(G)$ be a vertex of degree at least $2$. If $G \setminus
N_G[v_1]$ does not have any vertex of degree at least $2$, then set
$\sigma = \{v_1\}$ and $H_1$ be the graph obtained by removing all the
isolated vertices of $G \setminus N_G[v_1]$. If there exists $v_2 \in
V(H_1)$ such that $\deg_{H_1}(v_2) \geq 2$, then set $\sigma = \{v_1,
v_2\}$ and $H_2$ be the graph obtained by removing the isolated
vertices of $H_1 \setminus N_{H_1}[v_2]$. Continuing like this, we
obtain $\sigma = \{v_1, \ldots, v_k\}$ such that $H_{k-1} \setminus
N_{H_{k-1}}[v_k]$ is a collection of disconnected edges, say $\{w_1,
\ldots, w_r\}$ and isolated vertices. Let $\PP = \{N_G[v_1],
\ldots, N_G[v_k]\} \cup \{w_1, \ldots, w_r\}.$ We call this $\PP$ a
\textit{star packing} of $G$ and set $\zeta_{\PP}(G) = k+r$. Define $$\zeta(G)
:= \max \Big\{\zeta_{\PP}(G) \mid \PP \text{ is a star packing of } G \Big\}.$$
For example, if $G = C_n$, cycle on $n$ vertices, then for any $x \in
V(G)$, $N_G[x]$ is a path on $3$ vertices and hence $G \setminus
N_G[x]$ is a path on $n-3$ vertices. A maximal star packing can
be obtained by successively taking out $N_G[x]$, where $x$ is the 
neighbour of a degree $1$ vertex. Therefore, if $n \equiv \{0,1\}(\text{mod }3)$,
then $\zeta(G) = \lfloor \frac{n}{3} \rfloor = \nu(G)$ and if $n
\equiv 2(\text{mod }3)$, then $\zeta(G) = \lfloor \frac{n}{3} \rfloor + 1 =
\nu(G) + 1$.


It may be noted that for a graph $G$, $\nu(G) \leq \zeta(G)$,
\cite{HaWood}. H\`a and Woodroofe proved:
\begin{theorem}\cite[Theorem 1.6]{HaWood} \label{reg-upper} Let $G$ be
 a graph. Then $$\reg(I(G)) \leq \zeta(G)+1.$$ 
\end{theorem}

It is easy to see that $\zeta(G)$ is at most the matching number of
$G$.  There are two general upper bounds known for the class of edge
ideals, namely, $\reg(I(G)) \leq \cochord(G) + 1$, \cite[Theorem
1]{russ} and $\reg(I(G)) \leq \text{min-max}(G) + 1$, \cite{ha_adam,
russ}, where min-max$(G)$ denotes the minimum number of a maximal
matching in $G$.  We would like to note here that the invariants
$\zeta(G)$, $\cochord(G)$ and min-max$(G)$ are not comparable in
general, as can be seen from the following examples.
\begin{example}\label{ex:incomparable}
Let $G=C_7$. Then one can see that the co-chordal subgraphs of
$G$ are paths with at most $3$ edges so that $\cochord(G)=3$. Also, one seen that 
$\zeta(G)=2$. Let $H$ be obtained from $C_4$ by attaching a pendant to
any of the vertices. 
It is easy to see that $\cochord(H)=1$ and $\zeta(H)=2$.

Let $G$ be the graph obtained by adding a pendant vertex each to two
vertices having a common neighbor in $C_6$. Then min-max$(G) = 2$ and
$\zeta(G) = 3$. If $H = C_4$, then it can be seen that min-max$(G) =
2$ while $\zeta(G) = 1$.
\end{example}

We now make an observation about the behaviour of the invariant
which is crucial in our inductive arguments.

\begin{obs}\label{inv-obs}
Let $x$ be a vertex of $G$ of degree at least $2$, then $\zeta(G \setminus
N_G[x]) + 1 \leq \zeta(G)$.
\end{obs}
\begin{proof}
Let $H = G \setminus N_G[x]$. Let $\PP'$ be a star packing of $H$ such
that $\zeta_{\PP'}(H) = \zeta(H)$. Then $\PP = \PP' \cup \{N_G[x]\}$
is a star packing of $G$. Thus, 
$\zeta(H) + 1 = \zeta_{\PP'}(H) + 1 = \zeta_{\PP}(G) \leq \zeta(G).$
\end{proof}

We first prove that for a given graph $G$ and edges $e_1, \ldots,
e_s$, the regularity of $G'$
is bounded above by one more than $\zeta(G)$.


\begin{theorem}\label{base-reg}
 If $G$ is a  graph, then for any 
 $e_1,\ldots,e_s \in E(G)$, $s \geq 1$
$$\reg(I(G)^{s+1}:e_1 \cdots e_s) \leq  \zeta(G)+1.$$
\end{theorem}
\begin{proof}
Let $G'$ be the graph associated to 
$\widetilde{(I(G)^{s+1}:e_1 \cdots e_s)}$ contained in an appropriate polynomial ring 
$R_1$.
  We prove the assertion by induction
on $s$. Suppose $s=1$.  
Set $e_1=\{x,y\}$. If either $\deg_G(x)=1$ or $\deg_G(y)=1$, then 
  by Lemma \ref{even_obs2}, $I(G')=I(G)$. Therefore by 
  Theorem \ref{reg-upper}, $\reg(I(G'))=\reg(I(G))\leq \zeta(G)+1$.

Suppose $\deg_G(x)>1$ and $\deg_G(y)>1$. Setting
$U=N_{G'}(y)=\{y_1,\ldots,y_r\}$ and
 $J=I(G')$, consider the exact sequences:
\begin{eqnarray}\label{main-exact-seq}
  0 & \longrightarrow & \frac{R_1}{(J : y_1)}(-1)
  \overset{\cdot y_1}{\longrightarrow} \frac{R_1}{J} \longrightarrow
  \frac{R_1}{(J , y_1)} \longrightarrow 0;\nonumber \\
 
 
 
& & \hspace*{1cm} \vdots\hspace*{5cm}\vdots \hspace*{3cm}\vdots \\ 
0 & \longrightarrow & \frac{R_1}{((J,
  y_1,\ldots,y_{r-1}):y_r)}(-1) 
\overset{\cdot y_r}{\longrightarrow}
\frac{R_1}{(J, y_1,\ldots,y_{r-1})} \longrightarrow
\frac{R_1}{(J, U)} \longrightarrow 0.\nonumber
\end{eqnarray}
 It follows from these exact sequences that
\[
  \reg(R_1/J)  \leq  \max \left\{
	\begin{array}{l}
	  \reg\left(\frac{R_1}{(J :y_1)}\right)+1,\ldots, 
		\reg\left(\frac{R_1}{(J,y_1,\ldots,y_{r-1}):y_r)}\right) + 1,~ 
		\reg\left(\frac{R_1}{(J,~U)}\right)
	  \end{array}\right\}.
\]
We now prove that each of the regularities appearing on the right hand
side of the above inequality is bounded above by $\zeta(G)$. 
 
Since $(J,U)$ corresponds to an induced subgraph of $G$, by \cite[Proposition
4.1.1]{sean_thesis} and Theorem \ref{reg-upper},
\begin{equation*}\label{case2:eq3}
\reg \left(\frac{R_1}{(J,U)}\right) \leq \reg \left(\frac{R}{I(G)}\right)\leq \zeta(G).
 \end{equation*}
Let the notation be as in Equation (\ref{nota_nbd}).
Since $N_{G'}(y)=N_G(y)$, $U \subseteq X_1$. 
Note that $x \in N_G(y)$ and $e_1 \cap E(G \setminus N_{G}[y_j,x])=\emptyset$, for any $y_j \in U$. Therefore,
we have
$$
\begin{array}{lcll}
   \reg((J:y_j)) & = &\reg(I(G' \setminus N_{G'}[y_j])) \leq  
   \reg(I(G \setminus N_{G}[y_j,x])) & \mbox{ (by Lemma \ref{even-lemma})}\\ 
  
   & \leq & \reg(I(G \setminus N_{G}[x]))\leq\zeta(G \setminus N_{G}[x])+1 \leq \zeta(G). & \mbox{ (by Observation 
   \ref{inv-obs}) }\\
   \end{array}
$$
Since $((J,y_1,\ldots,y_{j-1}):y_j)$
corresponds to an induced subgraph of $(J:y_j)$, it follows that
$$\reg \left( \frac{R_1}{((J,y_1,\ldots,y_{j-1}):y_j)}\right)+1 \leq 
\reg \left( \frac{R_1}{(J:y_j)}\right) +1\leq \zeta(G).$$

Therefore, 
$\reg\left( \frac{R_1}{J}\right) \leq \zeta(G).$

Suppose $s > 1$. Assume by induction that for any graph $G$ and for any $e_1,
\ldots, e_{s-1}\in E(G)$, $\reg(I(G)^s : e_1 \cdots e_{s-1}) \leq
\zeta(G) + 1$.

Let $G$ be a graph, $e_1, \ldots, e_s \in E(G), ~s\geq 2$.
For $1 \leq i \leq s$, let $e_i=\{a_i,b_i\}$. If for some $1 \leq j \leq s$, either
$\deg_G(a_j)=1$ or $\deg_G(b_j)=1$, then
by Lemma \ref{even_obs2},
$$\reg((I(G)^{s+1}:e_1 \cdots e_s))=\reg((I(G)^{s}:e_1 \cdots e_{j-1}e_{j+1} \cdots e_{s})) 
\leq \zeta(G)+1,$$
where the last inequality follows by induction hypothesis on $s$. 

Suppose
$\deg_G(a_i)>1$ and $\deg_G(b_i)>1$, for all $1 \leq i \leq s$.
Let $N_{G'}(b_s)=\{y_1,\ldots,y_p,z_1,\ldots,z_q\}$.  
Following the notation in Equation (\ref{nota_nbd}),
set $X_1=\{y_1,\ldots,y_p\}$,
$X_2=\{z_1,\ldots,z_q\}$ and $J=I(G')$. 
It follows from set of short exact sequences, similar to Equation
(\ref{main-exact-seq}), that
\[
  \reg(R_1/J)  \leq  \max \left\{
	\begin{array}{l}
	  \reg\left(\frac{R_1}{(J :y_1)}\right)+1, \ldots, \reg\left(\frac{R_1}{(J,X_1) : z_1}\right)+1,  
		\ldots, \\		
		\;\; \\
		\reg\left(\frac{R_1}{((J,X_1,z_1,\ldots,z_{q-1}):z_q)}\right) + 1,~ 
		\reg\left(\frac{R_1}{(J,X_1,X_2)}\right).
\end{array}\right.
\]
Now,
\[
  \begin{array}{llll}
\reg((J,X_1,X_2))& = & \reg(I(G' \setminus N_{G'}[b_s])) &
(\text{by \cite[Remark 2.5]{selvi_ha}}) \\
 & \leq&  \reg(I((G \setminus
 N_{G}[b_s])')) & (\text{by Lemma \ref{tech_lemma}}),
 \end{array}\]
 where  
 $E(G \setminus N_G[b_s]) \cap
 \{e_1,\ldots,e_s\}=\{e_{j_1},\ldots,e_{j_t}\}$ and $(G \setminus N_{G}[b_s])'$
 is the graph associated to $\widetilde{(I(G \setminus
   N_G[b_s])^{t+1}:e_{j_1} \cdots e_{j_t})}$.   
   Since $a_s \in N_G(b_s), e_s \notin E(G\setminus N_G[b_s])$ so that
   $t<s$. Hence by
 induction hypothesis on $s$ and Observation \ref{inv-obs}, we get
  $$\reg(I(G' \setminus N_{G'}[b_s])) \leq \reg(I((G \setminus N_{G}[b_s])')) \leq 
  \zeta(G \setminus N_{G}[b_s])+1 \leq \zeta(G).$$
Let $E(G \setminus N_G[y_i,a_s]) \cap
\{e_1,\ldots,e_s\}=\{e_{j_1},\ldots,e_{j_t}\}$ and $(G \setminus
N_G[y_i,a_s])'$ be the graph associated to 
  $\widetilde{(I(G \setminus N_G[y_i,a_s])^{t+1}:e_{j_1} \cdots
  e_{j_t})}$.
  For any $y_i \in X_1$, we have
  \[
	\begin{array}{llll}
	  \reg((J:y_i))=\reg(I(G' \setminus N_{G'}[y_i])) & \leq &
	  \reg(I((G \setminus N_G[y_i,a_s])')) & (\text{by Lemma
		\ref{even-lemma}}) \\		
	  & \leq & \zeta(G \setminus N_{G}[y_i,a_s])+1 & (\text{by
	  induction on } s) \\
	  & \leq & \zeta(G \setminus N_{G}[a_s])+1 
	   \leq  \zeta(G). & (\text{by Observation \ref{inv-obs}})
	\end{array}
  \]
Since $((J,y_1,\ldots,y_{i-1}):y_i)$
corresponds to an induced subgraph of $(J:y_i)$, it follows that
$$\reg(((J,y_1,\ldots,y_{i-1}):y_i)) \leq \reg(J:y_i)\leq \zeta(G).$$
 
Let $G_1'=G' \setminus X_1$. For any $z_i \in X_2$, we may conclude,
as done earlier, that 
\[\reg((J,X_1:z_i)) \leq \reg(I((G \setminus N_G[z_i,a_s])'))
\leq \zeta(G \setminus N_{G}[a_s])+1\leq \zeta(G).\]
 
Since $((J,X_1,z_1,\ldots,z_{i-1}):z_i)$
corresponds to an induced subgraph of $(J,X_1:z_i)$, it follows that
$$\reg(((J,X_1,z_1,\ldots,z_{i-1}):z_i)) \leq \reg(J,X_1:z_i)\leq \zeta(G).$$

Therefore
$\reg(J) \leq \zeta(G)+1.$
Hence, for any $e_1,\ldots,e_s \in E(G)$, $s \geq 1$,
$$\reg((I(G)^{s+1}:e_1 \cdots e_s)) \leq  \zeta(G)+1.$$
 \end{proof}
Now we prove an upper bound for the regularity of powers of edge
ideals of  graphs. 
 \begin{theorem}\label{main-first}
  If $G$ is a graph, then for all $q \geq 1$,
  $$\reg(I(G)^q) \leq 2q+\zeta(G)-1$$
 \end{theorem}
\begin{proof}
 We prove by induction on $q$. If $q=1,$ then the
 assertion follows from Theorem \ref{reg-upper}.
Assume that $q >1$. By applying \cite[Theorem 5.2]{banerjee} and using
induction, it is enough to prove that for edges $e_1, \ldots, e_q$ of
$G$, 
$\reg(I(G)^{q+1}:e_1 \cdots e_q) \leq \zeta(G))+1$ for all $q > 1$. 
This follows from  Theorem \ref{base-reg}.
\end{proof}



If $G_1$ and $G_2$ are graphs for which the linearity of $\reg(I(G_1)^s)$ and
$\reg(I(G_2)^s)$ are known for $s \geq s_1$ and $s \geq s_2$
respectively, then by \cite[Theorem 5.7]{nguyen_vu}, it is known that
$\reg(I(G_1 \coprod G_2)^s)$ is linear for $s \geq s_1+s_2$. Using
this result, we obtain a class of graphs for which the upper bound in
Theorem \ref{main-first} is attained.

\begin{proposition}\label{disjoint}
 For $p \geq 0,r > p$, let
$
  H=\left(\coprod_{i=1}^p C_{n_i}\right) \coprod \left(\coprod_{j=p+1}^rC_{n_j}\right), 
 $ where 
$n_1,\ldots,n_p \equiv 2(mod~3)$, $n_{p+1},\ldots,n_r \equiv
\{0,1\}(mod~3)$.
Then for all $q \geq 1$,
$$\reg(I(H)^q)=2q+\zeta(H)-1.$$ 
\end{proposition}
\begin{proof}
 It follows from 
\cite[Theorem 7.6.28]{sean_thesis} and \cite[Theorem 5.2]{selvi_ha}
that
\[
  \reg(I(C_n)) = \left\{\def\arraystretch{1.2}%
  \begin{array}{@{}c@{\quad}l@{}}
    \nu(C_n)+1 & \text{ if $n \equiv \{0,1\}~(mod~3),$}\\
    \nu(C_n)+2 & \text{ if $n \equiv 2~(mod~3),$}\\
  \end{array}\right.
\]
and that for all $q \geq 2$, $\reg(I(C_n)^q)=2q+\nu(C_n)-1.$
If $q=1$, then by \cite[Lemma 8]{russ}, we get $\reg(I(H))=\zeta(H)+1$. If $p = 0$, then
$H=(\coprod_{j=p+1}^rC_{n_j})$.
By  \cite[Theorem 5.7]{nguyen_vu},
$\reg(I(H)^q)=2q+\zeta(H)-1, \text{for all $q \geq 1$}.$

Suppose $p>0$. Set $H'=(\coprod_{j=p+1}^rC_{n_j})$.
Let $L_1 = H' \coprod C_{n_1}$, where $n_1 \equiv 2(\text{mod }3)$.
Then  by \cite[Proposition 2.7]{HTT},
$\reg(I(L_1)^2)=\zeta(L_1)+3.$
By \cite[Theorem 5.7]{nguyen_vu}, for $q \geq 3$, we have
$\reg(I(L_1)^q)=2q+\zeta(L_1)-1.$
For $i \geq 2$, let $L_i = L_{i-1} \coprod C_{n_i}$, where $n_i \equiv
2(\text{mod }3)$.
Recursively applying \cite[Proposition 2.7]{HTT} and \cite[Theorem
5.7]{nguyen_vu}, to the graphs $L_i$, we get for all $q \geq 2$,
$\reg(I(H)^q)=2q+\zeta(H)-1.$
\end{proof}

In \cite{jayanthan}, the authors asked if there exists a graph 
$G$ with $2q + \nu(G) - 1 < \reg(I(G)^q) < 2q + \cochord(G) - 1$ for
all $q \gg 0$, \cite[Question 5.8]{jayanthan}. We show that some of
the graphs considered in Proposition
\ref{disjoint} satisfy this inequality.
Let $H$ be a graph as in Proposition \ref{disjoint}, with $n_j \equiv
1(\text{mod }3)$ for $j = p+1, \ldots, q$. Then $\nu(H) =
\sum_{i=1}^q \lfloor\frac{n_i}{3} \rfloor$, $\zeta(H) =
p+ \sum_{i=1}^q \lfloor \frac{n_i}{3} \rfloor$ and $\cochord(G) =
q+ \sum_{i=1}^q \lfloor \frac{n_i}{3} \rfloor$. Therefore, we get
$$2q+\nu(H)-1<\reg(I(H)^q) = 2q + \zeta(H) - 1 <2q+\cochord(H)-1.$$


Using techniques very similar to the ones used in the proof of Theorem
\ref{base-reg}, we prove a weaker version of Conjecture
\ref{ABBH-conj}. 

\begin{theorem}\label{weak-conj1} Let $G$ be a graph. If every induced subgraph $H$ of 
$G$ has a vertex $x$ with $\reg(I(H \setminus N_H[x]))+1 \leq
\reg(I(H))$, then for all $q \geq 1$,
\[
 \reg(I(G)^q) \leq 2q+\reg(I(G))-2.
\]
\end{theorem}
\begin{proof}
Let $G$ be a graph satisfying the given hypothesis. We prove the
assertion by induction on $q$. If $q=1,$ then we are done.
Assume that $q >1$. 
For any graph $K$, set 
 \[
  \PP(K)=\{x \in V(K) \mid \reg(I(K)) \geq \reg(I(K \setminus N_K[x]))+1\}.
   \]
By hypothesis, $\PP(G) \neq \emptyset$.
By applying \cite[Theorem 5.2]{banerjee} and using
induction, it is enough to prove that for edges $e_1, \ldots, e_s$ of
$G$,
$\reg((I(G)^{s+1}:e_1 \cdots e_s)) \leq \reg(I(G))$ for all $s \geq 1$. 
We prove this by induction
on $s$.


Let $G'$ be the graph associated to the ideal
  $\widetilde{(I(G)^{s+1}:e_1\cdots e_s)}$ which is contained in an appropriate polynomial ring 
  $R_1$.
Suppose $s=1$. 
 \vskip 1mm \noindent
\textsc{Case 1:} Suppose $e_1\cap \PP(G) \neq \emptyset$.
\vskip 1mm \noindent 
Let $e_1=\{x,y\}$ with $x \in \PP(G)$.
We proceed as in the proof of Theorem \ref{base-reg}. 
 If either $\deg_G(x)=1$ or $\deg_G(y)=1$, 
then by Lemma \ref{even_obs2}, $I(G')=I(G)$. Therefore,
$\reg(I(G'))=\reg(I(G))$.
\vskip 1mm \noindent
Suppose  $\deg_G(x)>1$ and $\deg_G(y)>1$. Setting 
   $U=N_G(y)=\{y_1,\ldots,y_r\}$ and 
 $J=I(G')$ and considering the exact sequences as in Equation
 (\ref{main-exact-seq}), we get
 \[
  \reg(R_1/J)  \leq  \max \left\{
	\begin{array}{l}
	  \reg\left(\frac{R_1}{(J :y_1)}\right)+1, 
		\ldots, 
		\reg\left(\frac{R_1}{(J,y_1,y_2,\ldots,y_{r-1}):y_r)}\right) + 1,~ 
		\reg\left(\frac{R_1}{(J,~U)}\right).
\end{array}\right.
\]
Proceeding as in that proof, we conclude that $\reg(R_1/(J,U)) \leq
\reg(R/I(G))$ and $\reg(J: y_j) \leq \reg(I(G \setminus N_G[x])) <
\reg(I(G))$, where the last inequality follows from the hypothesis. 
Since $((J,y_1,\ldots, y_{j-1}): y_j)$ corresponds to
an induced subgraph of $(J : y_j)$, we get
$$\reg \left( \frac{R_1}{((J,y_1,\ldots,y_{j-1}):y_j)}\right)+1 \leq 
\reg \left( \frac{R_1}{(J:y_j)}\right) +1\leq \reg\left(\frac{R}{I(G)}\right).$$
Therefore, 
$\reg\left( \frac{R_1}{J}\right) \leq \reg(\frac{R}{I(G)}).$
\vskip 1mm \noindent
\textsc{Case 2:} Suppose $e_1 \cap \PP(G) = \emptyset$. 
\vskip 1mm \noindent  
 Let $|V(G)|=n$. We proceed by induction on $n$. If $n \leq 4$, then it can be
seen that $e \cap \PP(G)\neq \emptyset$, for all $e \in E(G)$ so that
\textsc{Case 2} does not occur.
Therefore $n \geq 5$.  
 \noindent
 \begin{minipage}{\linewidth}
 
\begin{minipage}{0.2\linewidth} 
\begin{figure}[H]
 \begin{tikzpicture}[scale=.75]
\draw (4,3)-- (3,2);
\draw (4,3)-- (5,2);
\draw (3,2)-- (5,2);
\draw (3,2)-- (3.01,0.59);
\draw (5,2)-- (4.99,0.61);
\draw (3.01,0.59)-- (4.99,0.61);
\draw (4.99,0.61)-- (3.01,0.59);
\draw (5,2)-- (3,2);
\begin{scriptsize}
\fill [color=black] (4,3) circle (1.5pt);
\draw[color=black] (4.25,3.23) node {$t_1$};
\fill [color=black] (3,2) circle (1.5pt);
\draw[color=black] (2.88,2.25) node {$t_5$};
\fill [color=black] (5,2) circle (1.5pt);
\draw[color=black] (5.25,2.23) node {$t_2$};
\fill [color=black] (3.01,0.59) circle (1.5pt);
\draw[color=black] (2.79,0.7) node {$t_4$};
\fill [color=black] (4.99,0.61) circle (1.5pt);
\draw[color=black] (5.23,0.85) node {$t_3$};
\end{scriptsize}
\end{tikzpicture}
\end{figure}
\end{minipage}
\begin{minipage}{0.78\linewidth}
Suppose $n=5$.  There are $23$ simple graphs (without isolated
vertices) on $5$ vertices. Among these graphs, it can be verified,
manually or using computational packages such as Macaulay 2 \cite{M2}
or SAGE \cite{sage}, that all, except the graph given on the left,
satisfy the property that $G \setminus \PP(G)$ is a set of isolated
vertices. 
\end{minipage}
\end{minipage}
For this graph $G$, $\reg(I(G)) = 2$ and $\PP(G) = \{t_2, t_5\}$. Hence
$\{t_3,t_4\} \in E(G \setminus \PP(G))$ and $(I(G)^2 : t_3t_4) = I(G)$ so
that $G' = G$. Therefore, the assertion holds true.
  
Now assume that $n>5$. By induction, assume that if $K$ is a
graph with $|V(K)| < n$ and for every induced subgraph $K'$ of $K$,
there exists $z \in V(K')$ such that
$\reg(I(K' \setminus N_{K'}[z]))+1 \leq \reg(I(K'))$,
then $\reg(I(K)^2 :e) \leq \reg(I(K))$ for every
$e\in E(K)$ such that $e \cap \PP(K)= \emptyset$.

Let $x \in \PP(G)$. Then by \cite[Theorem 3.4]{Ha2},
\[\reg(I(G')) \leq \max
\Big\{\reg(I(G' \setminus \{x\})), \reg(I(G' \setminus
N_{G'}[x])+1\Big\}.\]
Since $e_1 \cap \{x\}=\emptyset$, by Lemma \ref{single_vertex}, 
$$\reg(I(G' \setminus x))=\reg((I(G \setminus x)^2:e_1)).$$
Note that $G \setminus x$ is a graph with $|V(G \setminus x)|<n$ and every induced
subgraph of $G \setminus x$ is an induced subgraph of $G$.
If $e_1 \cap \PP(G \setminus x) \neq \emptyset$, then by Case 1, or if
$e_1 \cap \PP(G \setminus x) = \emptyset$, then by induction on the number of vertices, we get
$$\reg((I(G \setminus x)^2:e_1)) \leq \reg(I(G \setminus x)) \leq \reg(I(G)).$$
Now we prove that $\reg(I(G' \setminus N_{G'}[x])+1 \leq \reg(I(G))$.
Note that $G \setminus N_G[x]$ is a graph with $|V(G \setminus N_G[x])|<n$.
If $e_1 \cap \PP(G \setminus N_G[x]) \neq \emptyset$, then by Case 1, or if
$e_1 \cap \PP(G \setminus N_G[x]) = \emptyset$, then by induction on the number of vertices, we get
\[
\begin{array}{llll}
\reg(I(G' \setminus N_{G'}[x]))+1 & \leq & \reg(I(G \setminus N_G[x])^2:e_1)+1 & 
(\text{by Lemma }\ref{tech_lemma}) \\

 
   & \leq & \reg(I(G \setminus N_G[x]))+1 &  \\
   & \leq & \reg(I(G)). & 
\end{array}
\]
Hence $\reg(I(G')) \leq \reg(I(G))$. This proves the case $s =1$.
  
Suppose $s > 1$. We now show that $\reg(I(G)^{s+1}: e_1\cdots e_s)
\leq \reg(I(G))$. Let $e_i = \{a_i, b_i\}$ for $1 \leq i \leq s$. If
$\deg_G(a_i) = 1$ or $\deg_G(b_i)$ for some $i$, then by Lemma
\ref{even_obs2}, it follows that 
\[\reg(I(G)^{s+1} : e_1\cdots e_s) = \reg(I(G)^s : e_1\cdots
  e_{i-1}e_{i+1}\cdots e_s) \leq \reg(I(G)),\]
where the last inequality follows from induction on $s$.

Assume now that $\deg_G(a_i) \geq 2$ and $\deg_G(b_i) \geq 2$ for all
$1 \leq i \leq s$.
  \vskip 1mm \noindent
\textsc{Case 3:} Suppose $e_i \cap \PP(G) \neq \emptyset$, for some $1
\leq i \leq s$. 
\vskip 1mm \noindent
Without loss of generality, assume that $e_s \cap \PP(G) \neq
\emptyset$ and $a_s \in \PP(G)$.
Proceeding as in the proof Theorem \ref{base-reg} following the same
notation, one gets 
  \begin{eqnarray*}
   \reg(J,X_1,X_2)  &\leq & \reg(I(G' \setminus N_{G'}[b_s]))\leq \reg(I(G \setminus N_G[b_s])) \leq
  \reg(I(G));\\
  \reg(J : y_i) & \leq & \reg(I((G \setminus N_G[y_i,a_s])')) \leq \reg(I((G \setminus N_G[a_s])')) \\
  & \leq&  \reg(I(G \setminus N_G[a_s])) < \reg(I(G));
  \\
  \reg(J,X_1 : z_i) &\leq &\reg(I((G \setminus N_G[y_i,a_s])')) \leq \reg(I((G \setminus N_G[a_s])'))\\
  & \leq & \reg(I(G \setminus N_G[a_s])) < \reg(I(G)).
\end{eqnarray*}
For the above conclusions, we use, in a similar manner as in the proof
of Theorem \ref{base-reg}, Lemmas \ref{tech_lemma}, \ref{ind-reg},
\ref{even-lemma} and induction on $s$. Using these inequalities, we
conclude that $\reg(J)
\leq \reg(I(G))$.
\vskip 1mm \noindent
\textsc{Case 4:}
Suppose $e_i \cap \PP(G) = \emptyset$, for all $1 \leq i \leq s$.

If $|V(G)| \leq 4$, then one can see that the case $e_i \cap \PP(G) =
\emptyset$ does not occur. If $|V(G)| = 5$, then as remarked in
\textsc{Case 2}, one can see that there is only one graph $G$, which
is given there, such that $G \setminus \PP(G)$ has an edge. In this
case, the only possibility is $e_i = \{t_3, t_4\}$ for all $i = 1,
\ldots, s$. Hence $G' = G$ and hence the assertion holds true.

Now assume that $|V(G)| = n > 5$.
Let $x \in \PP(G)$. Then by by \cite[Theorem 3.4]{Ha2}, 
\[\reg(I(G')) \leq \max
\Big\{\reg(I(G' \setminus \{x\})), \reg(I(G' \setminus
N_{G'}[x]))+1\Big\}.\]

By Lemma \ref{single_vertex}, $\reg(I(G' \setminus x)) =
\reg(I(G\setminus x)^{s+1} : e_1 \cdots e_s))$ and by Lemma
\ref{tech_lemma},  $\reg(I(G' \setminus N_{G'}[x])) \leq \reg(I(G
\setminus N_G[x])^{t+1} : e_{i_1}\cdots e_{i_t})$, where $E(G\setminus
N_G[x]) \cap \{e_1, \ldots, e_s\} = \{e_{i_1}, \ldots, e_{i_t}\}$.
Proceeding as in \textsc{Case 2}, using the above inequalities and
induction on $|V(G)|$ as well as on $s$, 
one can conclude that $\reg(I(G')) \leq \reg(I(G))$. 
Therefore $\reg(I(G)^{s+1} : e_1\cdots e_s) \leq \reg(I(G))$.
\end{proof}

In view of the above theorem, we would like to ask:

\begin{question}
Does every finite simple graph $G,$ having no isolated vertices, have
a vertex $x$ such that $\reg(I(G): x) + 1 \leq \reg(I(G))$?
\end{question}
We note here that if the answer to the above question is positive,
then it follows from Theorem \ref{weak-conj1} that the Conjecture
\ref{ABBH-conj} is true.



\section{Vertex decomposable graphs}\label{reg-vertex}
In this section, we prove Conjecture \ref{ABBH-conj} for vertex
decomposable graphs.
We first recall the definition of simplicial complex and vertex decomposable graph.

A \textit{simplicial complex} $\Delta$ on $V = \{x_1,\ldots,x_n\}$ is
a collection of subsets of $V$ such that: 
\begin{enumerate}
 \item $\{x_i\}\in \Delta $ for $i =1,\ldots,n$, and
 \item if $F \in \Delta$ and $G \subseteq F$, then $G \in \Delta$.
\end{enumerate}
Elements of $\Delta$ are called the \textit{faces} of $\Delta$, and the maximal elements, with 
respect to inclusion, are called the facets. The link of a face $F$ in
$\Delta$ is $\link_\Delta(F) = \{F' \mid F' \cup F \text{ is a face in
} \Delta, ~F' \cap F = \emptyset \}$.


A simplicial complex $\Delta$ is
recursively defined to be {\em vertex decomposable} if it is either a
simplex or else has some vertex $v$ so that 
\begin{enumerate}
  \item both $\Delta \setminus v$ and $\link_\Delta v$ are vertex decomposable, and
  \item no face of $\link_\Delta v$ is a facet of $\Delta \setminus v$.
\end{enumerate}

The \textit{independence complex} of $G$, denoted $\Delta(G)$, is the simplicial
complex on $V(G)$ with face set 
$$\Delta(G)=\Big\{F \subseteq V(G) \mid F \text{ is an independent set of $G$ } \Big\}.$$
A graph $G$ is said to be \textit{vertex decomposable} if $\Delta(G)$ is a
vertex decomposable simplicial complex. 
In \cite{Wood2}, Woodroofe translated the notion of vertex decomposable
for graphs as follows.
\begin{definition} \cite[Lemma 4]{Wood2}
 A graph $G$ is recursively defined to be vertex decomposable if 
 $G$ is totally disconnected (with no edges) or if 
 \begin{enumerate}
  \item there is a vertex $x$ in $G$ such that $G \setminus x$ and 
  $G \setminus N_G[x]$ are both vertex decomposable, and
  \item no independent set in $G\setminus N_G[x]$ is a maximal independent set 
  in $G\setminus x$.
 \end{enumerate}
\end{definition}
A vertex $x$ which satisfies the second condition is called a \textit{shedding vertex} of
$G$.
 If $G$ is a vertex decomposable graph, then by \cite[Theorem 2.5]{BFH15},
 $G \setminus N_G[x]$ is a vertex decomposable graph, for any  $x \in V(G)$.
 For any vertex decomposable graph $K$, set 
 \[
\s(K)=\Big \{ x \in V(K) \mid \text{$x$ is a shedding vertex and 
$K \setminus x$ is a vertex decomposable graph} \Big\}.
\]
 Note that if $K$ is vertex decomposable, then $\s(K) \neq \emptyset$.
 \begin{obs} \label{reg-obs}
 Let $G$ be a vertex decomposable graph and $x \in \s(G)$. By \cite[Theorem 4.2]{HaWood},
 $$\reg(I(G))=\max\Big\{\reg(I(G \setminus x)), ~\reg(I(G \setminus N_G[x]))+1\Big\}.$$
 Therefore, $\reg(I(G \setminus N_G[x]))+1 \leq \reg(I(G))$.
 \end{obs}
 We prove Conjecture \ref{ABBH-conj} for the class of vertex decomposable graphs.
\begin{theorem}\label{upper-ver}
  Let $G$ be a vertex decomposable graph. Then for all $q \geq 1$,
 $$\reg(I(G)^q) \leq 2q+\reg(I(G))-2.$$
 \end{theorem}
\begin{proof}
This proof is also very similar to the proof of Theorem
\ref{weak-conj1}. We give a sketch of the proof here.  The proof is by
induction on $q$. If $q=1,$ then we are done.  Assume that $q >1$. By
applying \cite[Theorem 5.2]{banerjee} and using induction, it is
enough to prove that for edges $e_1, \ldots, e_s$ of $G$ (not
necessarily distinct), $\reg((I(G)^{s+1}:e_1 \cdots e_s)) \leq
\reg(I(G))$ for all $s \geq 1$.  We prove this by induction on $s$.
Let $G'$ be the graph associated to $\widetilde{(I(G)^{s+1}:e_1\cdots
e_s)}$, for any $e_1, \ldots, e_s \in E(G)$.

Let $s = 1$. As in the proof of Theorem \ref{weak-conj1}, we split the
proof into two cases.
\vskip 1mm \noindent
\textsc{Case 1:} Suppose $e_1\cap \s(G) \neq \emptyset$.
\vskip 1mm \noindent 
The proof is identical to \textsc{Case 1} in Theorem \ref{weak-conj1}.
The only difference in the proof is that
while we used the hypothesis in Theorem \ref{weak-conj1} to conclude
that $\reg(J:y_i) < \reg(I(G))$, here we use Observation \ref{reg-obs}
for that conclusion.
\vskip 1mm \noindent
\textsc{Case 2:} Suppose $e_1 \cap \s(G) = \emptyset$. 
\vskip 1mm \noindent
Let $|V(G)|=n$.  We proceed by induction on $n$. 
If $G$ is a vertex decomposable with $n \leq 4$, then
it can be seen that $e \cap \s(G)\neq \emptyset$, for all $e \in
E(G)$. Therefore $n \geq 5$.

\noindent
 \begin{minipage}{\linewidth}
 
\begin{minipage}{0.41\linewidth} 
\begin{figure}[H]
 \begin{tikzpicture
\draw (3,3)-- (2,2);
\draw (3,3)-- (4,2);
\draw (2,2)-- (4,2);
\draw (5,3)-- (5,2);
\draw (5,2)-- (7,2);
\draw (7,2)-- (7,1);
\draw (5,2)-- (5,1);
\draw (5,1)-- (7,1);
\draw (4,2)-- (4,1);
\draw (2,2)-- (2,1);
\draw (2,1)-- (4,1);
\begin{scriptsize}
\fill [color=black] (3,3) circle (1.5pt);
\fill [color=black] (2,2) circle (2.5pt);
\fill [color=black] (4,2) circle (2.5pt);
\fill [color=black] (5,3) circle (1.5pt);
\fill [color=black] (5,2) circle (2.5pt);
\fill [color=black] (7,2) circle (1.5pt);
\fill [color=black] (7,1) circle (1.5pt);
\fill [color=black] (5,1) circle (1.5pt);
\fill [color=black] (4,1) circle (1.5pt);
\fill [color=black] (2,1) circle (1.5pt);
\end{scriptsize}
\end{tikzpicture}
\caption*{Vertex decomposable graphs with $|V(G)|=5$ and $\bullet$
denote shedding vertices.}\label{fig:vertexdecom}
\end{figure}
\end{minipage}
\begin{minipage}{0.59\linewidth}
Suppose $n=5$.
It can verified, manually or using computational packages such as
Macaulay 2 \cite{M2}, SimplicialDecomposability \cite{Cook} or SAGE \cite{sage}, that there are $20$ vertex decomposable
graphs (without isolated vertices) on $5$ vertices. Among these
graphs, all except two graphs satisfy the property that $G \setminus
\s(G)$ is a set of isolated vertices. The two graphs for which $G
\setminus \s(G)$ contain edges are given in the figure on the left.
Then for any choice of $e \in E(G \setminus
\s(G)), ~ (I(G)^2 : e) = I(G)$ so that $G' = G$.
\end{minipage}
\end{minipage}

Now assume that $n>5$. By induction, assume that if $H$ is a
vertex decomposable graph with $|V(H)| < n$ and $e
\in E(H)$ such that $e \cap S(H)= \emptyset$, then $\reg(I(H)^2 :
e) \leq \nu(H)+1$. 
Let $x \in \s(G)$. By \cite[Theorem 3.4]{Ha2}, 
\[\reg(I(G')) \leq \max
\Big\{\reg(I(G' \setminus \{x\})), \reg(I(G' \setminus
N_{G'}[x])+1\Big\}.\]
Now the proof is identical to that of the proof of \textsc{Case 2} in
Theorem \ref{weak-conj1}. In this case also, we use Observation
\ref{reg-obs} to conclude $\reg(I(G \setminus N_G[x])) < \reg(I(G))$.

Suppose $s > 1$. Assume by induction that for any vertex decomposable graph $G$
and edges $e_1,\ldots, e_{s-1}$, $\reg(I(G)^s : e_1 \cdots e_{s-1}) \leq \reg(I(G))$.
We now prove that for edges $e_1, \ldots, e_s$, $\reg(I(G)^{s+1} :
e_1\cdots e_s) \leq \reg(I(G))$. Let $e_i = \{a_i, b_i\}$. If
$\deg_G(a_i) = 1$ or $\deg_G(b_i) = 1$ for some $i$, then the
assertion follows as in the proof of Theorem \ref{weak-conj1}.
Therefore, we may assume that $\deg_G(a_i) \geq 2$ and $\deg_G(b_i)
\geq 2$ for all $1 \leq i \leq s$.

  \vskip 1mm \noindent
\textsc{Case 3:} Suppose $e_i \cap \s(G) \neq \emptyset$, for some $1
\leq i \leq s$. 
\vskip 1mm \noindent
Without loss of generality, assume that $e_s \cap \s(G) \neq \emptyset$ and $a_s \in \s(G)$.
Proceeding as in the proof Theorem \ref{weak-conj1} following the same
notation, one gets 
\begin{eqnarray*}
\reg(J,X_1,X_2)  &\leq & \reg(I(G' \setminus N_{G'}[b_s]))\leq \reg(I(G \setminus N_G[b_s])) \leq
  \reg(I(G));  \\  
  \reg(J : y_i) & \leq & \reg(I((G \setminus N_G[y_i,a_s])')) \leq \reg(I((G \setminus N_G[a_s])')) \\
  & \leq&  \reg(I(G \setminus N_G[a_s])) < \reg(I(G));
  \\
  \reg(J,X_1 : z_i) &\leq &\reg(I((G \setminus N_G[y_i,a_s])')) \leq \reg(I((G \setminus N_G[a_s])'))\\
  & \leq & \reg(I(G \setminus N_G[a_s])) < \reg(I(G)).
\end{eqnarray*}
Here also, we use Observation \ref{reg-obs} along with 
Lemmas \ref{tech_lemma},
\ref{ind-reg}, \ref{even-lemma} and induction on $s$ for the above
conclusions.
Using these inequalities, we conclude, as in the proof
of Theorem \ref{weak-conj1}, that $\reg(J) \leq \reg(I(G))$.

\vskip 1mm \noindent
\textsc{Case 4:}
Suppose $e_i \cap \s(G) = \emptyset$, for all $1 \leq i \leq s$.

Let $x \in \s(G)$. By \cite[Theorem 3.4]{Ha2}, 
\[\reg(I(G')) \leq \max
\Big\{\reg(I(G' \setminus \{x\})), \reg(I(G' \setminus
N_{G'}[x])+1\Big\}.\]
Here too, the proof is identical to \textsc{Case 4} of Theorem
\ref{weak-conj1}.

Finally, we obtain
$\reg(I(G)^{s+1} : e_1\cdots e_s) \leq \reg(I(G))$. Therefore, for all
$q \geq 1$,
$\reg(I(G)^q) \leq 2q + \reg(I(G)) - 2$.
\end{proof}

As an immediate consequence of the above result, we obtain the linear
polynomial corresponding to $\reg(I(G)^q)$ for several 
classes of graphs.

\begin{corollary}\label{main-cor} If
\begin{enumerate}
 \item $G$ is $C_5$-free vertex decomposable;
 \item $G$ is chordal;
 \item $G$ is sequentially Cohen-Macaulay bipartite,    ~~or
 \item $G=H \cup W(S)$, where $S \subseteq V(H)$, $H \setminus S$ is a
   chordal graph and $H \cup W(S)$ denotes the graph obtained from $H$ by adding a whisker to each vertex in $S$,
\end{enumerate}
then for all $q \geq 1$, $$\reg(I(G)^q)=2q+\nu(G)-1.$$ 
\end{corollary}
\begin{proof} (1) Follows from Theorem \ref{upper-ver}, \cite[Theorem 4.5]{selvi_ha} and
\cite[Lemma 2.3]{khosh_moradi}.
\vskip 1mm \noindent
(2) Since $G$ is chordal, it is $C_5$-free and by \cite{Wood2} $G$ is
vertex decomposable. By (1), $\reg(I(G)^q)=2q+\nu(G)-1$.
 \vskip 1mm \noindent
 (3) By \cite[Theorem 2.10]{adam}, $G$ is vertex decomposable. 
  Since a bipartite graph is $C_5$-free, the assertion follows from
  (1).
  \vskip 1mm \noindent
 (4) First we show that $\reg(I(G))=\nu(G))+1$. By \cite[Lemma 2.2]{Kat}, we have
$\nu(G))+1 \leq \reg(I(G)$. Therefore, it is enough to prove that $\reg(I(G))\leq 
\nu(G)+1$. Set $|S|=m$.
 If $m=0$, then by \cite[Corollary 6.9]{ha_adam}
 $\reg(I(G))=\nu(G)+1.$
 Suppose $m \geq 1$. There is a vertex $x$ in $S$ such that $N_{G}(z_x)=\{x\}$. 
 By \cite[Theorem 3.4]{Ha2},
 $$\reg(I(G)) \leq \max \{\reg(I(G \setminus x)),\reg(I(G \setminus N_{G}[x]))+1\}.$$
 By induction hypothesis on $m$, 
 $\reg(I(G \setminus x)) \leq \nu(G)+1$ and $\reg(I(G \setminus N_{G}[x])))+1 \leq 
 \nu(G \setminus N_G[x])+2$. If $\{f_1,\ldots,f_t\}$ is an induced matching of $G \setminus N_G[x]$,
 then $\{f_1,\ldots,f_t,\{x,z_x\}\}$ is an induced matching of $G$.
 Therefore $\nu(G \setminus N_G[x])+1 \leq \nu(G)$. Hence
 $ \reg(I(G))=\nu(G)+1.$
 By \cite[Corollary 4.6]{BFH15}, $G$ is a vertex decomposable graph. Therefore, by
 Theorem \ref{upper-ver} and \cite[Theorem 4.5]{selvi_ha},
 $\reg(I(G)^q)=2q+\nu(G)-1.$
\end{proof}


\vskip 2mm \noindent
\textbf{Acknowledgement:} We would like to thank  Fahimeh Khosh-Ahang,
Huy T{\`a}i H\`a, Adam Van Tuyl and Russ Woodroofe for several
clarifications on our doubts on their results. We also would like to
thank Arindam Banerjee and Huy T\`ai H\`a for pointing out an error in
one of the proofs in an earlier version of the manuscript. We
extensively used \textsc{Macaulay2}, \cite{M2}, \textsc{SAGE},
\cite{sage} and the package \textsc{SimplicialDecomposability},
\cite{Cook}, for testing our our computations.




\bibliographystyle{abbrv} 

2018-05-04T02:12:24.000
1805
1805.01412
en
https://arxiv.org/abs/1805.01412
Let $G$ be a finite simple graph and $I(G)$ denote the corresponding edge ideal. In this paper, we obtain upper bounds for the Castelnuovo-Mumford regularity of $I(G)^q$ in terms of certain combinatorial invariants associated with $G$. We also prove a weaker version of a conjecture by Alilooee, Banerjee, Beyarslan and Hà on an upper bound for the regularity of $I(G)^q$ and we prove the conjectured upper bound for the class of vertex decomposable graphs. Using these results, we explicitly compute the regularity of $I(G)^q$ for several classes of graphs.
Commutative Algebra (math.AC); Combinatorics (math.CO)
Upper bounds for the regularity of powers of edge ideals of graphs
Qwen/Qwen-72B
1. YES
2. YES