# On powers of cover ideals of graphs

Dancheng Lu and Zexin Wang  Dancheng Lu, School of Mathematics Science,
Soochow University, P.R.China<EMAIL_ADDRESS>Zexin Wang, School of
Mathematics Science, Soochow University, P.R.China<EMAIL_ADDRESS>
###### Abstract.

For a simple graph $G$, assume that $J(G)$ is the vertex cover ideal of $G$
and $J(G)^{(s)}$ is the $s$-th symbolic power of $J(G)$. We prove that
$\operatorname{reg}(J(C)^{(s)})=\operatorname{reg}(J(C)^{s})$ for all $s\geq
1$ and for all odd cycle $C$. For a simplicial complex $\Delta$, we show that
if $I_{\Delta}^{\vee}$ is weakly polymatroidal (not necessarily generated in
one degree) then $\Delta$ is vertex decomposable. Let $W=G^{\pi}$ be a fully
clique-whiskering graph. We prove that $J(W)^{s}$ is weakly polymatroidal for
all $s\geq 1$. Finally, we point out a gap in the proof of [17, Theorem 4.3]
and give a revised proof for it.

###### Key words and phrases:

Regularity, Symbolic power, Odd cycle, Weakly polymatroidal, Whisker graph,

###### 2010 Mathematics Subject Classification:

Primary 05E40,13A02; Secondary 06D50.

##  1\. Introduction

Let $R=K[x_{1},\ldots,x_{n}]$ be the polynomial ring over a field $K$ and let
$G$ be a simple graph on vertex set $[n]:=\\{1,2,\ldots,n\\}$ with edge set
$E(G)$. There are two square-free monomial ideals of $R$ associated to $G$:
the edge ideal $I(G)$ which is generated by all monomial $x_{i}x_{j}$ with
$\\{i,j\\}\in E(G)$ and the vertex cover ideal $J(G)$ generated by monomials
$\prod_{i\in F}x_{i}$, where $F$ is taken over all minimal vertex covers of
$G$. Recall that a subset $F$ of $V(G)$ is a vertex cover of $G$ if $F\cap
e\neq\emptyset$ for every edge $e$ of $G$ and a vertex cover $F$ of $G$ is
minimal if $C\setminus\\{i\\}$ is not a vertex cover for each $i\in F$. The
vertex cover ideal $J(G)$ is the Alexander duality of the edge ideal $I(G)$,
i.e.,

$J(G)=I(G)^{\vee}=\bigcap_{\\{i,j\\}\in E(G)}(x_{i},x_{j}).$

Let $I$ be a graded ideal of $R$. The $s$-th symbolic power of $I$ is defined
by

$I^{(s)}=\bigcap_{\mathfrak{p}\in\mathrm{Min}(I)}I^{s}R_{\mathfrak{p}}\cap R,$

where $\mathrm{Min}(I)$ is as usual the set of all minimal prime ideals of
$I$. It follows from [12, Proposition 1.4.4] that for every integer $s\geq 1$,

$J(G)^{(s)}=\bigcap_{\\{i,j\\}\in E(G)}(x_{i},x_{j})^{s}.$

The Castelnuovo-Mumford regularity (or simply regularity) is a fundamental
invariant in commutative algebra and algebraic geometry. For a finitely
generated graded module $M$ over the polynomial ring $R$, the regularity of
$M$, denoted by $\operatorname{reg}(M)$, is the least integer $r\geq 0$ such
that for all $i\geq 0$, the $i$-th syzygy of $M$ is generated by homogeneous
elements of degree at most $r+i$. An equivalent definition of the regularity
via local cohomology is as follows:

$\operatorname{reg}(M)=\max\\{i+j\colon\;H^{i}_{\mathfrak{m}}(M)_{j}\neq
0,i\geq 0,j\in\mathbb{Z}\\}.$

Here $\mathfrak{m}$ denotes the maximal ideal $(x_{1},\ldots,x_{n})$.

For edge ideals of graphs, there have been a lot of research on connections
between the regularity functions $\operatorname{reg}(I(G)^{s})$ as well as
$\operatorname{reg}(I(G)^{(s)})$ and the combinatorial properties of $G$, see
[1] and the references therein. Recently the conjecture that
$\operatorname{reg}(I(G)^{(s)})=\operatorname{reg}(I(G)^{s})$ for all $s\geq
1$ and for all graphs $G$ attracted much attention and much progress has been
made in this direction, For the details, see [9] and the references therein.

Meanwhile, the study of algebraic properties of (symbolic and ordinary) powers
of vertex cover ideals of graphs is also an active research topic. However,
the regularity of powers of such ideals is harder to compute or deal with. In
fact, although S.A. Seyed Fakhari presented in [21] the following remarkable
bounds for a large class of graphs $G$, including bipartite graphs, unmixed
graphs, claw-free graphs:

$s\mathrm{Deg}(J(G))\leq\mathrm{reg}(J(G)^{(s)})\leq(s-1)\mathrm{Deg}(J(G))+|V(G)|-1,$

there are not many graphs $G$ for which either
$\operatorname{reg}(J(G)^{(s)})$ or $\operatorname{reg}(J(G)^{s})$ is known
precisely. Here, $\mathrm{Deg}(J(G))$ is the maximum size of minimal vertex
covers of $G$. When $G$ is either a crown graph or a complete multipartite
graph, $\operatorname{reg}(J(G)^{(s)})$ was explicitly given in [11]. It is
known if a graded ideal is componentwise linear then its regularity is equal
to the maximum degree of its minimal generators. In the literatures [4, 7, 17,
21, 20] and [22], some classes of graphs for which either $J(G)^{s}$ or
$J(G)^{(s)}$ is componentwise linear are identified. For examples, in [22], it
was characterized all the graphs $G$ with the property that $J(G)^{(k)}$ has a
linear resolution for some (equivalently, for all ) integer $k\geq 2$. In [4,
7, 20, 21] and [22], they investigate the question of how to combinatorially
modify a graph to obtain prescribed algebraic properties of the corresponding
monomial ideals, and identify some graphs $G$ such that
$\operatorname{reg}(J(G)^{(s)})$ is componentwise linear. In [17], some
classes of graphs $G$ such that $\operatorname{reg}(G)^{s}$ is componentwise
linear were found. For such graphs $G$, the regularity of either $J(G)^{s}$ or
$J(G)^{(s)}$ is known.

In this paper we investigate further the properties of (symbolic and ordinary)
powers of vertex cover ideals of simple graphs. Our first main result is
motivated by Theorem 5.15 in [4], in which a family of graphs $G$ was
constructed such that $\operatorname{reg}(J(G)^{(s)})$ is not eventually
linear in $s$. This result particularly shows that the equality
$\operatorname{reg}(J(G)^{(s)})=\operatorname{reg}(J(G)^{s})$ is not true in
general. On the other side, we have known the equality
$\operatorname{reg}(I(G)^{(s)}=\operatorname{reg}(I(G)^{s})$ for all $s\geq 1$
holds for many classes of graphs such as unicyclic graphs and chordal graphs
and so on. These facts lead us to ask the following question:

For which graphs $G$ has one
$\operatorname{reg}(J(G)^{(s)})=\operatorname{reg}(J(G)^{s})$ for all $s\geq
1$?

In this vein we prove the following result.

Theorem 2.4 If $G$ is an odd cycle, then
$\operatorname{reg}(J(G)^{(s)})=\operatorname{reg}(J(G)^{s})$ for all $s\geq
1$.

We remark this is the first non-trivial example where the above formula holds,
due to the well-known fact that $G$ is a bipartite graph if and only if
$J(G)^{(s)}=J(G)^{s}$ for some $s\geq 2$ (equivalently for all $s\geq 1$), see
[23, Proposition 1.3] or [13, Theorem 5.1].

We next investigate relations between weak polymatroidality of a monomial
ideal and vertex decomposability of a simplicial complex. It turns out it
helps to understand the behaviors of the powers of cover ideals. Vertex
decomposability was first introduced by [19] in the pure case, and extended to
the non-pure case in [2]. It is defined in terms of the deletion and link. Let
$\Delta$ be a simplicial complex on $[n]$. For $x\in[n]$, the link of $x$ in
$\Delta$ is the subcomplex

$\mbox{lk}_{\Delta}(x)=\\{F\in\Delta\colon\;F\cup\\{x\\}\in\Delta\mbox{ and
}x\notin F\\};$

and the deletion of $x$ in $\Delta$ is the subcomplex

$\mbox{del}_{\Delta}(x)=\\{F\in\Delta\colon\;x\notin F\\}.$

######  Definition 1.1.

A simplicial complex $\Delta$ is said to be vertex decomposable if either
$\Delta$ is a simplex, or there exists a vertex $x$ of $\Delta$ such that

(1) $\mbox{lk}_{\Delta}(x)$ and $\mbox{del}_{\Delta}(x)$ are vertex
decomposable;

(2) Each facet of $\mbox{lk}_{\Delta}(x)$ is not a facet of
$\mbox{del}_{\Delta}(x)$.

A vertex satisfying condition (2) is called a shedding vertex of $\Delta$.

For the recent developments on vertex decomposability, one may refer to [8]
and the references therein. The following strict implications is well-known
for a simplicial complex $\Delta$:

$\mbox{vertex decomposable }\Longrightarrow\mbox{ shellable
}\Longrightarrow\mbox{ Sequentially Cohen-Macaulay}$

Moreover, $\Delta$ is shellable if and only if $I_{\Delta}^{\vee}$ has linear
quotients; and $\Delta$ is Sequentially Cohen-Macaulay if and only if
$I_{\Delta}^{\vee}$ is componentwise linear. One may ask what property
$I_{\Delta}^{\vee}$ has when $\Delta$ is vertex decomposable, or vice versa.

######  Definition 1.2.

Following [10], we say that a monomial ideal $I$ in $R$ is weakly
polymatroidal if for every pair of elements $u=x_{1}^{a_{1}}\cdots
x_{n}^{a_{n}}$ and $v=x_{1}^{b_{1}}\cdots x_{n}^{b_{n}}$ of $G(I)$ with
$a_{1}=b_{1},\ldots,a_{q-1}=b_{q-1}$ and $a_{q}<b_{q}$, (noting that $q<n$)
there exists $p>q$ such that $w:=(x_{q}u)/x_{p}$ belongs to $G(I)$. Here,
$G(I)$ denotes the set of minimal monomial generators of $I$.

Different from the original definition in [10], we here do not require $I$ to
be generated in one degree. Using the same method as in [10], one can prove if
$I$ is weakly polymatroidal in this generalized sense, then $I$ has linear
quotients. Our second main result is as follows:

Theorem 3.1. If $I_{\Delta}^{\vee}$ is weakly polymatroidal then $\Delta$ is
vertex decomposable.

This particularly shows that being weakly polymatroidal is a condition
stronger than the property of having quotients. We also prove that the
converse of Theorem 3.1 holds in some special cases. Recall that a graph is
called unmixed if every minimal vertex cover of $G$ has the same cardinality,
i.e. $J(G)$ is generated in one degree.

Corollary 3.2. Let $G$ be either a cactus graph or a bipartite graphs or a
chordal graph. Assume further that $G$ is unmixed. Then the following are
equivalent:

  1. (1)

$R/I(G)$ is Cohen-Macaulay;

  2. (2)

$G$ is vertex indecomposable;

  3. (3)

$J(G)$ is weakly polymatroidal (in some ordering of variables);

  4. (4)

$J(G)^{k}$ is weakly polymatroidal (in some ordering of variables) for all
$s\geq 1$.

Here, a cactus graph is a simple graph in which every edge belongs to at most
one cycle. This leads us to conjecture the following.

Conjecture  If $G$ is an unmixed graph, then $G$ is vertex decomposable if and
only if $J(G)$ is weakly polymatroidal.

We prove that the above conjecture is true if $G$ has girth $\geq 5$, see
Proposition 3.5.

It is natural to ask for which unmixed graphs $G$, $J(G)^{s}$ is weakly
polymatroidal besides the graphs appearing in Corollary 3.2. Of course, such
graphs (i.e., $R/I(G)$) should be Cohen-Macaulay by Alexander duality. Let $G$
be a simple graph on vertex set $V(G)$ with edge set $E(G)$. Following [3], a
clique vertex-partition of $G$ is a partition $V(G)=W_{1}\sqcup\cdots\sqcup
W_{t}$ such that the induced graph of $G$ on $W_{i}$ is a clique (a complete
graph) for $i=1,\ldots,t$. Denote this partition by
$\pi=\\{W_{1},\ldots,W_{t}\\}$. The fully clique-whiskering graph $G^{\pi}$ of
$G$ by $\pi$ is the graph on vertex set $V(G)\cup\\{y_{1},\ldots,y_{t}\\}$ and
with edge set $E(G)\cup\\{vy_{i}\colon\;v\in W_{i},1\leq i\leq t\\}$. When
$\pi$ is a trivial partition, i.e., $|W_{1}|=\cdots=|W_{t}|=1$, $G^{\pi}$ is
also called the whisker graph of $G$. A tree is Cohen-Macaulay if and only if
it is the whisker graph of some graph; A Cameron-Walker graph is Cohen-
Macaulay if and only if it is a fully clique-whiskering graph $G^{\pi}$ of a
bipartite gaph $G$ by some clique vertex-partition $\pi$ of $G$, see [15,
Theorem 1.3]. Our third main result is as follows:

Theorem 4.4. If $W=G^{\pi}$ for some graph $G$ and some clique vertex-
partition $\pi$, then $J(W)^{s}$ is weakly polymatroidal.

This result is a complement of Corollary 3.2. As a consequence, we obtain if
$W=G^{\pi}$ then
$\operatorname{reg}(J(W)^{s})=\operatorname{reg}(J(W)^{(s)})=s|V(G)|$ for all
$s\geq 1$.

In [17] F. Mohammadi succeeded in describing the precise structure of a Cohen-
Macaulay cactus graph. Based on this result, he proved that if $G$ is a Cohen-
Macaulay cactus graph then $J(G)^{s}$ is weakly polymatroidal, see [17,
Theorem 4.3]. We conclude this paper by an appendix, in which we illustrate by
an example that there exists an essential mistake in the proof of [17, Theorem
4.3] and then present a corrected proof for this result.

In the rest part of this paper we will keep the notions introduced in this
section unless otherwise said, and refer to [12] for some unexplained notions.

##  2\. Powers of cover ideals of odd cycles

In this section we will prove that if $C$ is an odd cycle then both $J(C)^{s}$
and $J(C)^{(s)}$ have the same regularity for all $s\geq 1$.

We begin with fixing some notions. Let $M$ be a finitely generated graded
$R$-module generated by homogeneous elements $f_{1},\ldots,f_{r}$ minimally
with $\deg(f_{1})\leq\deg(f_{2})\leq\cdots\leq\deg(f_{r})$. We denote by
$\mathrm{Deg}(M)$ the number $\deg(f_{r})$ and by $\deg(M)$ the number
$\deg(f_{1})$. It is known that $\operatorname{reg}(M)\geq\mathrm{Deg}(M).$
Let $\mathfrak{m}$ denote the maximal graded ideal
$(x_{1},x_{2},\ldots,x_{n})$ of $R$.

######  Proposition 2.1.

Let $I$ be a homogeneous ideal in $R$ and $t$ a positive integer. Put
$J=I\cap\mathfrak{m}^{t}$. Then

  1. (1)

$\mathrm{reg}(\frac{R}{I})\leq\mathrm{reg}(\frac{R}{J}).$

  2. (2)

If $t\leq\mathrm{Deg}(I)$, then
$\mathrm{reg}(\frac{R}{I})=\mathrm{reg}(\frac{R}{J}).$

###### Proof.

(1) Set $b_{i}=\max\\{j\colon\;H_{\mathfrak{m}}^{i}(\frac{R}{I})_{j}\neq 0\\}$
and $a_{i}=\max\\{j\colon\;H_{\mathfrak{m}}^{i}(\frac{R}{J})_{j}\neq 0\\}$.
Then $\mathrm{reg}(\frac{R}{I})=\max\\{b_{i}+i\colon\;i\geq 0\\}$ and
$\mathrm{reg}(\frac{R}{J})=\max\\{a_{i}+i\colon\;i\geq 0\\}$. Applying the
local cohomological functors with respect to $\mathfrak{m}$ to the short exact
sequence

(${\dagger}$)
$0\rightarrow\frac{R}{J}\rightarrow\frac{R}{I}\oplus\frac{R}{\mathfrak{m}^{t}}\rightarrow\frac{R}{\mathfrak{m}^{t}+I}\rightarrow
0,$

we obtain the long exact sequence: $0\rightarrow
H_{\mathfrak{m}}^{0}(R/J)\rightarrow H_{\mathfrak{m}}^{0}(\frac{R}{I})\oplus
H_{\mathfrak{m}}^{0}(\frac{R}{\mathfrak{m}^{t}})\rightarrow
H_{\mathfrak{m}}^{0}(\frac{R}{\mathfrak{m}^{t}+I})\rightarrow\cdots\rightarrow
H_{\mathfrak{m}}^{i}(R/J)\rightarrow H_{\mathfrak{m}}^{i}(\frac{R}{I})\oplus
H_{\mathfrak{m}}^{i}(\frac{R}{\mathfrak{m}^{t}})\rightarrow
H_{\mathfrak{m}}^{i}(\frac{R}{\mathfrak{m}^{t}+I})\rightarrow\cdots$. From
this sequence as well as the equality
$H_{\mathfrak{m}}^{i}(\frac{R}{\mathfrak{m}^{t}+I})=H_{\mathfrak{m}}^{i}(\frac{R}{\mathfrak{m}^{t}})=0$
for all $i>0$, we obtain the following facts.

(i) $a_{i}=b_{i}$ for all $i\geq 2$.

(ii) The sequence $H_{\mathfrak{m}}^{1}(\frac{R}{J})\rightarrow
H_{\mathfrak{m}}^{1}(\frac{R}{I})\rightarrow 0$ is exact. From this, we have
$H_{\mathfrak{m}}^{1}(\frac{R}{I})_{i}=0$ if
$H_{\mathfrak{m}}^{1}(\frac{R}{J})_{i}=0$. This implies that $a_{1}\geq
b_{1}$.

(iii) The sequence $0\rightarrow H_{\mathfrak{m}}^{0}(\frac{R}{J})\rightarrow
H_{\mathfrak{m}}^{0}(\frac{R}{I})\oplus\frac{R}{\mathfrak{m}^{t}}\rightarrow\frac{R}{I+\mathfrak{m}^{t}}$
is exact. Thus, for any $i\in\mathbb{Z}$ with
$H_{\mathfrak{m}}^{0}(\frac{R}{J})_{i}=0$, we have
$\dim_{k}H_{\mathfrak{m}}^{0}(\frac{R}{I})_{i}+\dim_{k}[\frac{R}{\mathfrak{m}^{t}}]_{i}\leq\dim_{k}[\frac{R}{I+\mathfrak{m}^{t}}]_{i}\leq\dim_{k}[\frac{R}{\mathfrak{m}^{t}}]_{i}$
and so $\dim_{k}H_{\mathfrak{m}}^{0}(\frac{R}{I})_{i}=0$. Hence $a_{0}\geq
b_{0}$.

Combining (i),(ii) with (iii), we obtain that
$\mathrm{reg}(\frac{R}{J})\geq\mathrm{reg}(\frac{R}{I})$.

(2) By using the short exact sequence (${\dagger}$ ‣ 2), we also obtain

$\mathrm{reg}(\frac{R}{J})\leq\max\\{\mathrm{reg}(\frac{R}{I}),t-1\\}=\mathrm{reg}(\frac{R}{I}).$

This finishes the proof.

Proposition 2.1 can be extended to the case of graded modules. Let
$M=\bigoplus_{i\in\mathbb{Z}}M_{i}$ be a finitely generated
$\mathbb{Z}$-graded $R$-module. For $j\in\mathbb{Z}$, we denote by $M_{\geq
j}$ the graded submodule $\bigoplus_{j\geq i}M_{i}$ of $M$. Note that
$I\cap\mathfrak{m}^{t}=I_{\geq t}$ for any graded ideal $I$, we may look upon
the following result as a generalization of Proposition 2.1.

######  Proposition 2.2.

Let $M$ a finitely generated $\mathbb{Z}$-graded $R$-module and let
$j\in\mathbb{Z}$ such that $M_{\geq j}\neq 0$. Then the following statements
hold:

  1. (1)

$\operatorname{reg}(M_{\geq j})\geq\operatorname{reg}(M)$;

  2. (2)

If $j\leq\mathrm{Deg}(M)$, then $\operatorname{reg}(M_{\geq
j})=\operatorname{reg}(M)$.

###### Proof.

(1) Consider the following short exact sequence:

(${\ddagger}$) $0\rightarrow M_{\geq j}\rightarrow M\rightarrow M/M_{\geq
j}\rightarrow 0.$

It is known that $\operatorname{reg}(N)=\max\\{i\colon\;N_{i}\neq 0\\}$
whenever $N$ is a graded $R$-module of finite length. From this, it follows
that $\operatorname{reg}(M_{\geq j})\geq j>\operatorname{reg}(M/M_{\geq j})$.
Hence $\operatorname{reg}(M)\leq\max\\{\operatorname{reg}(M_{\geq
j}),\operatorname{reg}(M/M_{\geq j})\\}=\operatorname{reg}(M_{\geq j})$.

(2) Using the sequence (${\ddagger}$ ‣ 2) again, we obtain

$\operatorname{reg}(M_{\geq
j})\leq\max\\{\operatorname{reg}(M),\operatorname{reg}(M/M_{\geq j})+1\\}.$

Note that $\operatorname{reg}(M)\geq\mathrm{Deg}(M)\geq
j\geq\operatorname{reg}(M/M_{\geq j})+1$, the result follows.

Let $G$ be a simple graph on vertex set $[n]$ and $H$ a subgraph of $G$. The
neighborhood of $H$ is defined by

$N_{G}(H)=\\{i\in V(G)\colon\;i\mbox{ is adjacent to some vertex of }H\\}.$

By [13, Proposition 5.3], if $N_{G}(C)=[n]$ for every odd cycle $C$, then the
symbolic Rees algebra

$\mathcal{R}_{s}(J(G))=\bigoplus_{k\geq 0}J(G)^{(k)}t^{k}$

of $J(G)$ is generated by the monomial $x_{1}\cdots x_{n}t^{2}$ together with
the monomials $t\prod_{i\in F}x_{i}$ such that $F$ is a minimal vertex cover
of $G$. Thus, the following result is a direct sequence of [13, Proposition
5.3].

######  Proposition 2.3.

Let $G$ be a simple graph on vertex set $[n]$ such that $N_{G}(C)=[n]$ for
every odd cycle of $G$. Then

$J(G)^{(s)}=J(G)^{s}+\sum_{i=1}^{\lfloor\frac{s}{2}\rfloor}(x_{1}x_{2}\cdots
x_{n})^{i}J(G)^{s-2i}.$

Here, $\lfloor\frac{s}{2}\rfloor$ denotes the largest integer at most
$\frac{s}{2}$.

Let $C$ be an odd cycle of length $n=2r+1$. It is not difficult to see that
$C$ is not unmixed if $n\geq 9$. More precisely, we have $\deg(J(C))=r+1$ and

$\mathrm{Deg}(J(C))=\left\\{\begin{array}[]{ll}4t+2,&\hbox{$n=6t+3$;}\\\
4t+3,&\hbox{$n=6t+5$;}\\\ 4t+4,&\hbox{$n=6t+7$.}\end{array}\right.$

for all $t\geq 0$.

We now come to the main result of this section.

######  Theorem 2.4.

Let $J$ be the vertex cover ideal of an odd cycle of $C$ on vertex set $[n]$
with $n=2r+1$. Then $\operatorname{reg}(J^{(s)})=\operatorname{reg}(J^{s})$
for all $s\geq 1$.

###### Proof.

Put $t=\mathrm{Deg}(J)$. Then $t\geq r+1$ and so
$\mathrm{Deg}(J^{(s)})=\mathrm{Deg}(J^{s})=st$ for all $s\geq 1$ by
Proposition 2.3. Fix $s\geq 1$. We claim that

$J^{(s)}\cap\mathfrak{m}^{st}=J^{s}\cap\mathfrak{m}^{st}.$

In light of Proposition 2.3, it suffices to show that

$(x_{1}x_{2}\cdots x_{2r+1})^{i}J^{s-2i}\cap\mathfrak{m}^{st}\subseteq J^{s}$

for all $i=1,\ldots,\lfloor\frac{s}{2}\rfloor$. Fix $i$ and let $\alpha$ be a
monomial in $(x_{1}x_{2}\cdots x_{2r+1})^{i}J^{s-2i}\cap\mathfrak{m}^{st}$.
Then we may write $\alpha=(x_{1}x_{2}\cdots
x_{2r+1})^{i}\alpha_{1}\cdots\alpha_{s-2i}\mathbf{u}$, where $\alpha_{i}$ is a
minimal monomial generator of $J$ for each $i$ and $\mathbf{u}$ is some
monomial. Since $\deg(\alpha)\geq st$ and $\deg(\alpha_{i})\leq t$, it follows
that $\deg(\mathbf{u})\geq i$. This, together with the fact $(x_{1}x_{2}\cdots
x_{2r+1})x_{i}\in J^{2}$ for any $i\in[2r+1]$, implies $\alpha\in J^{s}$.
Thus, the claim is proved.

In view of Proposition 2.1, the result is immediate from the above claim.

######  Remark 2.5.

Proposition 2.1 is also useful in the study of powers of edge ideals. For
example, by Proposition 2.1, [9, Theorem 3.5] is a direct consequence of [9,
Corollary 3.3].

##  3\. Vertex decomposability via weak polymatroidality

In this section we prove that if $\Delta$ is a simplicial complex such that
$I_{\Delta}^{\vee}$ is weakly polymatroidal then $\Delta$ is vertex
decomposable. This particularly shows that for a monomial ideal, the property
of being weakly polymatroidal is stronger than the property of having linear
quotients. The converse implication of the above result is also discussed.

We first give an observation on the property of a shedding vertex. Let
$\Delta$ be a simplicial complex on vertex set $[n]$ with facets
$F_{1},F_{2},\ldots,F_{r}$. Assume that $k$ is a shedding vertex of $\Delta$
and assume without loss of generality that $k\in F_{i}$ for $i=1,\ldots,j$ and
$k\notin F_{i}$ for $i=j+1,\ldots,r$. Then $\mbox{lk}_{\Delta}(k)=\langle
F_{1}\setminus\\{k\\},\ldots,F_{j}\setminus\\{k\\}\rangle$ and
$\mbox{del}_{\Delta}(k)=\langle
F_{1}\setminus\\{k\\},\ldots,F_{j}\setminus\\{k\\},F_{j+1},\ldots,F_{r}\rangle=\langle
F_{j+1},\ldots,F_{r}\rangle$. This observation is useful in the following
proofs. Let $I$ be a monomial ideal. As usual, $G(I)$ denotes the set of
minimal monomial generators of $I$ and $\mathrm{supp}(I)$ is the set
$\cup_{u\in G(I)}\mathrm{supp}(u)$, where for a monomial $u$,
$\mathrm{supp}(u)$ denotes the set $\\{i\in[n]\colon\;x_{i}|u\\}$.

######  Theorem 3.1.

Let $\Delta$ be a simplicial complex on $[n]$ such that $I_{\Delta}^{\vee}$ is
weakly polymatroidal in some ordering of variables. Then $\Delta$ is vertex
decomposable.

###### Proof.

Since the vertex decomposability of a simplicial complex is independent of the
ordering of varaibles, we may assume $I_{\Delta}^{\vee}$ is weakly
polymatroidal itself. Let $\mathcal{F}(\Delta)$ denote the set of facets of
$\Delta$. In the following, we will use the induction on
$|\mathcal{F}(\Delta)|$, the number of facets of $\Delta$. If
$|\mathcal{F}(\Delta)|=1$, then $I_{\Delta}^{\vee}$ is generated by a single
monomial and so it is weakly polymatroidal automatically. Now assume
$|\mathcal{F}(\Delta)|\geq 2$. Let $k=\min\\{i\colon\;i\in F_{1}\cup\cdots\cup
F_{r},i\notin F_{1}\cap\cdots\cap F_{r}\\}$.

We first show that $k$ is a shedding vertex of $\Delta$. For this, let $F,G$
be facets of $\Delta$ such that $k\in F$ and $k\notin G$, respectively. Note
that $x_{\overline{F}}=x_{k+1}^{a_{k+1}}\cdots x_{n}^{a_{n}}$ and
$x_{\overline{G}}=x_{k}x_{k+1}^{b_{k+1}}\cdots x_{n}^{b_{n}}$, where
$a_{i},b_{i}\in\\{0,1\\}$ for all $i$ and they are minimal generators of
$I_{\Delta}^{\vee}$. Here, for $A\subseteq[n]$, $x_{\overline{A}}$ denotes the
monomial $\prod_{i\in[n]\setminus A}x_{i}$. This implies there exists $\ell>k$
such that $\mathbf{u}:=x_{k}x_{\overline{F}}/x_{\ell}$ is also a minimal
generators of $I_{\Delta}^{\vee}$ and so there exists a facet $H$ of $\Delta$
such that $\mathbf{u}=x_{\overline{H}}$. From this it follows that $k\notin H$
and $F\setminus\\{k\\}\subseteq H$. Since $H$ is a facet of $\Delta$, we have
$F\setminus\\{k\\}\subsetneq H$. This actually shows that none of facets of
$\mathrm{lk}_{\Delta}(k)$ is a facet of $\mathrm{del}_{\Delta}(k)$ and so $k$
is a shedding vertex of $\Delta$.

Set $\Delta_{1}:=\mathrm{lk}_{\Delta}(k)$ and
$\Delta_{2}:=\mathrm{del}_{\Delta}(k)$. Next we show $I_{\Delta_{1}}^{\vee}$
and $I_{\Delta_{2}}^{\vee}$ are both weakly polymatroidal. We will look
$\Delta_{1}$ and $\Delta_{2}$ upon as simplicial complexes on
$V:=[n]\setminus\\{k\\}$. Then $I_{\Delta_{i}}^{\vee}=(x_{V\setminus
F}\colon\;F\in\mathcal{F}(\Delta_{i}))$. Note that

(1)
$G(I_{\Delta}^{\vee})=G(I_{\Delta_{1}}^{\vee})\bigsqcup\\{x_{k}u\colon\;u\in
G(I_{\Delta_{2}}^{\vee})\\}.$

Moreover, $\mathrm{supp}(I_{\Delta_{i}}^{\vee})\subseteq\\{k+1,\ldots,n\\}$
for $i=1,2$.

Let $\mathbf{u}=x_{k+1}^{a_{k+1}}\cdots x_{n}^{a_{n}}$ and
$\mathbf{v}=x_{k+1}^{b_{k+1}}\cdots x_{n}^{b_{n}}$ be distinct elements in
$G(I_{\Delta_{1}}^{\vee})$ such that
$a_{k+1}=b_{k+1},\ldots,a_{k+i-1}=b_{k+i-1}$ and $a_{k+i}<b_{k+i}$. Then,
since $I_{\Delta}^{\vee}$ is weakly polymatroidal, there exists $j>i\geq 1$
such that $\mathbf{w}:=x_{k+i}\mathbf{u}/x_{k+j}\in G(I_{\Delta}^{\vee})$.
This, together with the decomposition in (1), implies $\mathbf{w}\in
G(I_{\Delta_{1}}^{\vee})$. Thus, we have proven that $I_{\Delta_{1}}^{\vee}$
is weakly polymatroidal. Similarly, we can prove $I_{\Delta_{2}}^{\vee}$ is
weakly polymatroidal. By induction hypothesis, we have $\Delta_{i}$ is vertex
decomposable for $i=1,2$ and so $\Delta$ is vertex decomposable, as required.

Let $G$ be a simple graph. A subset $A$ of $V(G)$ is an independent set of $G$
if for any $i,j\in A$, the pair $\\{i,j\\}$ is not an edge of $G$. The
independence complex of $G$ is the collection of all independent sets of $G$.
We call $G$ to be vertex decomposable if its independence complex is vertex
decomposable. If we let $\Delta$ be the independence complex of $G$, then the
Stanley-Reisner ideal $I_{\Delta}$ is the edge ideal $I(G)$ and its Alexander
duality $I_{\Delta}^{\vee}$ is the vertex cover ideal $J(G)$.

The converse of Theorem 3.1 is true in some cases as shown by the following
corollary.

######  Corollary 3.2.

Let $G$ be either a cactus graph or a bipartite graphs or a chordal graph.
Assume further that $G$ is unmixed. Then the following are equivalent:

  1. (1)

$R/I(G)$ is Cohen-Macaulay;

  2. (2)

$G$ is vertex indecomposable;

  3. (3)

$J(G)$ is weakly polymatroidal (in some ordering of variables);

  4. (4)

$J(G)^{k}$ is weakly polymatroidal (in some ordering of variables) for all
$s\geq 1$.

In particular, if $\Delta$ is the independence complex of either a cactus
graph or a bipartite graph or a chordal graph, then $I_{\Delta}^{\vee}$ is
weakly polymatroidal in some ordering of variables if and only if $\Delta$ is
vertex decomposable and pure.

###### Proof.

(1)$\Rightarrow$(4) Suppose that $R/I(G)$ is Cohen-Macaulay. If $G$ is either
a cactus graph or a chordal graph, then $J(G)^{s}$ is weakly polymatroidal by
[17, Theorem 4.3] and [18, Theorem 1.7] respectively. If $G$ is bipartite,
then $G$ comes from a finite poset $P$, see [12, Theorem 9.1.3]. Using the
notation in [5], we may write $I(G)=I_{2}(P)$. From this it follows that
$(I_{\Delta}^{\vee})^{s}=(H_{2}(P))^{s}$ is weakly polymatroidal for all
$s\geq 1$ by [5, Theorem 2.2].

(4)$\Rightarrow$(3) Automatically.

(3)$\Rightarrow$(2) It follows from Theorem 3.1.

(2)$\Rightarrow$(1) Every vertex decomposable graph is sequentially Cohen-
Macaulay and an unmixed sequentially Cohen-Macaulay graph is a Cohen-Macaulay
graph.

######  Corollary 3.3.

Let $C$ be a cycle of size $5$. Then
$\operatorname{reg}(J(C)^{(s)})=\operatorname{reg}(J(C)^{s})=3s.$

###### Proof.

It is known that if $C$ is a cycle of size $n$, then $R/I(C)$ is Cohen-
Macaulay if and only if $R/I(C)$ is sequentially Cohen-Macaulay if and only if
$n\in\\{3,5\\}$, see [6, Proposition 4.1]. By this fact the result follows
from Theorem 2.4 together with Corollary 3.2.

We also have the following partial converse of Theorem 3.1.

######  Proposition 3.4.

Let $\Delta$ be a pure simplicial complex on $[n]$. If $1$ is a shedding
vertex of $\Delta$ such that $I_{\Delta_{i}}^{\vee}$ is weakly polymatroidal
for $i=1,2$, then $I_{\Delta}^{\vee}$ is weakly polymatroidal. Here,
$\Delta_{1}:=\mathrm{lk}_{\Delta}(1)$ and
$\Delta_{2}:=\mathrm{del}_{\Delta}(1)$.

###### Proof.

Since $1$ is a shedding vertex of $\Delta$, we have

$G(I_{\Delta}^{\vee})=G(I_{\Delta_{1}}^{\vee})\bigsqcup\\{x_{1}u\colon\;u\in
G(I_{\Delta_{2}}^{\vee})\\}.$

Note that $\mathrm{supp}(u)\subseteq\\{2,\ldots,n\\}$ for any $u\in
G(I_{\Delta_{1}}^{\vee})\bigsqcup G(I_{\Delta_{2}}^{\vee})$.

Let $\mathbf{u}=x_{1}^{a_{1}}\cdots x_{n}^{a_{n}}$ and
$\mathbf{v}=x_{1}^{b_{1}}\cdots x_{n}^{b_{n}}$ be monomials belonging to
$G(I_{\Delta}^{\vee})$ satisfying $a_{1}=b_{1},\ldots,a_{i-1}=b_{i-1}$ and
$a_{i}<b_{i}$. We need to find a monomial $\mathbf{w}\in G(I_{\Delta}^{\vee})$
such that $\mathbf{w}=x_{i}\mathbf{u}/x_{j}$ for some $j>i$. If either
$\\{\mathbf{u,v}\\}\subseteq G(I_{\Delta_{1}}^{\vee})$ or
$\\{\mathbf{u,v}\\}\subseteq\\{x_{1}u\colon\;u\in
G(I_{\Delta_{2}}^{\vee})\\}$, the existence of $\mathbf{w}$ follows by the
assumption that $I_{\Delta_{i}}^{\vee}$ is weakly polymatroidal for $i=1,2$.
So we only need to consider the case that $\mathbf{u}\in
G(I_{\Delta_{1}}^{\vee})$ and $\mathbf{v}\in\\{x_{1}u\colon\;u\in
G(I_{\Delta_{2}}^{\vee})\\}$. Note that $i=1$ in this case. Moreover, since
$1$ is a shedding vertex, there exists $\mathbf{v_{1}}\in
G(I_{\Delta_{2}}^{\vee})$ such that $\mathbf{u}$ divides $\mathbf{v_{1}}$.
This implies $\mathbf{v_{1}}=\mathbf{u}x_{j}$ for some $j>1$ by the purity of
$\Delta$. Hence $\mathbf{w:}=x_{1}\mathbf{v_{1}}=x_{1}\mathbf{u}/x_{j}$ meets
the requirement and so we are done.

Proposition 3.4 together with Corollary 3.2 leads us to present the following.

######  Conjecture 1.

If $\Delta$ is a vertex decomposable pure simplicial complex, then
$I_{\Delta}^{\vee}$ is weakly polymatroidal.

A weak form of this conjecture is:

######  Conjecture 2.

If $G$ is an unmixed vertex decomposable graph, then $J(G)$ is weakly
polymatroidal.

The condition that $G$ is unmixed is necessary in the above conjecture. For
example, if $G$ is a star graph with more than two vertices of degree 1, then
$G$ is vertex decomposable, but $J(G)$ is not weakly polymatroidal.

The following is another example in support of Conjecture 2.

######  Proposition 3.5.

Let $G$ be a Cohen-Macaulay graph of girth at least 5. Then $J(G)$ is weakly
polymatroidal.

###### Proof.

By [16, Theorem 2.4], we have $G$ is a $\mathcal{PC}$ graph. Recall an induced
5-cycle of $G$ is called basic if it does not contains two adjacent vertices
of degree three or more in $G$, and an edge is called a pendant if it contains
a vertex of degree 1. Let $C^{1},\ldots,C^{k}$ be the set of all basic
5-cycles of $G$ and let $L^{1},\ldots,L^{l}$ be the set of all pendants of
$G$. Recall that $G$ is a $\mathcal{PC}$ graph if $V(G)$ can be partitioned
into $V(G)=V(C^{1})\sqcup\cdots\sqcup V(C^{k})\sqcup
V(L^{1})\sqcup\cdots\sqcup V(L^{l})$.

Label the vertices of $C^{i}$ successively by
$x_{i1},x_{i4},x_{i2},x_{i3},x_{i5}$ such that $x_{i3},x_{i4},x_{i5}$ are
vertices of degree 2 for $i=1,\ldots,k$, and let $y_{i1},y_{i2}$ be vertices
of $L^{i}$ such that $y_{i2}$ has degree 1 for $i=1,\ldots,l$. We work with
the following ordering of variables:

$x_{11}>\cdots>x_{15}>\cdots>x_{k1}>\cdots
x_{k5}>y_{11}>y_{12}>\cdots>y_{l1}>y_{l2}.$

To prove $J(G)$ is weakly polymatroidal, we let $f,g$ be minimal monomial
generators of $J(G)$ with $f\neq g$ and let $z$ be a variable such that
$\deg_{z^{\prime}}f=\deg_{z^{\prime}}g$ for $z^{\prime}>z$ and
$\deg_{z}g<\deg_{z}f$. We need to find a variable $w<z$ such that $zg/w\in
J(G)$. To this end, for each monomial $h\in J(G)$, we write $h$ as following:

$h=h(C^{1})\cdots h(C^{k})h(L^{1})\cdots h(L^{l}),$

where $h(C^{i})$ and $h(L^{j})$ are monomials such that
$\mathrm{supp}(h(C^{i}))\subseteq V(C^{i})$ for $i=1,\ldots,k$ and
$\mathrm{supp}(h(L^{j}))\subseteq V(L^{j})$ for $j=1,\ldots,l$. We consider
the following cases:

Case 1 $z=x_{i1}$ for some $i$: Then
$g(C^{i})\in\\{x_{i2}x_{i4}x_{i5},x_{i3}x_{i4}x_{i5}\\}$. We set $w=x_{i4}$ if
$g(C^{i})=x_{i2}x_{i4}x_{i5}$ and set $w=x_{i5}$ if
$g(C^{i})=x_{i3}x_{i4}x_{i5}$. Then $zg/w\in J(G)$.

Case 2 $z=x_{i2}$ for some $i$: Then
$g(C^{i})\in\\{x_{i1}x_{i4}x_{i3},x_{i3}x_{i4}x_{i5}\\}$. We set $w=x_{i4}$ if
$g(C^{i})=x_{i1}x_{i4}x_{i3}$, and set $w=x_{i3}$ and set $w=x_{i4}$ if
$g(C^{i})=x_{i3}x_{i4}x_{i5}$. Then $zg/w\in J(G)$.

Case 3 $z=x_{i3}$ for some $i$: Then $g(C^{i})=x_{i1}x_{i5}x_{i2}$. We set
$w=x_{i5}$.

Case 4 $z=x_{i4}$ for some $i$: This case is impossible.

Case 5 $z=x_{i5}$ for some $i$: This case is impossible again.

Case 6 $z=y_{i1}$ for some $i$: Then $h(L_{i})=y_{i2}$. We set $w=y_{i2}$.

Case 7 $z=y_{i2}$ for some $i$: This case is impossible again.

Thus, in all possible cases, we find a variable $w$ which meets the
requirement. This completes the proof.

##  4\. Powers of cover ideals of clique-whiskering graphs

Let $W=G^{\pi}$ be the fully clique-whiskering of some graph $G$ by some
clique vertex-partition $\pi$ of $G$. In this section we prove $J(W)^{s}$ is
weakly polymatroidal for all $s\geq 1$. As a consequence,
$\operatorname{reg}(J(W)^{s})=\operatorname{reg}(J(W)^{(s)})=s|V(G)|$ for all
$s\geq 1$.

For convenience, we introduce the notions of a simplicial co-complex and the
face ideal of a simplicial co-complex with respect to a partition.

######  Definition 4.1.

Let $V$ be a finite set. We say that a collection $\nabla$ of subsets of $V$
is a simplicial co-complex on $V$ if whenever $F\in\nabla$ and $F\subseteq
G\subseteq V$ one has $G\in\nabla$. Assume that $V$ has a partition
$V=V_{1}\sqcup\cdots\sqcup V_{t}$ and assume that
$V_{i}=\\{x_{i1},\ldots,x_{ik_{i}}\\}$ for $i=1,\ldots,t$. For each face
$F\in\nabla$, we put

$u_{F}:=\prod_{x_{ij}\in F}x_{ij}\prod_{i\in[t]}y_{i}^{k_{i}-|F\cap W_{i}|}.$

Then the face ideal of $\nabla$ with respect to this partition is the
following monomial ideal $J$ in the polynomial ring
$k[x_{11},\ldots,x_{1,k_{1}},\ldots,x_{t1},\ldots,x_{1,k_{t}},y_{1},\ldots,y_{t}]$:

$J=(u_{F}:F\in\nabla).$

######  Remark 4.2.

When $|V_{1}|=\cdots=|V_{t}|=1$, the face ideal of a simplicial co-complex is
the same as the face ideal of a simplicial complex in [14] in essence.

######  Proposition 4.3.

Let $\nabla$ be a simplicial co-complex on $V$ and assume that $V$ has a
partition $V=V_{1}\sqcup\cdots\sqcup V_{t}$ with
$V_{i}=\\{x_{i1},\ldots,x_{ik_{i}}\\}$ for $i=1,\ldots,t$. Denote by $J$ the
face ideal of $\nabla$ with respect to this partition. Then $J^{s}$ is weakly
polymatroidal for each $s\geq 1$ in the ordering:
$x_{11}>\cdots>x_{1k_{1}}>\cdots>x_{t1}>\cdots>x_{tk_{t}}>y_{1}>\cdots>y_{n}$.

###### Proof.

Let $\alpha,\beta$ be the minimal monomial generators of $J^{s}$ with
$\alpha\neq\beta$. We may write

$\alpha=u_{F_{1}}u_{F_{2}}\cdots u_{F_{s}}=u_{1}\cdots
u_{t}y_{1}^{sk_{1}-\deg(u_{1})}\cdots y_{t}^{sk_{t}-\deg(u_{t})},$

and

$\beta=u_{G_{1}}u_{G_{2}}\cdots u_{G_{s}}=v_{1}\cdots
v_{t}y_{1}^{sk_{1}-\deg(v_{1})}\cdots y_{t}^{sk_{t}-\deg(v_{t})}.$

Here $F_{i}\in\nabla,G_{i}\in\nabla$ for all $i\in[s]$, and
$\mathrm{supp}(u_{i})\cup\mathrm{supp}(v_{i})\subseteq V_{i}$ for
$i=1,\ldots,t$. Since $\alpha\neq\beta$, there exists a variable $z<y_{1}$
such that $\deg_{w}(\alpha)=\deg_{w}(\beta)$ for all $w<z$ and
$\deg_{z}(\alpha)<\deg_{z}(\beta)$. Suppose that $z=x_{ij}$, where $1\leq
i\leq t$ and $1\leq j\leq k_{i}$. Then $\deg_{x_{ij}}\alpha\leq s-1$ and so
there exists $l\in[s]$, such that $x_{ij}\notin F_{l}\cap W_{i}$. Say $l=1$.
Put $F_{1}^{\prime}:=F_{1}\cup\\{x_{ij}\\}$ and let

$\gamma:=u_{F_{1}^{\prime}}u_{F_{2}}\cdots u_{F_{s}}.$

Then $\gamma=x_{ij}\alpha/y_{i}$. From this it follows that $J^{s}$ is weakly
polymatroidal.

######  Theorem 4.4.

Let $W=G^{\pi}$, where $G$ is a simple graph and $\pi=(W_{1},\ldots,W_{t})$ is
a clique vertex-partition of $G$. Then $J(W)^{s}$ is weakly polymatroidal for
every $s\geq 1$.

###### Proof.

Let $\nabla:=\\{C\cap V(G)\colon\;C\mbox{ is a minimal vertex cover of }W\\}.$
Then $\nabla$ is a simplicial co-complex on $V(G)$. Moreover, $J(W)$ coincides
with the face ideal of $\Delta$ with respect to the partition $\pi$. Now, the
result follows from Proposition 4.3.

As a direct consequence of Theorem 4.4 we have $G^{\pi}$ is vertex
decomposable, see Theorem 3.1. This recovers [3, Theorem 3.3]. Another
consequence of Theorem 4.4 is as follows.

######  Corollary 4.5.

Let $W=G^{\pi}$ as in Theorem 3.1. Then
$\operatorname{reg}(J(W)^{(s)})=\operatorname{reg}(J(W)^{s})=s|V(G)|$ for all
$s\geq 1$.

###### Proof.

It follows from Theorem 4.4 that $\operatorname{reg}(J(W)^{s})=s|V(G)|$. By
[20, Corollary 4.4], we have $\operatorname{reg}(J(W)^{(s)})=s|V(G)|$.

Finally in this section we present a class of graphs $G$ for which the
symbolic powers $J(G)^{(s)}$ are weakly polymatroidal.

######  Proposition 4.6.

Let $\nabla$ be a simplicial co-complex on $[n]$ such that that for $i\in[n]$,
there exist $F,G\in\nabla$ such that $F\cup G=[n]$ and $F\cap G=\\{i\\}$. Let
$J$ denote the face ideal of $\nabla$ with respect to the trivial partition
(i.e. a partition in which every part contains exactly one vertex). For
positive integers $s,t$ with $2t\leq s$, let $L_{s,t}$ denote the ideal

$J(\nabla)^{s}+(x_{[n]}y_{[n]})J^{s-2}+(x_{[n]}y_{[n]})^{2}J^{s-4}+\cdots+(x_{[n]}y_{[n]})^{t}J^{s-2t}.$

Then $L_{s,t}$ is weakly polymatroidal in the ordering:
$x_{1}>x_{2}>\cdots>x_{n}>y_{1}>\cdots>y_{n}$.

###### Proof.

Let $\alpha,\beta$ be the minimal monomial generators of $L_{s,t}$ with
$\alpha\neq\beta$. We may write

$\alpha=(x_{[n]}y_{([n])})^{k}u_{F_{1}}\cdots
u_{F_{s-2k}}=x_{1}^{a_{1}+k}\cdots x_{n}^{a_{n}+k}y_{1}^{s-k-a_{1}}\cdots
y_{n}^{s-k-a_{n}}$

and

$\beta=(x_{[n]}y_{([n])})^{\ell}u_{G_{1}}\cdots
u_{G_{s-2\ell}}=x_{1}^{b_{1}+\ell}\cdots x_{n}^{b_{n}+\ell}y_{1}^{s-\ell-
b_{1}}\cdots y_{n}^{s-\ell-b_{n}}.$

Here, $0\leq k,\ell\leq t$, and $F_{i},G_{j}\in\nabla$ for $i=1,\ldots,s-2k$
and $j=1,\ldots,s-2\ell$. Since $\alpha\neq\beta$, there exists $i\in[n]$ such
that $a_{1}+k=b_{1}+\ell,\ldots,a_{i-1}+k=b_{i-1}+\ell$ and
$a_{i}+k<b_{i}+\ell$. We consider the following two cases.

  1. (1)

If $k\leq\ell$, then $a_{i}<s-\ell-k\leq s-2k$ and so there exits $j\in[k]$
such that $i\notin F_{j}$. Say $j=1$. Then put $F_{1}^{\prime}=F_{1}\cup{i}$
and $\gamma:=(x_{[n]}y_{([n])})^{k}u_{F_{1}^{\prime}}u_{F_{2}}\cdots
u_{F_{s-2k}}$. It is easy to check that $\gamma$ is a minimal monomial
generator of $L_{s,t}$ and moreover $\gamma=x_{i}\alpha/y_{i}$.

  2. (2)

If $k>\ell$, then $k\geq 1$. By the assumption, there are $F,G\in\nabla$ such
that $F\cup G=[n]$ and $F\cap G=\\{i\\}$. Put
$\gamma=(x_{[n]}y_{([n])})^{k-1}u_{F_{1}}\cdots u_{F_{s-2k}}u_{F}u_{G}$, then
$\gamma=(x_{i}\alpha)/y_{i}$ is a minimal generator of $L_{s,t}$.

Thus, we can find a monomial $\gamma$ which meets the requirement in both
cases and this implies $L_{s,t}$ is weakly polymatroidal.

######  Corollary 4.7.

Let $W$ be the whisker graph of a cycle. Then $J(W)^{(s)}$ is weakly
polymatroidal for every $s\geq 1$.

###### Proof.

For any cycle $C$ on $[n]$ and for any $i\in[n]$, there exist vertex covers
$F_{1}$ and $F_{2}$ of $C$ such that $F_{1}\cap F_{2}=\\{i\\}$ and $F_{1}\cup
F_{2}=[n]$. Thus, the result follows from Proposition 4.6 as well as [13,
Proposition 5.3].

##  5\. Appendix

In this section we will explain why the original proof of [17, Theorem 4.3] is
not flawless, and then give a corrected proof. We will adopt the notions from
[17] in this section.

The author of [17] considers several cases in the proof of [17, Theorem 4.3].
In case 4, he assumes that $z=y_{i3}$, then deduces that
$\\{y_{i1},y_{i2},y_{i5}\\}\subseteq\mathrm{supp}(g_{j})$ for some $1\leq
j\leq k$. Let us see the following example.

######  Example 5.1.

Suppose that $m=t=0$ and $n=1$. In this case $G$ is just a 5-cycle. Let
$f=f_{1}f_{2}=(y_{1}y_{2}y_{3})(y_{3}y_{4}y_{5})=y_{1}y_{2}y_{3}^{2}y_{4}y_{5}$
and
$g=g_{1}g_{2}=(y_{2}y_{4}y_{5})(y_{1}y_{3}y_{4})=y_{1}y_{2}y_{3}y_{4}^{2}y_{5}$
be minimal monomial generators of $J(G)^{2}$. Then
$\deg_{y_{i}}f=\deg_{y_{i}}g$ for $i=1,2$ and $\deg_{y_{3}}f>\deg_{y_{3}}g$.
But, it is clear $\\{y_{1},y_{2},y_{5}\\}\nsubseteq\mathrm{supp}(g_{j})$ for
$j=1,2$. Furthermore, although
$\\{y_{1},y_{2},y_{5}\\}\subseteq\mathrm{supp}(g)$,
$\frac{g}{y_{1}y_{2}y_{5}}$ does not belong to $J(G)$ and one can easily check
that $y_{3}g/y_{5}\notin J(G)^{2}$.

This example shows the proof of case 4 is not correct. The one of case 5 is
not correct in a similar way. In the sequel, we give a new proof in case 4 and
case 5.

######  Theorem 5.2.

([17, Theorem 4.3]) Let $G$ be a Cohen-Macaulay cactus graph. Then $J(G)^{s}$
is weakly polymatroidal for all $k\geq 1$.

###### Proof.

As in the original proof of [17, Theorem 4.3], we may assume that $V(G)$ is
the disjoint union of

$F_{1},\ldots,F_{m},G_{1},\ldots,G_{n},L_{1},\ldots,L_{t}$

such that the induced graph of $G$ on $F_{i}$ is a simplex, the induced graph
of $G$ on $G_{j}$ is a a basic 5-cycle, and $L_{l}$ is an edge which belongs
to a 4-cycle of $G$ for each $ij,l$.

Consider the following ordering of the variables (corresponding to the
vertices of $G$):

$x_{11}>\cdots>x_{1k_{1}}>\cdots>x_{m1}>\cdots>x_{mk_{m}}>y_{11}>\cdots>y_{15}>$
$\cdots>y_{n1}>\cdots>y_{n5}>z_{11}>z_{12}>\cdots>z_{t1}>z_{t2},$

where $F_{i}=\\{{x_{i1},\ldots,x_{ik_{i}}}\\},2\leq k_{i}\leq 3$ and
${x_{ib_{i}},\ldots,x_{ik_{i}}}$ are the free vertices of $F_{i}$ for all $i$,
and $y_{j1},y_{j2},y_{j3},y_{j4},y_{j5}$ are the vertices of $G_{j}$ such that
the vertices $y_{j3},y_{j4},y_{j5}$ are of degree two for all $j$, and
$z_{i1},z_{i2}$ are the vertices of $L_{i}$ of degree two for all $i$. Note
that for each $i\in[n]$, each minimal vertex cover $C$ of $G$ contains exactly
one of the subsets

$\\{y_{i1},y_{i2},y_{i5}\\},\\{y_{i2},y_{i4},y_{i5}\\},\\{y_{i1},y_{i2},y_{i3}\\},\\{y_{i1},y_{i3},y_{i4}\\},\\{y_{i2},y_{i4},y_{i5}\\}$

Now, let $f=f_{1}\cdots f_{k}$ and $g=g_{1}\cdots g_{k}$ be elements in the
minimal generating set of $J(G)^{k}$ with $f_{s},g_{s}\in J(G)$ for $1\leq
s\leq k$. Suppose that there exists a variable $z$ such that
$\mathrm{deg}_{z^{{}^{\prime}}}f=\mathrm{deg}_{z^{{}^{\prime}}}g$ for any
variable $z^{{}^{\prime}}>z$ and $\mathrm{deg}_{z}f>\mathrm{deg}_{z}g$. We
only need to find a variable $w<z$ such that $zg/w\in J(G)^{2}$ in the cases
that $z=y_{i3}$ and that $z=y_{i4}$ for some $i$, which correspond to case 4
and case 5 of the original proof, respectively. To this end, we introduce some
notions.

Let $i$ be the number in $z=y_{i3}$ and $z=y_{i4}$. First we set

$f_{abc}=|\\{s:\\{y_{ia},y_{ib},y_{ic}\\}\subseteq\mathrm{supp}(f_{s})\\}\mbox{
and
}g_{abc}=|\\{s:\\{y_{ia},y_{ib},y_{ic}\\}\subseteq\mathrm{supp}(g_{s})\\}|,$

where $\\{y_{ia},y_{ib},y_{ic}\\}$ is a minimal vertex cover of $G_{i}$ for
each triple $\\{a,b,c\\}$.

Next, we let $T$ denote the subgraph of $G$ induced on the subset
$V(G)\setminus\\{y_{i3},y_{i4},y_{i5}\\}$, and for $a=1,2$ we set

$T_{a}=\\{z\in V(T)\colon\;\mbox{ there exists a path in }T\mbox{ connecting
}z\mbox{ and }y_{ia}\\}.$

We will assume $G$ is connected. Since $G$ is cactus, we have $T_{a}\cap
T_{b}=\emptyset$ and $V(T)=T_{1}\sqcup\\{y_{i1},y_{i2}\\}\sqcup T_{2}$.

Case that $z=y_{i3}$: If $g_{125}\neq 0$, there exists $s\in\\{1,\cdots,k\\}$
such that $\\{y_{i1},y_{i2},y_{i5}\\}\subseteq\mathrm{supp}(g_{s})$. Since the
subset $(\mathrm{supp}(g_{s})\backslash\\{y_{i5}\\})\cup\\{y_{i3}\\}$ is again
a minimal vertex cover of $G$, we have $y_{i3}g/y_{i5}\in J(G)^{k}$ and so we
are done. Note that $g_{125}\neq 0$ if $k=1$, we assume now that $g_{125}=0$
and $k\geq 2$.

Because $\mathrm{deg}_{y_{ia}}f=\mathrm{deg}_{y_{ia}}g$ for $a=1,2$ and
$\mathrm{deg}_{y_{i3}}f>\mathrm{deg}_{y_{i3}}$, we have the following
formulas:

$f_{134}+f_{123}+f_{125}=g_{134}+g_{123}+g_{125};$
$f_{245}+f_{123}+f_{125}=g_{245}+g_{123}+g_{125};$
$f_{134}+f_{123}+f_{345}>g_{134}+g_{123}+g_{345};$
$f_{134}+f_{245}+f_{123}+f_{125}+f_{345}=g_{134}+g_{245}+g_{123}+g_{125}+g_{345}=k.$

Due to $g_{125}=0$, we obtain successively that

$f_{123}>g_{123},f_{345}>g_{345},f_{245}<g_{245}\mbox{ and }f_{134}<g_{134}.$

Thus, there exist $p,q\in\\{1,\cdots,k\\}$ with $p\neq q$ such that
$\\{y_{i2},y_{i4},y_{i5}\\}\subseteq g_{p}$ and
$\\{y_{i1},y_{i3},y_{i4}\\}\subseteq g_{q}$. say $p=1$ and $q=2$, We need to
prove that $y_{i3}g_{1}g_{2}/y_{i4}$ belongs to $J(G)^{2}$. If this is done,
then $y_{i3}g/y_{i4}$ belongs to $J(G)^{k}$ and we are done.

We may write $g_{1},g_{2}$ as follows:

$g_{1}=y_{i2}y_{i4}y_{i5}u_{1}u_{2}\mbox{ and
}g_{2}=y_{i1}y_{i3}y_{i4}v_{1}v_{2}$

such that $\mathrm{supp}(u_{i})\cup\mathrm{supp}(v_{i})\subseteq T_{i}$ for
$i=1,2$.

Then we have the following decomposition:

$y_{i3}g_{1}g_{2}/y_{i4}=(y_{i3}y_{i4}y_{i5}u_{1}u_{2})(y_{i1}y_{i2}y_{i3}v_{1}v_{2})=(y_{i3}y_{i4}y_{i5}u_{1}v_{2})(y_{i1}y_{i2}y_{i3}v_{1}u_{2}).$

We next check that both $\mathrm{supp}(y_{i3}y_{i4}y_{i5}u_{1}v_{2})$ and
$\mathrm{supp}(y_{i1}y_{i2}y_{i3}v_{1}u_{2})$ are vertex covers of $G$. Denote
$V_{1}=\mathrm{supp}(y_{i3}y_{i4}y_{i5}u_{1}v_{2})$ and
$V_{2}=\mathrm{supp}(y_{i1}y_{i2}y_{i3}v_{1}u_{2})$. Let $e=\\{z_{1},z_{2}\\}$
be an edge of $E(G)$.

If $e\subseteq V(G_{i})$, then it is clear that $V_{1}\cap e\neq\emptyset$ and
$V_{2}\cap e\neq\emptyset$;

If $z_{1}=y_{i1}$ and $z_{2}\in T_{1}$ then $z_{2}\in\mathrm{supp}(u_{1})\cap
e$. This implies $V_{1}\cap e\neq\emptyset$ and $V_{2}\cap e\neq\emptyset$;
Similarly, we have if $z_{1}=y_{i2}$ and $z_{2}\in T_{2}$ then $V_{1}\cap
e\neq\emptyset$ and $V_{2}\cap e\neq\emptyset$.

Finally suppose that $e\cap V(G_{i})=\emptyset$. Then either $e\subseteq
E(T_{1})$ or $e\subseteq E(T_{2})$. In the case that $e\subseteq E(T_{1})$, we
have $\mathrm{supp}{(u_{1})}\cap e\neq\emptyset$ and
$\mathrm{supp}{(v_{1})}\cap e\neq\emptyset$ and so $V_{1}\cap e\neq\emptyset$
and $V_{2}\cap e\neq\emptyset$. The case that $e\subseteq E(T_{2})$ is
similar.

Thus, both $V_{1}$ and $V_{2}$ are vertex covers of $G$ indeed.

Case that $z=y_{i4}$: We may assume $k\geq 2$. Because
$\mathrm{deg}_{y_{ia}}f=\mathrm{deg}_{y_{ia}}g$ for $a=1,2,3$ and
$\mathrm{deg}_{y_{i4}}f>\mathrm{deg}_{y_{i4}}$, we have the following
formulas:

$f_{134}+f_{123}+f_{125}=g_{134}+g_{123}+g_{125};$
$f_{245}+f_{123}+f_{125}=g_{245}+g_{123}+g_{125};$
$f_{134}+f_{123}+f_{345}=g_{134}+g_{123}+g_{345};$
$f_{134}+f_{245}+f_{345}>g_{134}+g_{245}+g_{345};$
$f_{134}+f_{245}+f_{123}+f_{125}+f_{345}=g_{134}+g_{245}+g_{123}+g_{125}+g_{345}.$

From these we obtain successively that

$f_{134}>g_{134},f_{345}<g_{345},f_{245}>g_{245}\mbox{ and }f_{125}<g_{125}$

Thus, there exist $p,q\in\\{1,\cdots,k\\}$ such that
$\\{y_{i3},y_{i4},y_{i5}\\}\subseteq g_{p}$ and
$\\{y_{i1},y_{i2},y_{i5}\\}\subseteq g_{q}$. Say $p=1$ and $q=2$. We only need
to prove that $y_{i4}g_{1}g_{2}/y_{i5}$ belongs to $J(G)^{2}$.

For this we decompose $g_{1}$ and $g_{2}$ as follows:

$g_{1}=y_{i3}y_{i4}y_{i5}u_{1}u_{2}\mbox{ and
}g_{2}=y_{i1}y_{i2}y_{i5}v_{1}v_{2}$

such that $\mathrm{supp}(u_{i})\cup\mathrm{supp}(v_{i})\subseteq T_{i}$ for
$i=1,2$.

Then we have

$y_{i4}g_{1}g_{2}/y_{i5}=(y_{i3}y_{i4}y_{i5}u_{1}u_{2})(y_{i1}y_{i2}y_{i4}v_{1}v_{2})=(y_{i2}y_{i4}y_{i5}u_{1}v_{2})(y_{i1}y_{i3}y_{i4}v_{1}u_{2}).$

We next check that both $\mathrm{supp}(y_{i2}y_{i4}y_{i5}u_{1}v_{2})$ and
$\mathrm{supp}(y_{i1}y_{i3}y_{i4}v_{1}u_{2})$ are vertex covers of $G$. Denote
$V_{1}=\mathrm{supp}(y_{i2}y_{i4}y_{i5}u_{1}v_{2})$ and
$V_{2}=\mathrm{supp}(y_{i1}y_{i3}y_{i4}v_{1}u_{2})$. Let $e=\\{z_{1},z_{2}\\}$
be an edge of $E(G)$.

If $e\subseteq V(G_{i})$, then it is clear that $V_{1}\cap e\neq\emptyset$ and
$V_{2}\cap e\neq\emptyset$;

If $z_{1}=y_{i1}$ and $z_{2}\in T_{1}$ then $z_{2}\in\mathrm{supp}(u_{1})\cap
e$. This implies $V_{1}\cap e\neq\emptyset$ and $V_{2}\cap e\neq\emptyset$;
Similarly, we have if $z_{1}=y_{i2}$ and $z_{2}\in T_{2}$ then $V_{1}\cap
e\neq\emptyset$ and $V_{2}\cap e\neq\emptyset$.

Finally suppose that $e\cap V(G_{i})=\emptyset$. Then either $e\subseteq
E(T_{1})$ or $e\subseteq E(T_{2})$. In the case that $e\subseteq E(T_{1})$, we
have $\mathrm{supp}{(u_{1})}\cap e\neq\emptyset$ and
$\mathrm{supp}{(v_{1})}\cap e\neq\emptyset$ and so $V_{1}\cap e\neq\emptyset$
and $V_{2}\cap e\neq\emptyset$. The other case is similar.

Thus, both $V_{1}$ and $V_{2}$ are vertex covers of $G$ indeed.

Acknowledgment This research is supported by NSFC (No. 11971338)

## References

  * [1] A. Banerjee, S. Beyarslan, H. T. H$\mathrm{\grave{a}}$,  Regularity of Edge Ideals and Their Powers, Springer Proceedings in Mathematics and Statistics, 277 (2019) 17–52.
  * [2] A. Bjorner, M. Wachs, Shellable nonpure complexes and posets. I, Trans. Amer. Math. Soc. 348 (1996) 1299–1327.
  * [3] D. Cook II, U. Nagel, Cohen-Macaulay graphs and face vectors of flag complexes, SIAM J. Discrete Math. 26 (2012) 89–101.
  * [4] L. X. Dung, T. T. Hien, H. D. Nguyen, T. N. Trung, Regularity and Koszul property of symbolic powers of monomial ideals, Math. Z. 298 (2021) 1487–1522.
  * [5] V. Ene, J. Herzog, F. Mohammadi, Monomial ideals and toric rings of Hibi type arising from a finite poset, European Journal of Combinatorics, 2011 (32) 404–421.
  * [6] A. C. Francisco; A. V. Tuyl, Adam, Sequentially Cohen-Macaulay edge ideals, Proc. Amer. Math. Soc. 135 (2007) 2327–2337.
  * [7] Y. Gu, H. T. H$\mathrm{\grave{a}}$, J.W. Skelton, Symbolic powers of cover ideals of graphs and Koszul property,  Internat. J. Algebra Comput. 31 (2021) 865–881.
  * [8] J. Guo, M. Li, T. Wu, A new view toward vertex decomposable graphs, Discrete Mathematics 345 (2022) 112953
  * [9] A. V. Jayanthan, R. Kumar, Regularity of symbolic powers of edge ideals, Journal of Pure and Applied Algebra 224 (2020) 106306
  * [10] M. Kokubo, T. Hibi, Weakly polymatroidal ideals, Algebra Colloq. 13 (2006) 711–720.
  * [11] A. Kumar, R. Kumar, R. Sarkar, S. Selvaraja, Symbolic Powers of Certain Cover Ideals of Graphs, Acta Mathematica Vietnamica 46 (2021) 599–611
  * [12] J. Herzog, T. Hibi, Monomial Ideals, Graduate Text in Mathematics 260, Springer, 2011.
  * [13] J. Herzog, T. Hibi, N. V. Trung, Symbolic powers of monomial ideals and vertex cover algebras, Adv. Math. 210 (2007) 304–322.
  * [14] J. Herzog, T. Hibi, The face ideal of a simplicial complex, arXiv: 1411.3567
  * [15] T. Hibi, A. Higashitani, K. Kimura, A.B. O’Keefe, Algebraic study on Cameron-Walker graphs, J. Algebra 422 (2015) 257–269.
  * [16] D.T. Hoang, N.C. Minh, T.N. Trung, Cohen-Macaulay graphs with large girth, J. Algebra Appl. 14 (2015) 1550112
  * [17] F. Mohammadi, Powers of the vertex cover ideals, Collect. Math. 65 (2014) 169–181.
  * [18] F. Mohammadi, Powers of the vertex cover ideal of a chordal graph, Comm. Algebra 39 (2011) 1–12.
  * [19] J. Provan, L. Billera, Decompositions of simplicial complexes related to diameters of convex polyhedra, Math. Oper. Res. 5 (1980) 576–594.
  * [20] S. Selvaraja, Symbolic powers of vertex cover ideals. Internat. J. Algebra Comput. 30 (2020) 1167–1183.
  * [21] S. A. Seyed Fakhari, Regularity of symbolic powers of cover ideals of graphs. Collect. Math. 70(2019) 187–195.
  * [22] S. A. Seyed Fakhari, On the minimal free resolution of symbolic powers of cover ideals of graphs, Proc. Amer. Math. Soc. 149 (2021) 3687–3698.
  * [23] N. V. Trung, T. M. Tuan, Equality of ordinary and symbolic powers of Stanley-Reisner ideals, J. Algebra (2011) 77-93.