REGULARITY OF BICYCLIC GRAPHS AND THEIR POWERS

arXiv:1802.07202v1 [] 20 Feb 2018

YAIRON CID-RUIZ, SEPEHR JAFARI, NAVID NEMATI, AND BEATRICE PICONE
Abstract. Let I(G) be the edge ideal of a bicyclic graph. In this paper,
we characterize the Castelnuovo-Mumford regularity of I(G) in terms of the
induced matching number of G. For the base case of this family of graphs,
i.e. dumbbell graph, we explicitly compute the induced matching number.
Moreover, we prove that reg I(G)q = 2q + reg I(G) − 2, for all q ≥ 1, when G
is a dumbbell graph with a connecting path having no more than two vertices.

Introduction
Let I be a homogeneous ideal of the polynomial ring R = K[x1 , . . . , xr ]. The
Castelnuovo-Mumford regularity of I, denoted by reg (I), has been an interesting
and active research topic for the past decades. There exists a vast literature on
the study of the reg (I). One of the most important results on the behavior of the
regularity of powers of ideals was given in 1999 by Cutkosky, Herzog, and Trung
(see [10]). In 2000, Kodiyalam used a different method to prove the same result
(see [23]). In the both papers, it is proved that for all q ≥ q0 , the regularity of
powers of I is a linear function like reg (I q ) = dq + b where q0 is the so called
stabilizing index, and b is the so called constant. The value of d in the above
formula is well understood. For example, d is equal to the degree of the generators
of I when I is equigenerated. Their method does not give precise information on
q0 and b.
Since then, many researchers have tried to compute q0 and b for special families
of ideals. The most simple case, yet interesting, is when I is the edge ideal of a
finite simple graph. Let G = (V (G), E(G)) denote a finite simple undirected
graph. Let R be the polynomial ring K[xi | xi ∈ V (G)] where K is any field. The
edge ideal I(G) of G is the ideal
I(G) = (xi xj | {xi , xj } ∈ E(G)).
Several authors have settled the problem of determining the stabilizing index and
the constant for special families of graphs. Banerjee proved that reg I(G)q = 2q,
for all q ≥ 2, when G is a gap-free and cricket-free graph (see [4]). Moghimian,
Fakhari, and Yassemi answered the question for the family of whiskered graphs
(see [25]). Beyarslan, Tài Hà, and Nam Trung settled the problem for the family
of forests and cycles (see [6]). Their results were expanded to the family of unicyclic graphs by Alilooee, Beyarslan, and Selvaraja (see [1]). Moreover, Alilooee
and Banerjee determined the stabilizing index and the constant for the family of
bipartite graphs with regularity equal to three (see [2]). Jayanthan and Selvaraja
settled the problem for the family of very well-covered graphs (see [19]). Recently,
Erey proved that if G is a gap-free and diamond-free graph, then reg I(G)q = 2q
2010 Mathematics Subject Classification. 13D02, 05C25, 05C38, 05E40.
Key words and phrases. bicyclic graphs, edge ideals, regularity, induced matching number, Lozin
transformation, even-connection.
The first named author was funded by the European Union’s Horizon 2020 research and innovation programme under the Marie Sklodowska-Curie grant agreement No. 675789.
1

2

YAIRON CID-RUIZ, SEPEHR JAFARI, NAVID NEMATI, AND BEATRICE PICONE

for all q ≥ 2 (see [13]). The approach is focused on the relations between the combinatorics of graphs and algebraic properties of edge ideals. We refer the reader
to see [22], [16], [8], [17], [3], [27] and [26] for more information on this topic. The
purpose of this paper is to extend the results of [1] to the family of bicyclic graphs
(i.e. a graph with exactly two cycles).
The base case of the family of bicyclic graphs is that of dumbbell graphs. A
dumbbell graph Cn ·Pl ·Cm is a graph consisting of two cycles Cn and Cm connected
with a path Pl , where n, m, and l are the number of vertices (see Example 2.1).
For the convenience of the notation, we define the following function
(
1
if n ≡ 0, 1 (mod 3),
ξ3 (n) =
0
if n ≡ 2 (mod 3).
Here, we describe the organization sections and main results of this paper.
In Section 1, we fix some notations and recall known results which are crucial
to our treatment.
In Section 2, we use combinatorial techniques to compute the induced matching
number of a dumbbell graph. Then, applying inductive methods, we study regularity of the edge ideals of dumbbell graphs. For a dumbbell graph Cn · Pl · Cm ,
we will always assume that n mod 3 ≤ m mod 3. The cases n ≡ 2 (mod 3),
m ≡ 0, 1 (mod 3) will have the same results as the cases n ≡ 0, 1 (mod 3),
m ≡ 2 (mod 3). Our treatment is based on the Lozin transformation (see [24]
and [7]), and the induced matching number of a dumbbell graph. The following
results are given in this section:
Theorem A (Theorem 2.4). Let n, m ≥ 3 and l ≥ 1, then
j n k j m k j l − ξ (n) − ξ (m) + 1 k
3
3
+
+
.
ν(Cn · Pl · Cm ) =
3
3
3
Theorem B (Theorem 2.6). Let m, n ≥ 3 and l ≥ 1,
(i) if l ≡ 0, 1 (mod 3), then
(
ν(Cn · Pl · Cm ) + 2
if n, m ≡ 2 (mod 3),
reg I(Cn · Pl · Cm ) =
ν(Cn · Pl · Cm ) + 1
otherwise;
(ii) if l ≡ 2 (mod 3), then
(
ν(Cn · Pl · Cm ) + 2
reg I(Cn · Pl · Cm ) =
ν(Cn · Pl · Cm ) + 1

if n ≡ 0, 1 (mod 3), m ≡ 2 (mod 3)
otherwise.

In Section 3, for an arbitrary bicyclic graph G, we give a combinatorial characterization of reg I(G) in terms of the induced matching number ν(G).
Theorem C (Theorem 3.2). Let G be a bicyclic graph with dumbbell Cn · Pl · Cm .
The following statements hold.
(I) Let n, m ≡ 0, 1 (mod 3), then reg I(G) = ν(G) + 1.
(II) Let n ≡ 0, 1 (mod 3) and m ≡ 2 (mod 3), then
ν(G) + 1 ≤ reg I(G) ≤ ν(G) + 2,
and reg I(G) = ν(G) + 2 if and only if ν(G) = ν(G \ ΓG (Cm )).
(III) Let n, m ≡ 2 (mod 3) and l ≥ 3, then ν(G) + 1 ≤ reg I(G) ≤ ν(G) + 3.
Moreover:
(i) reg I(G) = ν(G) + 3 if and only if ν (G \ ΓG (Cn ∪ Cm )) = ν(G).

REGULARITY OF BICYCLIC GRAPHS AND THEIR POWERS

3

(ii) reg I(G) = ν(G) + 1 if and only if the following conditions hold:
(a) ν(G) − ν(G \ ΓG (Cn ∪ Cm )) > 1;
(b) ν(G) > ν(G \ ΓG (Cn ));
(c) ν(G) > ν(G \ ΓG (Cm )).
(IV) Let n, m ≡ 2 (mod 3) and l ≤ 2, then ν(G) + 1 ≤ reg I(G) ≤ ν(G) + 2. If x
is an vertex on Pl and Lx (G) be the Lozin transformation of G with respect
to x, then reg I(G) = ν(G) + 1 if and only if the following conditions are
satisfied:
(a) ν(Lx (G)) − ν(Lx (G) \ ΓLx (G) (Cn ∪ Cm )) > 1;
(b) ν(Lx (G)) > ν(Lx (G) \ ΓLx (G) (Cn ));
(c) ν(Lx (G)) > ν(Lx (G) \ ΓLx (G) (Cm )).
In Section 4, we investigate the asymptotic behavior of regularity of powers
of I(Cn · Pl · Cm ) when l ≤ 2. The approach takes advantage of the notion of
even-connectedness and the relations between the induced matching number of
graphs and the regularity of the edge ideal.
Theorem D (Theorem 4.11). Let Cn · Pl · Cm with l ≤ 2, then
reg I(Cn · Pl · Cm )q = 2q + reg I(Cn · Pl · Cm ) − 2
for any q ≥ 1.
For the case l ≥ 3, there are immediate examples for which the above theorem
does not hold (see Remark 4.13).
1. Preliminaries
Let R = K[x1 , . . . , xr ] be the standard graded polynomial ring over a field K
and let m be its maximal homogeneous ideal. For a graded Rmodule M , one
can define The Castelnuovo-Mumford regularity in different terms. We recall the
definition of the regularity of an R-module M by the minimal free resolution M .
The minimal graded free resolution of M is an exact sequence of the form
0 → Fp → Fp−1 → · · · → F0 → M → 0,
L
where each Fi is a graded free R-module of the form Fi =
R(−j)βi,j (M ) , each
j∈N

ϕi : Fi → Fi−1 , with F−1 := M , is a graded homomorphism of degree zero
such that ϕi+1 (Fi+1 ) ⊆ mFi for all i ≥ 0. The numbers βi,j (M ) are important
invariants,
P known as the graded Betti numbers of M . In particular, the number
βi =
βi,j (M ) is called the i-th Betti number of M and βi,j (M ) is the i-th Betti
j∈N

number of M of degree j. Note that the minimal free resolution of M is unique
up to isomorphism, hence the graded Betti numbers are uniquely determined.
Definition 1.1. Let M be a finitely generated graded R-module. The regularity
of M is given by
reg (M ) = max{j − i | βi,j (M ) 6= 0}.
Note that, if I is an ideal of R, then reg (R/I) = reg (I) − 1.
Let G = (V, E) be a graph with vertex set V = {v1 , . . . , vl }. Here, we recall
some classes of graphs that we need for this study.
Definition 1.2. Let G = (V, E) be a graph.

4

YAIRON CID-RUIZ, SEPEHR JAFARI, NAVID NEMATI, AND BEATRICE PICONE

(i) G is called a path with l vertices, denoted by Pl , if V = {v1 , . . . , vl } and
{vi , vi+1 } ∈ E for all 1 ≤ i ≤ l − 1.
(ii) G is called a cycle with n vertices, denoted by Cn , if V = {v1 , . . . , vn } and
{vi , vi+1 } ∈ E for all 1 ≤ i ≤ n − 1 and {vn , v1 } ∈ E.
(iii) G is called a dumbbell graph if G contains two cycles Cn and Cm joined by
a path Pl of l vertices. We denote it by Cn · Pl · Cm . (See Example 2.1)
For a vertex u in a graph G = (V, E), let NG (u) = {v ∈ V |{u, v} ∈ E} be the
set of neighbors of u, and set NG [u] := NG (u) ∪ {u}. An edge e is incident to
a vertex u if u ∈ e. The degree of a vertex u ∈ V , denoted by degG (u), is the
number of edges incident to u. When there is no confusion, we will omit G and
write N (u), N [u] and deg(u). For an edge e in a graph G = (V, E), we define
G \ e to be the subgraph of G obtained by deleting e from E (but the vertices
are remained). For a subset W ⊆ V of the vertices in G, we define G \ W to
be the subgraph of G deleting the vertices of W and their incident edges. When
W = {u} consists of a single vertex, we write G \ u instead of G \ {u}. For an
edge e = {u, v} ∈ E, let NG [e] = NG [u] ∪ NG [v] and define Ge to be the induced
subgraph of G over the vertex set V \ NG [e].
By abuse of notation, we think of the vertices of G = (V, E) as the variables of
R = K[x1 , . . . , xr ]. Following this notation, we consider the edges of G as square
free monomials of degree two. When there is no confusion, we use e to denote
edge and xe for the monomial correspond to e. If we need to specify the vertices
of an edge, we use ei,j = xi xj .
Definition 1.3. The edge ideal of the graph G = (V, E) is the square free monomial ideal
I(G) = (xi xj | ei,j ∈ E).
Theorem 1.4. [15, Lemma 3.1, Theorems 3.4 and 3.5] Let G = (V, E) be a graph.
(i) If H is an induced subgraph of G, then reg I(H) ≤ reg I(G);
(ii) Let x ∈ V , then
reg I(G) ≤ max{reg I(G \ x), reg I(G \ N [x]) + 1};
(iii) Let e ∈ E, then
reg I(G) ≤ max{2, reg I(G \ e), reg I(Ge ) + 1}.
Definition 1.5. Let G = (V, E) be a graph with edge ideal I = I(G). Two
vertices xi and xj in G are called even-connected with respect to an s-fold product
M = e1 · · · es , where e1 , . . . , es are edges in G, if there is a path p0 , . . . , p2l+1 , for
some l ≥ 1, in G such that the following conditions hold:
(i) p0 = u and p2l+1 = v;
(ii) for all 0 ≤ j ≤ l − 1, {p2j+1 , p2j+2 } = ei for some i;
(iii) for all i, {j | {p2j+1 , p2j+2 } = ei } ≤ {t | et = ei } .
Definition 1.6. The edges e1 = v1,1 v1,2 , . . . , eq = vq,1 vq,2 are in an even-connected
position, if for all 1 ≤ i ≤ q − 1, the vertex xi,2 is connected to the vertex xi+1,1
and there exist u ∈ N (e1 ) and v ∈ N (eq ) such that u and v are even-connected
with respect to xe1 · · · xeq .
For the edge ideal I = I(G) of some G = (V, E) and an integer s ≥ 1, the
following holds.

REGULARITY OF BICYCLIC GRAPHS AND THEIR POWERS

5

Theorem 1.7. [4, Theorems 6.1 and 6.5] Let M = xe1 · · · xes 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} ∈ E or u and v are even-connected with respect to M .
Remark 1.8. By the above theorem it is easy to see that (I s+1 : M ) corresponds
to an edge ideal I(G0 ). If u and v are different and they are even-connected with
respect to M , then E(G0 ) = E(G) ∪ {u, v}. If u = v, we have u2 ∈ (I s+1 : M ). In
this case by polarization, G0 is produced by adding a whisker to u in G.
The key to our treatment of the dumbbell graphs is to calculate equal upper
bound and lower bound for the regularity of the edge ideal. The following theorems
are useful in our proofs.
Theorem 1.9. [4, Theorem 5.2] Let G be a graph and {m1 , . . . , mr } be the set of
minimal monomial generators of I(G)q for all q ≥ 1, then
reg I(G)q+1 ≤ max{reg (I(G)q : ml ) + 2q, 1 ≤ l ≤ r, reg I(G)q }.
Here by, we recal a result by Kalai and Meshulam on the regularity of monomial
ideals.
Theorem 1.10. [20] Let I1 , . . . , Is be monomial ideals in R, then
!
s
s
.X
X
reg R
Ii ≤
reg (R/Ii ).
i=1

i=1

Let G = (V, E) be a graph and W ⊆ V . The induced subgraph of G on W ,
denoted by G[W ], is the graph with vertex set W and edge set {e ∈ E | e ⊆ W }.
Definition 1.11. Let G = (V, E) be a graph.
A collection C of edges of G is called a matching if the edges in C are pairwise
disjoint. The maximum size of a matching in G is called its matching number,
which is denoted by match(G).
A collection C of edges of G is called an induced matching
 S  if C is a matching,
and C consists of all edges of the induced subgraph G
e of G. The maximum
e∈C

size of an induced matching in G is called its induced matching number and it is
denoted by ν(G).
Remark 1.12. ([6, Remark 2.12]) Let Pl be a path of l vertices, then we have
l+1
c
3
Remark 1.13. ([6, Remark 2.13]) Let Cn be a cycle of n vertices, then we have
n
ν(Cn ) = b c.
3
A maximal induced matching of Cn is completely determined by just choosing a
first edge, and then we go (for instance) in clockwise direction by taking the third
consecutive edge after the last one chosen. Thus, we shall use r = n mod 3 to
give a specific characterization of the structure of the maximal induced matching.
Depending on r we can assume the following:
(i) when r = 0, the edges x1 x2 and x1 xn do not belong to a maximal induced
matching of Cn ;
ν(Pl ) = b

6

YAIRON CID-RUIZ, SEPEHR JAFARI, NAVID NEMATI, AND BEATRICE PICONE

(ii) when r = 1, the edges x1 x2 , x1 xn and xn−1 xn do not belong to a maximal
induced matching of Cn ;
(iii) when r = 2, the edges x1 x2 , x2 x3 , x1 xn and xn−1 xn do not belong to a
maximal induced matching of Cn .
In [6] Beyarslan, Tài Hà and Trung provided a formula for the regularity of the
edge ideal of a forest or a cycle in terms of its induced matching number.
Theorem 1.14. [6, Theorem 4.5] Let G be a graph with edge ideal I(G) and let
ν(G) denote its induced matching number. Then, for all q ≥ 1, we have
reg I(G) ≥ 2q + ν(G) − 1
Theorem 1.15. [6, Theorem 4.7] Let G be a forest with edge ideal I = I(G), then
reg (I q ) = 2q + ν(G) − 1.
for all q ≥ 1, where ν(G) denote the induced matching number of G.
Theorem 1.16. [6, Theorem 5.2]. Let Cn be a cycle with n vertices, then
(
ν(Cn ) + 1
if n ≡ 0, 1 (mod 3),
reg I(Cn ) =
ν(Cn ) + 2
if n ≡ 2 (mod 3),
n
where ν(Cn ) = b c denote the induced matching number of Cn . Moreover,
3
reg I(Cn )q = 2q + ν(Cn ) − 1.
and for all q ≥ 2.
2. Regularity and induced matching number of a dumbbell graph
In this section we compute the induced matching number of a dumbbell graph
and the regularity of its edge ideal. Recall that Cn · Pl · Cm is denote the graph
constructed by two cycles Cn and Cm connected by a path Pl , where n, m and l
are the number of the vertices. In this section, we denote the vertices of Cn , Cm
and Pn by {x1 , . . . , xn }, {y1 , . . . , ym } and {z1 , . . . , zl } respectively.
Example 2.1. Two simple cases when l = 2 and l = 1 are the following:
x2

y2
x1 = z 1

y2

x2
x1 = y1 = z 1

y1 = z 2

y3

y3
x3

x3

y4

Figure 1. The graphs C3 · P2 · C3 and C3 · P1 · C4 .
Notation 2.2. By ξ3 we shall denote the function
(
1
if n ≡ 0, 1 (mod 3),
ξ3 (n) =
0
if n ≡ 2 (mod 3).
Let Cn · Pl be the graph given by connecting the path Pl to the cycle Cn . For
instance, the graph C3 · P3 can be illustrated as the following:

REGULARITY OF BICYCLIC GRAPHS AND THEIR POWERS

7

x2
x1 = z 1

z2

z3

x3

Proposition 2.3. Let n ≥ 3 and l ≥ 1, then
j n k j l − ξ (n) + 1 k
3
ν(Cn · Pl ) =
+
.
3
3
Proof. Case 1: From Remark 1.13, in the case n ≡ 2(mod 3) we have that in
clockwise and anticlockwise directions the two consecutive edges to the vertex x1
are not chosen in a maximal induced matching of Cn . Then, we can choose the
edges in Pl without any constraint coming from the maximal induced matching
chosen in Cn , and so we have ν(Cn · Pl ) = b n3 c + b l+1
3 c.
Case 2: Now we only need to take care of the cases ξ3 (n) = 1, i.e., n ≡
0, 1 (mod 3). We shall use a greedy algorithm to compute the maximal induced
matching number (see e.g. [9, Chapter 16]). We claim that the edge z1 z2 (the one
adjacent to the circle) does not belong to a maximal induced matching of Cn · Pl .
If we prove this claim, then from Remark 1.13 we have that choosing a maximal
induced matching in circle Cn and in the path Pl \ z1 are independent, and so the
best we can do is ν(Cn · Pl ) = ν(Cn ) + ν(Pl−1 ) = b n3 c + b (l−1)+1
c.
3
Suppose that M0 is a maximal induced matching of Cn · Pl . If z1 z2 6∈ M0 then
we are done, so we assume that z1 z2 ∈ M0 . When z1 z2 ∈ M0 , then we have that
the vertices NCn [x1 ] = {x1 , x2 , xn } cannot belong to M0 , and so the best that we
can do in the part of Cn is an induced matching for a path Pn−3 of n − 3 vertices.
n
Since n ≡ 0, 1 (mod 3), then we get ν(Pn−3 ) = b n−2
3 c = b 3 c − 1 = ν(Cn ) − 1. We
remove the edge z1 z2 from M0 , then starting from M0 \ {z1 z2 } we can obtain an
induced matching M1 that gains one more edge in the part of the circle Cn . We
have |M1 | ≥ |M0 | and this implies that M1 is also a maximal induced matching.
Finally, M1 can be seen as the maximal induced matching of a graph given by
the disjoint union of Cn and Pl−1 , and so |M1 | = b n3 c + b (l−1)+1
c.

3
Theorem 2.4. Let n, m ≥ 3 and l ≥ 1, then
j n k j m k j l − ξ (n) − ξ (m) + 1 k
3
3
ν(Cn · Pl · Cm ) =
+
+
.
3
3
3
Proof. We use the same argument as in Proposition 2.3. By Remark 1.13 we have
that when either n ≡ 2 (mod 3) or m ≡ 2 (mod 3), then the maximal induced
matching in Cn or in Cm does not affect the way we choose edges in the path Pl .
In the case n ≡ 0, 1 (mod 3) we can choose a maximal induced matching that
does not use the edge connected to the cycle Cn , which is the same as saying
that we are not going to use one extreme vertex of the path Pl . Similarly, when
m ≡ 0, 1 (mod 3) we can drop the other extreme vertex.

The aim of the rest of this section is to explicitly compute the regularity of
I(Cn · Pl · Cm ) in term of the induced matching number. We divide it into three
subsections depending on the value of l mod 3. The base of our computations is
given by the following proposition.

8

YAIRON CID-RUIZ, SEPEHR JAFARI, NAVID NEMATI, AND BEATRICE PICONE

Proposition 2.5. Let n, m ≥ 3 and l ≥ 1, then
reg I(Cn · Pl · Cm ) − ν(Cn · Pl · Cm ) = reg I(Cn · Pl+3 · Cm ) − ν(Cn · Pl+3 · Cm ).
Proof. From the formula obtained in Theorem 2.4 or [24, Lemma 1], we have the
equality
ν(Cn · Pl+3 · Cm ) = ν(Cn · Pl · Cm ) + 1.
We can apply the Lozin transformation (see e.g. [24], [7]) to any of the vertices
in the bridge Pl , then from [7, Theorem 1.1] we have
reg I(Cn · Pl+3 · Cm ) = reg I(Cn · Pl · Cm ) + 1.
Thus, the statement of the proposition follows by subtracting these equalities.



From the previous proposition, it follows that we only need to consider the
cases l = 1, l = 2 and l = 3. We treat each case in a separate subsection. In the
following theorem we compute the regularity of the edge ideal of the dumbbell
Cn · P l · Cm .
Theorem 2.6. Let m, n ≥ 3 and l ≥ 1, then
(i) if l ≡ 0, 1 (mod 3), then
(
ν(Cn · Pl · Cm ) + 2
reg I(Cn · Pl · Cm ) =
ν(Cn · Pl · Cm ) + 1
(ii) l ≡ 2 (mod 3), then
(
ν(Cn · Pl · Cm ) + 2
reg I(Cn · Pl · Cm ) =
ν(Cn · Pl · Cm ) + 1

if n, m ≡ 2 (mod 3),
otherwise;

n ≡ 0, 1 (mod 3), m ≡ 2 (mod 3);
otherwise.

Proof. Follows from Proposition 2.5, and Theorem 2.8, Theorem 2.14, and Theorem 2.16.

2.1. The case l = 1.
Throughout this subsection, we consider the dumbbell graph Cn · P1 · Cm .
Proposition 2.7. Let n, m ≥ 3, then
jn − 2k jm − 2k
o
nj n k j m k
+
+ 1,
+
+2 .
reg I(Cn · P1 · Cm ) ∈
3
3
3
3
Proof. We use [11, Lemma 3.2], that gives an improved version of the exact sequence coming from deleting the vertex z1 . We have
n

 o
reg I(Cn · P1 · Cm ) ∈ reg I (Cn · P1 · Cm ) \ z1 , reg I (Cn · P1 · Cm ) \ N [z1 ] +1 .
Since (Cn · P1 · Cm ) \ z1 = Pn−1 ∪ Pm−1 and (Cn · P1 · Cm ) \ N [z1 ] = Pn−3 ∪ Pm−3 ,
we get the result by applying [6, Theorem 4.7].

Theorem 2.8. Let n, m ≥ 3, then
(
ν(Cn · P1 · Cm ) + 2
reg I(Cn · P1 · Cm ) =
ν(Cn · P1 · Cm ) + 1

if n ≡ 2 (mod 3), m ≡ 2 (mod 3);
otherwise.

Proof. For any case distinct to n ≡ 2 (mod 3), m ≡ 2 (mod 3) we have the
inequality
n
m
n−2
m−2
b c+b c+1≥b
c+b
c + 2.
3
3
3
3

REGULARITY OF BICYCLIC GRAPHS AND THEIR POWERS

9

So from Proposition 2.7 and the general inequality reg I(Cn · P1 · Cm ) ≥ ν(Cn ·
P1 · Cm ) + 1 = b n3 c + b m
3 c + 1 (see [6, Theorem 4.5]), we get
reg I(Cn · P1 · Cm ) = ν(I(Cn · P1 · Cm )) + 1
for all these cases.
Now we only have to take care of the case n ≡ 2 (mod 3), m ≡ 2 (mod 3). We
shall delete the vertex xn which is one the neighbors of x1 , and then we get the
induced subgraph H = (Cn · P1 · Cm ) \ {xn }. Here we have that H is the graph
given by joining Cm and a path of length Pn−1 , that is, H = Cm · Pn−1 . Since
(n−1)+1
n = 3r1 + 2, then using Proposition 2.3 we have that ν(H) = b m
c=
3c+b
3
(n−3)+1
m
b 3 c + b 3 c. Hence, we can even consider the possibility of not taking the
vertices x1 and x2 (the other neighbor of x1 in Cn ) in the maximal induced
matching of H. Using the fact that ν(H) = ν(H \ {x2 }), then from [1, Theorem
1.1] we get that reg I(H) = ν(H) + 2 = b n3 c + b m
3 c + 2. Finally, from [6, Corollary
4.3] we get reg I(Cn · P1 · Cm ) ≥ reg I(H), and using Proposition 2.7, then the
equality reg I(Cn · P1 · Cm ) = ν(Cn · P1 · Cm ) + 2 follows.

2.2. The case l = 2.
Throughout this subsection, we consider the dumbbell graph Cn · P2 · Cm . From
[6, Theorem 4.5] and the already computed value for ν(Cn · P2 · Cm ), we get a
lower bound given by
m
3 − ξ3 (n) − ξ3 (m)
n
c + 1,
reg I(Cn · P2 · Cm ) ≥ ν(Cn · P2 · Cm ) + 1 = b c + b c + b
3
3
3
then we shall use several constructions to find an upper bound.
Remark 2.9. The regularity of I(Cn ) is given in Theorem 1.16. For simplicity
of notation, we use the equivalent formula reg I(Cn ) = b n−2
3 c + 2.
Proposition 2.10. Let n, m ≥ 3, then
(1)
j n k j m k j 3 − ξ (n) − ξ (m) k
jn − 2k jm − 2k
3
3
+
+
≤ reg (R/I(Cn ·P2 ·Cm )) ≤
+
+2.
3
3
3
3
3
Proof. We only have to prove the inequality on the right. In the original graph
Cn · P2 · Cm we shall remove the edge that connects the two cycles Cn and Cm .
The set of vertices of Cn and Cm are given respectively by {x1 , . . . , xn } and
{y1 , . . . , ym } and we assume that the edge e = x1 y1 is the bridge between the two
cycles. Also, we denote by Cn ∪ Cm the resulting graph given as the disjoint union
of the two cycles Cn and Cm . Then we get the following exact sequence
R
R
R
×e
(−2) −−→
→
→ 0,
0 −→
I(Cn ∪ Cm ) : e
I(Cn ∪ Cm )
I(Cn · P2 · Cm )
and using the long exact sequence induced in local cohomology modules (see e.g.
[18, Lemma 3.1]) we get the inequality





o
n
R
R
R
reg
≤ max reg
+ 1, reg
.
I(Cn · P2 · Cm )
I(Cn ∪ Cm ) : e
I(Cn ∪ Cm )
From [18, Lemma 3.2] we have that the regularity of the two disjoint cycles
Cn ∪ Cm is given by






R
R
R
reg
= reg
+ reg
,
I(Cn ∪ Cm )
I(Cn )
I(Cm )

10

YAIRON CID-RUIZ, SEPEHR JAFARI, NAVID NEMATI, AND BEATRICE PICONE

and using Remark 2.9 we get the equality
 j

n − 2k jm − 2k
R
=
reg
+
+ 2.
I(Cn ∪ Cm )
3
3
On the other hand, the ideal I(Cn ∪ Cm ) : e corresponds to the edge ideal of
the graph H = {x2 } ∪ {xn } ∪ Pn−3 ∪ {y2 } ∪ {ym } ∪ Pm−3 , where x2 and xn are
neighboring vertices of x1 , and Pn−3 represents a path of length n − 3 with the
remaining vertices of Cn ; also, a similar argument follows for the cycle Cm . Hence
from [6, Remark 2.12, Theorem 4.7] and again [18, Lemma 3.2] we get


jn − 2k jm − 2k
R
+1=
+
+ 1,
reg
I(Cn ∪ Cm ) : e
3
3
which implies the statement of the proposition.



As a result of the previous proposition, we can prove the following corollary.
Corollary 2.11. If n ≡ 0, 1 (mod 3) and m ≡ 0, 1 (mod 3), then


jnk jmk
R
reg
= ν(Cn · P2 · Cm ) =
+
I(Cn · P2 · Cm )
3
3
m−2
Proof. In (1) we have the equality ν(Cn · P2 · Cm ) = b n−2
3 c + b 3 c + 2 for all
these cases.


Now we have only three more cases left to deal with, i.e., the case n ≡
0 (mod 3), m ≡ 2 (mod 3), the case n ≡ 1 (mod 3), m ≡ 2 (mod 3), and
the case n ≡ 2 (mod 3), m ≡ 2 (mod 3).
Lemma 2.12. If n ≡ 2 (mod 3) and m ≡ 2 (mod 3), then


jnk jmk
R
reg
= ν(Cn · P2 · Cm ) =
+
+ 1.
I(Cn · P2 · Cm )
3
3
Proof. We shall divide the graph into three subgraphs H1 , H2 and H3 . We make
H1 = Cn \ {x1 } and H2 = Cm \ {y1 }. The subgraph H3 is defined by taking
the bridge e = x1 y1 and the neighboring vertices {x2 , xn , y2 , ym }, i.e. the graph
below.
y2

x2
x1

y1

ym
xn

Using this decomposition and [21] we get the inequality
reg R/I(Cn · P2 · Cm ) ≤ reg (R/I(H1 )) + reg (R/I(H2 )) + reg (R/I(H3 )),
then have that H1 and H2 are paths of length n − 1 and m − 1 respectively, and
using [6, Theorem 4.7] we get
jnk jmk
reg R/I(Cn · P2 · Cm ) ≤
+
+ 1.
3
3
Finally, in the present case n ≡ 2 (mod 3) and m ≡ 2 (mod 3) we have the
equality ν(Cn · P2 · Cm ) = b n3 c + b m

3 c + 1.

REGULARITY OF BICYCLIC GRAPHS AND THEIR POWERS

11

Lemma 2.13. If n ≡ 0, 1 (mod 3) and m ≡ 2 (mod 3), then


jnk jmk
R
= ν(Cn · P2 · Cm ) + 1 =
+
+ 1.
reg
I(Cn · P2 · Cm )
3
3
Proof. In this case we will delete the vertex x1 from the cycle Cn . We have that
H = (Cn · P2 · Cm ) \ {x1 } is an induced subgraph of Cn · P2 · Cm which is given as
the union of a path of length n − 1 and a cycle m, i.e. H = Pn−1 ∪ Cm . From [6]
we get that
jnk jmk
reg (R/I(Cn · P2 · Cm )) ≥ reg (R/I(H)) =
+
+ 1.
3
3
Finally, when n ≡ 0, 1 (mod 3) and m ≡ 2 (mod 3) from Proposition 2.10 we have
that
jn − 2k jm − 2k
jnk jmk
+
+ 1 ≤ reg R/I(Cn · P2 · Cm ) ≤
+
+ 2,
3
3
3
3
and so the equality follows.

Theorem 2.14. Let n, m ≥ 3, then
(
ν(Cn · P2 · Cm ) + 2
reg I(Cn · P2 · Cm ) =
ν(Cn · P2 · Cm ) + 1

if n ≡ 0, 1 (mod 3), m ≡ 2 (mod 3);
otherwise.

Proof. It follows by Corollary 2.11, Lemma 2.12 and Lemma 2.13.



2.3. The case l = 3.
Throughout this subsection, we consider the dumbbell graph Cn · P3 · Cm . We will
apply Theorem 1.14 and Theorem 2.4 in our treatment.
Proposition 2.15. Let n, m ≥ 3, then
(i) reg I(Cn · P3 · Cm ) ≤ ν(Cn · P3 · Cm ) + 2,
(ii) reg I(Cn · P3 · Cm ) = ν(Cn · P3 · Cm ) + 1,

if n, m ≡ 2 (mod 3);
otherwise.

Proof. Let E(P3 ) = {e, e0 } be the set of the edges of P3 , where e = z1 z2 and
e0 = z2 z3 are connected to Cn and Cm , respectively. We have the following short
exact sequence by deleting e from Cn · P3 · Cm :
0 −→

R
R
R
×e
(−2) −−→
→
→ 0.
0
0
I(Cn ∪ (e · Cm )) : e
I(Cn ∪ (e · Cm ))
I(Cn · P3 · Cm )

We have that reg (I(Cn ∪ (e0 · Cm )) : e) = reg (I(Pn−3 ∪ Pm−1 )), and from Propo3−ξ3 (m)
sition 2.3 and [1, Lemma 3.2] follows that reg (I(e0 · Cm )) = b m
c + 1.
3 c+b
3
Thus, using Remark 2.9, [18, Lemma 3.2] and [6, Theorem 4.7], we get





o
n
R
R
R
reg
≤ max reg
+ 1, reg
I(Cn · P3 · Cm )
I(Pn−3 ∪ Pm−1 )
I(Cn ∪ (e0 · Cm )
nj n − 2 k j m k
jn − 2k
j m k j 3 − ξ (m) ko
3
≤ max
+
+ 1,
+1+
+
.
3
3
3
3
3
On the other hand, from Theorem 2.4 we have that ν(C
) = b n3 c +
n · P3 · Cm
4−ξ3 (n)−ξ3 (m)
bm
c. Therefore, we can check that reg I(Cn ·PR3 ·Cm ) ≤ ν(Cn ·
3c+b
3


P3 · Cm ) + 1 when n, m ≡ 2 (mod 3), and that reg I(Cn ·PR3 ·Cm ) = ν(Cn · P3 · Cm )
in all the remaining cases.


12

YAIRON CID-RUIZ, SEPEHR JAFARI, NAVID NEMATI, AND BEATRICE PICONE

Theorem 2.16. Let n, m ≥ 3, then
(
ν(Cn · P3 · Cm ) + 2
reg I(Cn · P3 · Cm ) =
ν(Cn · P3 · Cm ) + 1

if n, m ≡ 2 (mod 3),
otherwise.

Proof. Using Proposition 2.15, then we only need to prove that reg I(Cn · P3 · Cm ) ≥
ν(Cn · P3 · Cm ) + 2 in the case n, m ≡ 2 (mod 3). Hence, we assume n, m ≡
2 (mod 3). Let z2 be the middle vertex of Cn · P3 · Cm . By deleting z2 we see that
H = (Cn · P3 · Cm ) \ z2 = Cn ∪ Cm is an induced subgraph of Cn · P3 · Cm . From
[6] and [18, Lemma 3.2], we have that
reg I(H) = reg I(Cn ) + reg I(Cm ) − 1 = ν(Cn ) + ν(Cm ) + 3.
Since ν(Cn · P3 · Cm ) = ν(Cn ) + ν(Cm ) + 1, then using [6, Corollary 4.3] we get
reg I(Cn · P3 · Cm ) ≥ reg I(H) = ν(Cn · P3 · Cm ) + 2.



3. Combinatorial characterization of reg (I(G)) in terms of ν(G)
Let G be a general bicyclic graph, then its decycling number is smaller or equal
than 2, and so from [7, Theorem 4.11], we get
ν(G) + 1 ≤ reg I(G) ≤ ν(G) + 3.
Example 3.1. The following graph G
z3

x3

x2

z2

x1

y2

y3

y5

y4

y1
z1

x4

x5

has regularity reg I(G) = 6 and induced matching number ν(G) = 3.
In this section, we give a combinatorial characterization of the bicyclic graphs
with regularity ν(G) + 1, ν(G) + 2 and ν(G) + 3. For the rest of this paper, we
shall use the term “dumbbell” of the bicyclic graph G, and it will always denote
the unique subgraph of G of the form Cn · Pl · Cm . The theorem below contains
the characterization that we found.
Theorem 3.2. Let G be a bicyclic graph with dumbbell Cn · Pl · Cm . The following
statements hold.
(I) Let n, m ≡ 0, 1 (mod 3), then reg I(G) = ν(G) + 1.
(II) Let n ≡ 0, 1 (mod 3) and m ≡ 2 (mod 3), then
ν(G) + 1 ≤ reg I(G) ≤ ν(G) + 2,
and reg I(G) = ν(G) + 2 if and only if ν(G) = ν(G \ ΓG (Cm )).
(III) Let n, m ≡ 2 (mod 3) and l ≥ 3, then ν(G) + 1 ≤ reg I(G) ≤ ν(G) + 3.
Moreover:
(i) reg I(G) = ν(G) + 3 if and only if ν (G \ ΓG (Cn ∪ Cm )) = ν(G).
(ii) reg I(G) = ν(G) + 1 if and only if the following conditions hold:
(a) ν(G) − ν(G \ ΓG (Cn ∪ Cm )) > 1;
(b) ν(G) > ν(G \ ΓG (Cn ));

REGULARITY OF BICYCLIC GRAPHS AND THEIR POWERS

13

(c) ν(G) > ν(G \ ΓG (Cm )).
(IV) Let n, m ≡ 2 (mod 3) and l ≤ 2, then ν(G) + 1 ≤ reg I(G) ≤ ν(G) + 2. If x
is an edge on Pl and Lx (G) be the Lozin transformation of G with respect
to x, then reg I(G) = ν(G) + 1 if and only if the following conditions are
satisfied:
(a) ν(Lx (G)) − ν(Lx (G) \ ΓLx (G) (Cn ∪ Cm )) > 1;
(b) ν(Lx (G)) > ν(Lx (G) \ ΓLx (G) (Cn ));
(c) ν(Lx (G)) > ν(Lx (G) \ ΓLx (G) (Cm )).
Proof. Statement (I) follows from Proposition 3.4. In Theorem 3.11, (II) is proved.
By Theorem 3.16 and Theorem 3.19, we get (III). Finally, from Corollary 3.20,
we obtain (IV).

The following simple remark will be crucial in our treatment.
Remark 3.3. ([1, Observation 2.1]) Let G be a graph with a leaf y and its unique
neighbor x, say e = {x, y}. If {e1 , . . . , es } is an induced matching in G\N [x], then
{e1 , . . . , es , e} is an induced matching in G. So we have ν(G \ N [x]) + 1 ≤ ν(G).
Proposition 3.4. Let G be a bicyclic graph with dumbbell Cn · Pl · Cm . The
following statements hold.
(i) When n, m ≡ 0, 1 (mod 3), we have reg I(G) = ν(G) + 1.
(ii) When n ≡ 0, 1 (mod 3) and m ≡ 2 (mod 3), we have reg I(G) ≤ ν(G) + 2.
(iii) When l ≤ 2, we have reg I(G) ≤ ν(G) + 2.
Proof. (i) Again, it is enough to prove the upper bound reg I(G) ≤ ν(G) + 1.
Let E 0 be the set of edges E 0 = E(G) \ E(Cn · Pl · Cm ). We shall proceed by
induction on the cardinality |E 0 | of E 0 . If |E 0 | = 0 then the statement follows
from Theorem 2.6, so we assume |E 0 | > 0. There exists a leaf y in G such that
N [y] = {x}. Let G0 = G \ x and G00 = G \ N [x], then by [11] we have
reg I(G) ≤ max{reg I(G0 ), reg I(G00 ) + 1}.
The graph G0 can be either a bicyclic graph with the same dumbbell Cn ·Pl ·Cm , or a
unicyclic graph with a circle Cr (r = n or r = m) of the type r ≡ 0, 1 (mod 3), or a
forest; also, the same statement holds for the graph G00 . Using either the induction
hypothesis, or [1, Theorem 1.1], or [6, Theorem 1.1], then we get reg I(G0 ) =
ν(G0 )+1 and reg I(G00 ) = ν(G00 )+1. Since we have ν(G0 ) ≤ ν(G) and ν(G00 )+1 ≤
ν(G) (by Remark 3.3), then we obtain the required inequality.
(ii) and (iii) follow by the same inductive argument, only changing the fact that
G0 and G00 could be unicyclic graphs with cycle Cr of the type r ≡ 2 (mod 3). 
Remark 3.5. The inductive process of the previous proposition cannot conclude
reg I(G) ≤ ν(G) + 2 in the case l ≥ 3. Here we may encounter two disjoint
subgraphs G1 and G2 with reg I(Gi ) = ν(Gi ) + 2, which implies reg I(G1 ∪ G2 ) =
ν(G1 ∪ G2 ) + 3. This is exactly the case of Example 3.1.
Nevertheless, with this method follows easily an alternative proof of the inequality reg I(G) ≤ ν(G) + 3 for an arbitrary bicyclic graph G.
For the rest of this paper we shall use the following notation.
Notation 3.6. Let G be a graph and H ⊂ G be a subgraph. Then by ΓG (H) we
denote the set
ΓG (H) = {v ∈ G | d(v, H) = 1}.

14

YAIRON CID-RUIZ, SEPEHR JAFARI, NAVID NEMATI, AND BEATRICE PICONE

In the case k > 0, by SG,k (H) we denote the subgraph given by restricting to the
vertex set
V (SG,k (H)) = {v ∈ G | d(v, H) ≥ k},
and by SG,0 we denote the subgraph given by restricting to the vertex set
V (SG,0 (H)) = {v ∈ G | d(v, H) > 0 or deg(v) ≥ 3}.
Here d(v, H) denotes the minimal distance from the vertex v to the subgraph H,
and deg(v) the degree of v (i.e. the number of edges incident to v). We define
d(v, H) = min{d(v, w) | w ∈ H},
and d(v, w) denotes the length (i.e., the number of edges) of a minimal path between v and w.
Example 3.7. Let G be the graph of Example 3.1 and H = C5 ∪C5 be the subgraph
given by the two cycles of length 5. Then we have that ΓG (H) is the set containing
the vertex in the middle of the bridge joining the two circles, that SG,0 (H) is a
graph of the form
z3

z2

y1

x1
z1

and that the graph

z3

z2

represents SG,2 (H).
We have already computed reg I(G) in the case n, m ≡ 0, 1 (mod 3), for the
remaining cases we shall divide this section into subsections.
3.1. Case I.
In this subsection we shall focus on the case where n ≡ 0, 1 (mod 3) and m ≡
2 (mod 3). This case turns out to be almost identical to a unicyclic graph, and
our treatment is influenced by [1, Section 3].
Notation 3.8. Let G be a bicyclic graph with dumbbell Cn · Pl · Cm such that
n ≡ 0, 1 (mod 3) and m ≡ 2 (mod 3). We shall denote by F1 , . . . , Fc the connected
components of SG,0 (Cm ), and in this case we have that each Fi is either a tree or
a unicyclic graph with cycle Cn (and n ≡ 0, 1 (mod 3)). Then, the graph SG,2 (Cm )
can be given as the union of the components H1 , . . . , Hc , where each one is defined
as
Hi = Fi \ {v ∈ G | d(v, Cm ) ≤ 1}.
We remark that each Hi is not necessarily a connected graph, and that it could be
even the empty graph.
Lemma 3.9. Adopt Notation 3.8. If ν(Hi ) = ν(Fi ) for all 1 ≤ i ≤ c, then
ν(G \ ΓG (Cm )) = ν(G).
Proof. Follows identically to [1, Lemma 3.5].



REGULARITY OF BICYCLIC GRAPHS AND THEIR POWERS

15

Proposition 3.10. Adopt Notation 3.8. If ν(G\ΓG (Cm )) < ν(G) then reg I(G) =
ν(G) + 1.
Proof. Once more, we shall only prove that reg I(G) ≤ ν(G) + 1. Using the
contrapositive of Lemma 3.9, then there exists some i with ν(Hi ) < ν(Fi ). Let x
be the vertex in Fi ∩ Cm , let us use the notations G0 = G \ x and G00 = G \ N [x].
Again, we have the inequality
reg I(G) ≤ max{reg I(G0 ), reg I(G00 ) + 1}.
Note that both G0 and G00 can be either unicyclic graphs with cycle Cn (and n ≡
0, 1 (mod 3)), or forests. Hence, from [1] and [6] we get that reg I(G0 ) = ν(G0 ) + 1
and reg I(G00 ) = ν(G00 ) + 1.
In the case of G0 , we have that reg I(G0 ) = ν(G0 ) + 1 ≤ ν(G) + 1. Let H be
the induced subgraph of G obtained by deleting the vertices of Fi ∪ N [x]. Then
we have G00 = H ∪ Hi . Let M1 and M2 be maximal induced matchings in H
and Hi respectively, then ν(G00 ) = |M1 | + |M2 |. By the condition ν(Fi ) > ν(Hi )
then there exists a maximal induced matching M3 in Fi , such that |M3 | > |M2 |.
From the fact that H ∪ Fi is an induced subgraph in G, then we get
ν(G) ≥ ν(H ∪ Fi ) = |M1 | + |M3 | > |M1 | + |M2 | = ν(G00 ).
Hence reg I(G00 ) = ν(G00 ) + 1 ≤ ν(G), and so we get the statement of the proposition.

Theorem 3.11. Let G be a bicyclic graph with dumbbell Cn · Pl · Cm such that
n ≡ 0, 1 (mod 3) and m ≡ 2 (mod 3). Then the following statements hold.
(i) ν(G) + 1 ≤ reg I(G) ≤ ν(G) + 2;
(ii) reg I(G) = ν(G) + 2 if and only if ν(G) = ν(G \ ΓG (Cm )).
Proof. In Proposition 3.4 we proved (i). In order to prove (ii), we only need to
show that ν(G \ ΓG (Cm )) = ν(G) implies reg I(G) ≥ ν(G) + 2, because the inverse
implication follows from Proposition 3.10.
As in Notation 3.8, let G \ ΓG (Cm ) = Cm ∪ (∪ci=1 Hi ) where each Hi is either a
forest or a unicyclic graph with cycle Cn (and n ≡ 0, 1 (mod 3)). Then, from [1]
and [6] we get
reg I(G \ ΓG (Cm )) = reg I(Cm ) + reg I(∪ci=1 Hi ) − 1
= (ν(Cm ) + 2) + (ν(∪ci=1 Hi ) + 1) − 1
= ν(G \ ΓG (Cm )) + 2
= ν(G) + 2.
Finally, since G \ ΓG (Cm ) is an induced subgraph of G then we have reg I(G) ≥
ν(G) + 2.

3.2. Case II.
The object of study of this subsection is the case where n, m ≡ 2 (mod 3), l ≥ 3,
and in particular when reg I(G) = ν(G) + 3. More specifically, we shall give
necessary and sufficient conditions for the equality reg I(G) = ν(G) + 3.
Notation 3.12. Let G be a bicyclic graph with dumbbell Cn · Pl · Cm such that
n, m ≡ 2 (mod 3) and l ≥ 3. As in Notation 3.8, let F1 , . . . , Fc be the components
of the graph SG,0 (Cn ). We order the Fi ’s in such a way that F1 is a unicyclic graph

16

YAIRON CID-RUIZ, SEPEHR JAFARI, NAVID NEMATI, AND BEATRICE PICONE

with cycle Cm , and for all i > 1 we have that Fi is a tree. The graph SG,2 (Cn )
can be decomposed in components (not necessarily connected) H1 , . . . , Hc where
Hi = Fi \ {v ∈ G | d(v, Cn ) ≤ 1}.
Remark 3.13. Due to the assumption l ≥ 3, then we have that Cm is a subgraph
of H1 . During this subsection and the next one we shall fundamentally use this
fact, and it will allow us to inductively “separate” the two cycles Cn and Cm .
Lemma 3.14. Adopt Notation 3.12. If ν(Hi ) = ν(Fi ) for all 1 ≤ i ≤ c and
ν(H1 ) = ν(H1 \ ΓH1 (Cm )), then
ν (G \ ΓG (Cn ∪ Cm )) = ν(G).
Proof. Since G \ ΓG (Cn ∪ Cm ) is an induced subgraph of G, then we have ν(G \
ΓG (Cn ∪ Cm )) ≤ ν(G). To prove the reverse inequality, we can see that


(2)
G \ ΓG (Cn ∪ Cm ) = Cn ∪ ∪ci=2 Hi ∪ H1 \ ΓH1 (Cm ) .
Then we get
ν(G \ ΓG (Cn ∪ Cm )) = ν(Cn ) +
= ν(Cn ) +
= ν(Cn ) +

c
X
i=2
c
X
i=2
c
X

ν(Hi ) + ν(H1 \ ΓH1 (Cm ))
ν(Hi ) + ν(H1 )
ν(Fi )

i=1

≥ ν(G),
and so ν (G \ ΓG (Cn ∪ Cm )) = ν(G).



Proposition 3.15. Adopt Notation 3.12. If ν(G \ ΓG (Cn ∪ Cm )) < ν(G), then
reg I(G) ≤ ν(G) + 2.
Proof. Using the contrapositive of Lemma 3.14, then there exists some i with
ν(Hi ) < ν(Fi ) or we have ν(H1 \ ΓH1 (Cm )) < ν(H1 ). Then we divide the prove
into two cases.
Case 1: In this case we assume that for some 1 ≤ i ≤ c we have ν(Hi ) < ν(Fi ).
This case follows similarly to Proposition 3.10. Let x be the vertex in Fi ∩ Cn ,
let us use the notations G0 = G \ x and G00 = G \ N [x]. Once more, we have the
inequality
reg I(G) ≤ max{reg I(G0 ), reg I(G00 ) + 1}.
Note that both G0 and G00 are unicyclic graphs, and so we have reg I(G0 ) ≤
ν(G0 ) + 2 and reg I(G00 ) ≤ ν(G00 ) + 2 (see [7]). Since we have ν(G0 ) ≤ ν(G) and
ν(G00 )+1 ≤ ν(G) (see the proof of Proposition 3.10), then it follows the inequality
in this case.
Case 2: Now we suppose that ν(H1 \ ΓH1 (Cm )) < ν(H1 ). Let x be the vertex
in F1 ∩ Cn , let us use the notations G0 = G \ x and G00 = G \ N [x]. We use the
inequality
reg I(G) ≤ max{reg I(G0 ), reg I(G00 ) + 1}.
The graphs G0 and G00 are unicyclic. For the graph G0 we have reg I(G0 ) ≤
ν(G0 ) + 2 ≤ ν(G) + 2. The graph G00 can be given as the disjoint union of H1 and
another graph H defined by H = G \ (F1 ∪ N [x]), that is G00 = H ∪ H1 . Since H

REGULARITY OF BICYCLIC GRAPHS AND THEIR POWERS

17

is a forest, then using [1, Theorem 1.1] we obtain that reg I(G00 ) ≤ ν(G00 ) + 1. So
we get the inequality reg I(G00 ) + 1 ≤ ν(G00 ) + 2 ≤ ν(G) + 2.

Now we are ready to completely describe the case where reg I(G) = ν(G) + 3.
Theorem 3.16. Let G be a bicyclic graph with dumbbell Cn · Pl · Cm . Then
reg I(G) = ν(G) + 3 if and only if the following conditions are satisfied:
(i) n ≡ 2 (mod 3);
(ii) m ≡ 2 (mod 3);
(iii) l ≥ 3;
(iv) ν (G \ ΓG (Cn ∪ Cm )) = ν(G).
Proof. In Proposition 3.4 we proved that the conditions (i), (ii) and (iii) are necessary, and from Proposition 3.15 we have that the condition (iv) is also necessary.
Hence, we only need to prove that reg I(G) = ν(G) + 3 under these conditions.
From the decomposition (2), and using [1] and [6], we can compute




reg I(G \ ΓG (Cn ∪ Cm )) = reg I(Cn ) + reg I ∪ci=2 Hi + reg I H1 \ ΓH1 (Cm ) − 2
= (ν(Cn ) + 2) + (ν(∪ci=2 Hi ) + 1) + (ν(H1 \ ΓH1 (Cm )) + 2) − 2
= ν(G \ ΓG (Cn ∪ Cm )) + 3
= ν(G) + 3.
Since G \ ΓG (Cn ∪ Cm ) is an induced subgraph of G then we get
reg I(G) ≥ reg I(G \ ΓG (Cn ∪ Cm )) = ν(G) + 3,
and so from [7] the equality it is obtained.



3.3. Case III.
In this subsection we assume G to be a bicyclic graph with dumbbell Cn · Pl · Cm
such that n, m ≡ 2 (mod 3) and l ≥ 3. Now that we have characterized when
reg I(G) = ν(G) + 3, then we want to distinguish between reg I(G) = ν(G) + 1
and reg I(G) = ν(G) + 2.
Lemma 3.17. Adopt Notation 3.12. If ν(G) − ν (G \ ΓG (Cn ∪ Cm )) = 1 then
reg I(G) = ν(G) + 2.
Proof. From Theorem 3.16 we have that reg (I(G)) ≤ ν(G) + 2. Using the same
method as in Theorem 3.16, we can obtain a lower bound
reg I(G) ≥ reg I(G \ ΓG (Cn ∪ Cm )) = ν(G \ ΓG (Cn ∪ Cm )) + 3 = ν(G) + 2,
and so the equality follows.



Lemma 3.18. Adopt Notation 3.12. If ν(G) = ν(G \ ΓG (Cn )) then
reg I(G) ≥ ν(G) + 2.
Symmetrically, the same argument holds for Cm .
Proof. Making a lower bound similarly to Theorem 3.11, we get reg I(G) ≥
reg I(G \ ΓG (Cn )) ≥ ν(G \ ΓG (Cn )) + 2 = ν(G) + 2.

Taking into account the induced matching numbers ν(G), ν(G \ ΓG (Cn ∪ Cm )),
ν(G \ ΓG (Cn )) and ν(G \ ΓG (Cm )), we can give necessary and sufficient conditions
for the equality reg I(G) = ν(G) + 1.

18

YAIRON CID-RUIZ, SEPEHR JAFARI, NAVID NEMATI, AND BEATRICE PICONE

Theorem 3.19. Let G be a bicyclic graph with dumbbell Cn · Pl · Cm such that
n, m ≡ 2 (mod 3) and l ≥ 3. Then reg I(G) = ν(G) + 1 if and only if the following
conditions are satisfied:
(i) ν(G) − ν(G \ ΓG (Cn ∪ Cm )) > 1;
(ii) ν(G) > ν(G \ ΓG (Cn ));
(iii) ν(G) > ν(G \ ΓG (Cm )).
Proof. From Lemma 3.17 and Lemma 3.18, we have that the conditions (i), (ii)
and (iii) are necessary. Hence, it is enough to prove reg I(G) ≤ ν(G) + 1 under
these conditions.
Again, for any x ∈ G we denote G0 = G \ x and G00 = G \ N [x], and we have
the upper bound
reg I(G) ≤ max{reg I(G0 ), reg I(G00 ) + 1}.
We shall prove that under the conditions (i), (ii) and (iii) there exists a vertex
x ∈ Cn such that reg I(G0 ) ≤ ν(G) + 1 and reg I(G00 ) + 1 ≤ ν(G) + 1. We divide
the proof into three steps.
Step 1. In this step we prove that for any x ∈ Cn we have reg I(G0 ) ≤ ν(G) + 1.
First we note the following two statements:
• If ν(G0 ) < ν(G), then by [7], we have reg I(G0 ) ≤ ν(G0 ) + 2 ≤ ν(G) + 1.
• If ν(G0 ) > ν(G0 \ ΓG0 (Cm )), then from [1], we get reg I(G0 ) ≤ ν(G0 ) + 1 ≤
ν(G) + 1.
Thus, applying [1], we get that
reg I(G0 ) = ν(G) + 2 ⇐⇒ ν(G) = ν(G0 ) and ν(G0 ) = ν(G0 \ ΓG0 (Cm )).
Hence, if we prove that ν(G0 ) = ν(G) implies ν(G0 ) > ν(G0 \ ΓG0 (Cm )) then we
will get the required inequality reg I(G0 ) ≤ ν(G)+1. Let us assume ν(G) = ν(G0 ).
From the hypothesis ν(G) > ν(G \ ΓG (Cm )) and the fact that G0 \ ΓG0 (Cm ) is an
induced subgraph of G \ ΓG (Cm ), then we get
ν(G0 ) = ν(G) > ν(G \ ΓG (Cm )) ≥ ν(G0 \ ΓG0 (Cm )).
Step 2. Using ν(G) > ν(G\ΓG (Cn )) and the same argument of Lemma 3.9, then
there exists some 1 ≤ i ≤ c such that ν(Fi ) > ν(Hi ). Following Notation 3.12, we
have that F1 is a unicyclic graph containing the cycle Cm and that Fi is a tree for
all i > 1. In this step, let us assume i > 1 where Fi is a tree and ν(Fi ) > ν(Hi ).
Let x be the vertex in Fi ∩ Cn and H be the induced subgraph H = G \ (Fi ∪
N [x]). We have that G00 = H ∪ Hi , and we get the inequalities
ν(G00 ) = ν(H) + ν(Hi ) < ν(H) + ν(Fi ) ≤ ν(G)
from the condition ν(Hi ) < ν(Fi ) and the fact that H ∪ Fi is an induced subgraph
of G.
Let K be the induced subgraph defined by K = (G \ ΓG (Cm )) \ (Fi ∪ N [x]).
Since i > 1 then Fi ∩ F1 = ∅, and so we get the following statements:
• G00 \ ΓG00 (Cm ) = K ∪ Hi .
• K ∪ Fi is an induced subgraph of G \ ΓG (Cm ).
• We have the following inequalities
ν(G00 \ ΓG00 (Cm )) = ν(K) + ν(Hi ) < ν(K) + ν(Fi ) ≤ ν(G \ ΓG (Cm )).
We can apply the same argument as in Step 1 and obtain from [1] and [7] the
following equivalence
reg I(G00 ) + 1 = ν(G) + 2 ⇐⇒ ν(G) = ν(G00 ) + 1 and ν(G00 ) = ν(G00 \ ΓG00 (Cm )).

REGULARITY OF BICYCLIC GRAPHS AND THEIR POWERS

19

Again, it is enough to prove that ν(G) = ν(G00 ) + 1 implies ν(G00 ) > ν(G00 \
ΓG00 (Cm )). Assuming ν(G) = ν(G00 ) + 1 then we can get
ν(G00 ) = ν(G) − 1 > ν(G \ ΓG (Cm )) − 1 ≥ ν(G00 \ ΓG00 (Cm )).
Step 3. In this last step we assume that ν(F1 ) > ν(H1 ) and that ν(Fi ) = ν(Hi )
for all i > 1. Let x be the vertex in F1 ∩ Cn , then as in Step 2 we have the
statements:
• ν(G00 ) < ν(G).
• reg I(G00 ) + 1 = ν(G) + 2 ⇐⇒ ν(G) = ν(G00 ) + 1 and ν(G00 ) = ν(G00 \
ΓG00 (Cm )).
Once more, we shall prove that ν(G) = ν(G00 ) + 1 implies ν(G00 ) > ν(G00 \
ΓG00 (Cm )).
We denote by L the induced subgraph of G00 \ ΓG00 (Cm ) given by disconnecting
all the trees Fi with i > 1, that is
L = (G00 \ ΓG00 (Cm )) \ ΓG (Cn ).
From the conditions ν(Fi ) = ν(Hi ) for all i > 1, then we get ν(L) = ν(G00 \
ΓG00 (Cm )) (see the proofs of Lemma 3.9 or Lemma 3.14). We also have that L is
an induced subgraph of G \ ΓG (Cn ∪ Cm ) because we have the equality
L = (G \ ΓG (Cn ∪ Cm )) \ N [x].
Finally, from the hypothesis ν(G) − ν(G \ ΓG (Cn ∪ Cm )) > 1 we can obtain
ν(G00 ) = ν(G) − 1 > ν(G \ ΓG (Cn ∪ Cm )) ≥ ν(L) = ν(G00 \ ΓG00 (Cm )).



3.4. Case IV.
In this very short subsection we deal with the remaining case, we assume G to be
a bicyclic graph with dumbbell Cn · Pl · Cm such that n, m ≡ 2 (mod 3) and l ≤ 2.
When l ≤ 2, the two circles are too close to each other, and it is difficult
to make a direct analysis (with our methods). Fortunately, with the complete
characterization of the case l ≥ 3, then the problem can be solved with the Lozin
transformation. Suppose that x is one vertex on the bridge Pl (at most two), then
we can apply the Lozin transformation of G with respect to x, and this can give
a bicyclic graph Lx (G) with dumbbell of the type Cn · Pk · Cm where k ≥ 4. From
[24, Lemma 1] and [7, Theorem 1.1] we get the equality
(3)

reg (I(Lx (G))) − ν (Lx (G)) = reg (I(G)) − ν (G) ,

therefore we get a characterization in the following corollary.
Corollary 3.20. Let G be a bicyclic graph with dumbbell Cn · Pl · Cm such that
n, m ≡ 2 (mod 3) and l ≤ 2. Let x be a point on the bridge Pl and let Lx (G) be
the Lozin transformation of G with respect to x. Then we have that ν(G) + 1 ≤
reg I(G) ≤ ν(G) + 2, and that reg I(G) = ν(G) + 1 if and only if the following
conditions are satisfied:
(i) ν(Lx (G)) − ν(Lx (G) \ ΓLx (G) (Cn ∪ Cm )) > 1;
(ii) ν(Lx (G)) > ν(Lx (G) \ ΓLx (G) (Cn ));
(iii) ν(Lx (G)) > ν(Lx (G) \ ΓLx (G) (Cm )).
Proof. It follows from Proposition 3.4, (3), and Theorem 3.19.



Remark 3.21. The previous conditions given in terms of the graph Lx (G) can be
read easily from the original graph G. We preferred to give a neat and recursive
notation, than a larger notation in terms of the original graph.

20

YAIRON CID-RUIZ, SEPEHR JAFARI, NAVID NEMATI, AND BEATRICE PICONE

3.5. Examples.
In this last subsection we shall give examples for each one of the statements in
the characterization of Theorem 3.2.
Example 3.22. Statement (I) of Theorem 3.2. Let G be the graph below.
y2

x2
x3

x1

z2

z3

y1

z1

y3

x4

Then we have reg I(G) = 4 and ν(G) = 3.
Example 3.23. Statement (II) of Theorem 3.2. Let G be the graph below.
y2

x2
x1

y3

y1

y4

y8

x3

y5
y7

y6

Then we have reg I(G) = 5 and ν(G) = 3.
On the other hand, let G be the graph below.
y2

x2
x1

y3

y1

y4
y5

y8

x3

y7

z1

y6

Then we have reg I(G) = 5 and ν(G) = 4.
Example 3.24. Statement (III) of Theorem 3.2. In Example 3.1 we saw a graph
G where reg I(G) = 6 and ν(G) = 3.
Let G be the graph below.
z2

x3

y2

x2

x1

y3

y1
z1

x4

x5

y5

y4

REGULARITY OF BICYCLIC GRAPHS AND THEIR POWERS

21

Then we have reg I(G) = 5 and ν(G) = 3.
But if we move the outer edge to the left, then we get a different result. Let G
be the graph below.
z2

x3

y2

x2

y3

y1

x1
z1
x4

y5

x5

y4

Then we have reg I(G) = 5 and ν(G) = 4.
Example 3.25. Statement (IV) of Theorem 3.2. Let G be the graph below.
x3

y2

x2

y3

x1
x4

y5

x5

y4

Then we have reg I(G) = 4 and ν(G) = 2.
By adding an edge, let G be the graph below.
z1

x3

y2

x2

y3

x1
x4

x5

y5

y4

Then we have reg I(G) = 4 and ν(G) = 3.
4. Castelnuovo-Mumford regularity of powers
In this section, we study of the regularity of powers of I(Cn · Pl · Cm ) when
l ≤ 2. Our treatment is to determine equal upper bound and lower bound for
reg I(Cn · Pl · Cm )q for all q ≥ 1. To determine the upper bound, we follow the
argument of Banerjee in [4, Theorem 5.2]. To determine the lower bound, we
proceed by looking at “nice” induced subgraphs of Cn · Pl · Cm .
As a side result, we answer an interesting question on the behavior of the
constants. Let I be an arbitrary ideal generated in degree d and let reg (I q ) =
dq + bq for q ≥ q0 . An interesting question is the study of the sequence {bi }i≥1 .
In [12] Eisenbud and Harris proved that if dim(R/I) = 0, then {bi }i≥1 is a weakly
decreasing sequence of non-negative integers. In [5] Banerjee, Beyarslan and Hà
conjectured that for any edge ideal, {bi }i≥1 is a weakly decreasing sequence (see

22

YAIRON CID-RUIZ, SEPEHR JAFARI, NAVID NEMATI, AND BEATRICE PICONE

[5, Conjecture 7.11]). For the edge ideal of any dumbbell graph with l ≤ 2, we
prove bi = b1 for all i ≥ 1. However, we expect bi ≤ b1 for all i ≥ 1 for any graph.
Hereby, we study the relations between regularity of Cn · Pl · Cm when l ≤ 2
and some of their subgraphs.
Lemma 4.1. Let Cn · P2 · Cm be a dumbbell graph and G0 = Pn−3 ∪ Pm−3 , then
reg I(G0 ) ≤ reg I(Cn · P2 · Cm ) − 1.
Proof. By Theorem 1.10, we have
reg I(G0 ) ≤ reg (R/I(Pn−3 )) + reg (R/I(Pm−3 )) + 1
m−3+1
n−3+1
c+b
c+1
≤b
3
3
= reg I(Cn ) + reg I(Cm ) − 3.
Last equation follows from Theorem 1.16. In fact, if n ≡ 0, 1 (mod 3), then
n+1
n+1
c = reg I(Cn ) − 1 and if n ≡ 2 (mod 3), then b
c = reg I(Cn ) − 1. The
b
3
3
assumption follows from Corollary 2.11, Lemma 2.12 and Lemma 2.13.

Lemma 4.2. Let Cn · P1 · Cm be a dumbbell and G0 = Pn−3 ∪ Pm−3 , then
reg I(G0 ) ≤ reg I(Cn · P1 · Cm ) − 1.
Proof. Note that by Theorem 2.4 and Theorem 2.6, we
(
reg I(Cn ) + reg I(Cm ) − 2
if n or m ≡ 2 (mod 3),
reg I(Cn · P1 · Cm ) =
reg I(Cn ) + reg I(Cm ) − 1
otherwise.
If n, m ≡ 2 (mod 3) or n, m ≡ 0, 1 (mod 3), then Theorem 2.6 yields reg I(Cn · P1 · Cm ) =
reg I(Cn · P2 · Cm ). Hence, by Lemma 4.1, the inequality of the statement follows.
If n ≡ 2 (mod 3) and m ≡ 0, 1 (mod 3), by Theorem 1.10 and Theorem 1.16, we
have:
reg I(G0 ) ≤ reg (R/I(Pn−3 )) + reg (R/I(Pm−3 )) + 1
m−3+1
n−3+1
≤b
c+b
c+1
3
3
= reg I(Cn ) − 2 + reg I(Cm ) − 1
< reg I(Cn ) + reg I(Cm ) − 1
= reg I(Cn · P1 · Cm ).

Remark 4.3. By comparing reg I(Cn · Pl · Cm ) and reg I(Cn ), one can see
reg I(Cn ) ≤ reg I(Cn · Pl · Cm ).
The following lemma holds also for Cm by symmetry.
Lemma 4.4. Let G = Cn · P2 · Cm be a dumbbell graph with at least 6 adjacent
vertices on Cn like {xt1 , . . . , xt6 }. Let G0 = G \ {xt1 , . . . , xt6 }, then
reg I(G0 ) ≤ reg I(G) − 1.

REGULARITY OF BICYCLIC GRAPHS AND THEIR POWERS

23

Proof. Note that the cardinality of V (P2 ) ∩ {xt1 , . . . , xt6 } is either equal to zero
or one. We distinguish these cases.
If |V (P2 ) ∩ {xt1 , . . . , xt6 }| = 1, then G0 = Pn−6 ∪ Cm . By Theorem 1.10, Theorem 1.15, Theorem 1.16 and Theorem 2.6, we have
reg I(G0 ) ≤ reg I(Pn−6 ) + reg I(Cm ) − 1
≤ reg I(Cn ) + reg I(Cm ) − 3
≤ reg I(Cn · P2 · Cm ) − 1.
If |V (P2 ) ∩ {xt1 , . . . , xt6 }| = 0, then G0 is a connected unicyclic graph with exactly
one tree like T . Note that V (T ) ∩ V (Cm ) 6= ∅ and T has n − 5 vertices. One can
see the following relation:

if n ≡ 0 (mod 3),
 ν(Pn−6 ) = ν(Cn ) − 2 = reg I(Cn ) − 3
ν(Pn−6 ) + 1 = ν(Cn ) − 1 = reg I(Cn ) − 2 if n ≡ 1 (mod 3),
ν(T ) =

ν(Pn−6 ) = ν(Cn ) − 1 = reg I(Cn ) − 3
if n ≡ 2 (mod 3).
By Theorem 1.10, Theorem 1.15, Theorem 1.16 and Theorem 2.6, we have
reg I(G0 ) ≤ reg I(T ) + reg I(Cm ) − 1
= ν(T ) + reg I(Cm )
≤ reg I(Cn ) + reg I(Cm ) − 3
≤ reg I(Cn · P2 · Cm ) − 1
where Pn−6 is some path.



The following lemma holds also for Cm by symmetry.
Lemma 4.5. Let G = Cn · P1 · Cm be a dumbbell graph with at least 6 adjacent
vertices on Cn like {xt1 , . . . , xt6 }. Let G0 = G \ {xt1 , . . . , xt6 }, then
reg I(G0 ) ≤ reg I(G) − 1.
Proof. Note that the cardinality of V (P2 ) ∩ {xt1 , . . . , xt6 } is either equal to zero
or one. We distinguish these cases.
If |V (P2 ) ∩ {xt1 , . . . , xt6 }| = 1, then G0 = Pn−6 ∪ Cm . By Theorem 1.15, Theorem 1.16 and Theorem 1.10, we have
reg I(G0 ) ≤ reg I(Pn−6 ) + reg I(Cm ) − 1.
By Theorem 1.15 and Theorem 1.16, we have
n−6+1
n+1
c+1=b
c−1
3
3
= reg I(Cn ) − 2 < reg I(Cn ) − 1.

reg I(Pn−6 ) ≤ b

Moreover, reg I(Cn ) + reg I(Cm ) − 2 ≤ reg I(G). Thus, the required inequality
holds.
If |V (P2 ) ∩ {xt1 , . . . , xt6 }| = 0, then G0 is a connected unicyclic graph with exactly
one tree like T . Note that V (T ) ∩ V (Cm ) 6= ∅ and T has n − 5 vertices. One can
see that ν(T ) = reg I(Cn ) − 3 for all n. By Theorem 1.15 and Theorem 1.16, we

24

YAIRON CID-RUIZ, SEPEHR JAFARI, NAVID NEMATI, AND BEATRICE PICONE

have
reg I(G0 ) ≤ reg I(T ) + reg I(Cm ) − 1
= ν(T ) + reg I(Cm )
= reg I(Cn ) + reg I(Cm ) − 3
≤ reg I(G) − 1.

The following lemma holds also for Cm by symmetry.
Lemma 4.6. Let G = Cn · P2 · Cm . Let G0 = G ∪ {e} where e is a new edge added
to Cn . If G0 does not have any induced K3 subgraph, then
reg I(G0 ) ≤ reg I(G) + 1.
Proof. G0 is the union of a cycle Ck and a dumbbell graph Cl · P2 · Cm such that
k + l = n + 2. By Theorem 1.10, we have
reg I(G0 ) ≤ reg I(Ck ) + reg I(Cl · P2 · Cm ) − 1
≤ reg I(Ck ) + reg I(Cl ) + reg I(Cm ) − 2.
If n = k + l − 2 ≡ 0, 1 (mod 3), then by Theorem 1.16, we have
k+1
l+1
c+b
c+2
3
3
k+l−1
c+3
≤b
3
≤ reg I(Cn ) + 2

reg I(Ck ) + reg I(Cl ) =b

Thus,
reg I(G0 ) ≤ reg I(Cn ) + reg I(Cm )
= reg I(G) + 1.
If n = k + l − 2 ≡ 2 (mod 3), therefore k ≡ 0 (mod 3) and l ≡ 1 (mod 3) or
k, l ≡ 2 (mod 3). If k ≡ 0 (mod 3) and l ≡ 1 (mod 3), we have
k+1
l+1
c+b
c+2
3
3
k+l−1
=b
c+2
3
= reg I(Cn ) + 1.

reg I(Ck ) + reg I(Cl ) =b

Thus,
reg I(G0 ) ≤ reg I(Cn ) + reg I(Cm ) − 1
≤ reg I(G) + 1.
If k, l ≡ 2 (mod 3), we have
k+1
l+1
c+b
c+2
3
3
k+l−1
=b
c+3
3
= reg I(Cn ) + 2.

reg I(Ck ) + reg I(Cl ) =b

REGULARITY OF BICYCLIC GRAPHS AND THEIR POWERS

25

If m ≡ 0, 1 (mod 3), we have
reg I(G0 ) ≤ reg I(Ck ) + reg I(Cl ) + reg I(Cm ) − 2
= reg I(Cn ) + reg I(Cm )
≤ reg I(G) + 1.
And, if m ≡ 2 (mod 3), we have
reg I(G0 ) ≤ reg I(Ck ) + reg I(Cl ) + reg I(Cm ) − 3
= reg I(Cn ) + reg I(Cm )
≤ reg I(G) + 1.

Lemma 4.7. Let G = Cn · P1 · Cm . Let G0 = G ∪ {e} where e is a new edge added
to Cn . If G0 does not have any induced K3 subgraph, then
reg I(G0 ) ≤ reg I(G) + 1.
Proof. G0 is a union of a cycle Ck and a dumbbell graph Cl · P1 · Cm such that
k + l = n + 2. By Theorem 1.10 we have
reg I(G0 ) ≤ reg I(Ck ) + reg I(Cl · P1 · Cm ) − 1
and then, by Theorem 2.4 and Theorem 2.6, we have
(
reg I(Ck ) + reg I(Cl ) + reg I(Cm ) − 3 if n or m ≡ 2 (mod 3),
reg I(G0 ) ≤
reg I(Ck ) + reg I(Cl ) + reg I(Cm ) − 2 otherwise.
We proceed by looking at all cases.
If n = k + l − 2 ≡ 0, 1 (mod 3), therefore k ≡ 0 (mod 3) and l ≡ 2 (mod 3), or
k ≡ 1 (mod 3) and l ≡ 2 (mod 3), or k, l ≡ 1 (mod 3), or k, l ≡ 0 (mod 3). In all
these cases, we have:
l+1
k+l−1
k+1
c+b
c+2≤b
c+3
3
3
3
n+1
n
=b
c + 3 = b c + 3 = reg I(Cn ) + 2.
3
3
Now, if m ≡ 0, 1 (mod 3), we have:
reg I(Ck ) + reg I(Cl ) = b

reg I(G0 ) ≤ reg I(Ck ) + reg I(Cl ) + reg I(Cm ) − 2
≤ reg I(Cn ) + reg I(Cm ) = reg I(G) + 1.
And if m ≡ 2 (mod 3), we have:
reg I(G0 ) ≤ reg I(Ck ) + reg I(Cl ) + reg I(Cm ) − 3
≤ reg I(Cn ) + reg I(Cm ) − 1 = reg I(G) + 1.
If n = k + l − 2 ≡ 2 (mod 3), therefore k ≡ 0 (mod 3) and l ≡ 1 (mod 3) or
k, l ≡ 2 (mod 3). In both cases we have:
l+1
k+l−1
k+1
c+b
c+2≤b
c+3
3
3
3
n+1
n
=b
c + 3 = b c + 1 + 3 = reg I(Cn ) + 2,
3
3

reg I(Ck ) + reg I(Cl ) = b

26

YAIRON CID-RUIZ, SEPEHR JAFARI, NAVID NEMATI, AND BEATRICE PICONE

Thus,
reg I(G0 ) ≤ reg I(Ck ) + reg I(Cl ) + reg I(Cm ) − 3
≤ reg I(Cn ) + reg I(Cm ) − 1 = reg I(G) + 1,

Theorem 4.8. Let G = Cn · Pl · Cm with l ≤ 2, then
reg (I(G)2 : xe ) ≤ reg I(G)
for all edges e ∈ E(G).
Proof. By Theorem 1.7, one can deduce that (I(G)2 : xe ) is the edge ideal of a
graph G0 . Moreover, G = G0 \ A where A = {e1 , . . . , er } ⊆ E(G0 ) . We show
that reg I(G0 ) ≤ reg I(G). By using Theorem 1.4 repeatedly, it is suffices to prove
reg I(G0t ) + 1 ≤ reg I(G) for all 1 ≤ t ≤ r, where G0t = (G0 \ {e1 , . . . , et−1 })et .
Recall that for e ∈ E(G), Ge is the induced subgraph of G over the vertex set
V \ NG [e].
Let xi and xj be even-connected, not necessarily different, with respect to xe .
If xi and xj are different and d(xi , xj ) ≥ 2, then for all 1 ≤ t ≤ r G0t is a graph
obtained by deleting at least 6 verteces from G0 . Since we delete xi and xj , then
G0t becomes a subgraph of G. In the case in which G0t is obtained by deleting 6
adjacent vertices from one cycle of G, by Lemma 4.4 and Lemma 4.5 we get the
result. If we delete vertices from both cycles of G, then G0t becomes an induced
subgraph of Pn−3 ∪ Pm−3 and in this case the result follows from Lemma 4.1 and
Lemma 4.2.
Now suppose that d(xi , xj ) ≤ 1, i.e. xi and xj are neighbors. It is easy to see
that in this case for all 1 ≤ t ≤ r G0t is Cn or Cm . The assertion follows from
Remark 4.3.

Lemma 4.9. Let G be a graph. If two vertices xi and xj are even-connected with
respect to xe1 · · · xeq , with ei = xi,1 xi,2 for 1 ≤ i ≤ q, then
[
NG0 (xi,j ) ⊂ NG0 (xi ) ∪ NG0 (xj ),
1≤i≤q
j=1,2

where I(G0 ) = (I(G)q+1 :

Q

xei ).

1≤i≤q

Proof. Since (I(G)i+1 : xe1 · · · xei ) ⊂ (I(G)q+1 : xe1 · · · xeq ), then every neighbors
of xi,2 is connected to xi . Since (I(G)i+1 : xeq−i+1 · · · xeq ) ⊂ (I(G)q+1 : xe1 · · · xeq ),
then every neighbors of xq−i+1,1 is connected to xj .

Theorem 4.10. Let G = Cn · Pl · Cm with l ≤ 2 and I = I(G) be its edge ideal,
then
reg (I q+1 : xe1 · · · xeq ) ≤ reg I
for any 1 ≤ q and any edges e1 , . . . , eq ∈ E(G).
Proof. We proceed by induction on q. The case q = 1 is proved in Theorem 4.8.
Let 2 ≤ q and ei = vi,1 vi,2 . We have
I(G0 ) = (I(G)q+1 : xe1 · · · xeq ) =

q
X
j=1

(I(G)q : xe1 · · · xˆej · · · xeq )+I(A) :=

q
X
j=1

Ij +I(A),

REGULARITY OF BICYCLIC GRAPHS AND THEIR POWERS

27

where A = {a1 , . . . , ar } consists of edges which are even connected with respect to
xe1 · · · xeq . For simplicity, we denote each (I(G)q : xe1 · · · xˆej · · · xeq ) by Ij . Notice
that if e1 , . . . , eq are not in an even-connected position, then A = ∅. Applying
Theorem 1.4, we have
reg I(G0 ) ≤ max{reg I(G0 \ a1 ), reg I(G0a1 ) + 1}
≤ max{reg I(G0 \ a1 \ a2 ), reg I(G0a1 ) + 1, reg I((G0 \ a1 )a2 ) + 1}
..
.
≤ max{reg I(G0 \ A), reg I(G0a1 ) + 1, . . . , reg I((G0 \ a1 \ · · · \ ar−1 )ar ) + 1}.
P
By definition, we have I(G0 \ A) = qj=1 Ij . Furthermore, for any ideal I, J,
we have the following short exact sequence
R
R R
R
0→
→ ⊕ →
→ 0,
I ∩J
I
J
I +J
Applying long exact sequence, we have
R
R
R
R
≤ max{reg , reg , reg
− 1}.
reg
I +J
I
J
I ∩J
By applying the above short exact sequence to Ij ’s, we have


q


X
reg I(G0 \ A) = reg 
Ij  ≤ max{reg I1 , . . . , reg Iq , reg ∩qj=1 Ij − 1}.
j=1

One can easily see that ∩qj=1 Ij = I(G) or ∩qj=1 Ij = I(H), where H is a graph
obtained from G by adding a chord to one of the cycles of G such that there is no
new induced K3 subgraph. By using induction and by Lemma 4.7 and Lemma 4.6,
we have
reg I(G0 \ A) ≤ reg I(G).
Now, we need to study the regularity of
H1 := G0a1 , . . . , Hr := (G0 \ a1 \ · · · \ ar−1 )ar
If A = ∅, there is nothing to prove. Let A 6= ∅. In other words, we assume that
the edges e1 , . . . , eq are in an even-connected position. Firstly, assume that all
the edges ei ’s are distinct. By Lemma 4.9, all the H1 , . . . Hr are obtained from
G by removing at least 2q + 2 vertices or deleting one of the cycles. We must
distinguish the following cases:
• if all the edges e1 , . . . , eq are in one cycle, then Hi , 1 ≤ i ≤ r, is obtained
from G by deleting 2q + 2 vertices from one of the cycles. Then, the result
follows from Lemma 4.4 and Lemma 4.5;
• if e1 , . . . , eq are from both cycles, then to obtain Hi , 1 ≤ i ≤ r, we should
delete Pl . Therefore, it forms a union of two paths with n − a and m − b
vertices such that 2q + 2 ≤ a + b. Since we delete Pl , we have a, b ≥ 3.
Hence, the result follows from Lemma 4.1 and Lemma 4.2;
• if for some i, Hi is obtained by deleting at least one of the cycles, then
t2he result follows from Remark 4.3.
To complete the proof it is enough to consider the case where ei ’s are not
distinct. If ei ’s are not distinct and they are in an even-connected position, then
they cover at least one of the cycles. In this case to obtain Hi , 1 ≤ i ≤ r, we should
delete at least one cycle from G. Hence, the result follows from Remark 4.3. 

28

YAIRON CID-RUIZ, SEPEHR JAFARI, NAVID NEMATI, AND BEATRICE PICONE

Theorem 4.11. For the dumbbell graph Cn · Pl · Cm with l ≤ 2, we have
reg I(Cn · Pl · Cm )q ≥ 2q + reg I(Cn · Pl · Cm ) − 2,
for any q ≥ 1.
Proof. Using the inequality reg I(Cn · P2 · Cm )q ≥ 2q + ν(Cn · P2 · Cm ) − 1 of
[6, Theorem 4.5], for the cases where reg I(Cn · Pl · Cm ) = ν(Cn · Pl · Cm ) + 1 we
get the expected inequality. We divide the proof in two halves, the cases l = 1
and l = 2.
Case 1. Let l = 1. We only need to focus on the case where n, m ≡ 2 (mod 3).
Let H be the induced subgraph of Cn · P1 · Cm mentioned in the proof of Theorem 2.8, i.e. H = (Cn · P1 · Cm ) \ {xn } = Pn−1 · Cm . Using Theorem 2.4,
Proposition 2.3 and the modularity n, m ≡ 2 (mod 3), we can check that
ν(H) = ν(Cn · P1 · Cm )
and that
ν(H) = ν(H \ ΓH (Cm )).
From Theorem 2.8 and [1, Theorem 1.1] we get
reg I(Cn · P1 · Cm ) = ν(Cn · P1 · Cm ) + 2 = ν(H) + 2 = reg I(H).
Since H is an induced subgraph of Cn · P1 · Cm , then from [1, Theorem 1.2] and
[6, Corollay 4.3] we get the inequality
reg I(Cn · P1 · Cm )q ≥ reg I(H)q = 2q +reg I(H)−2 = 2q +reg I(Cn · P1 · Cm )−2.
Case 2. Let l = 2. We only need to focus on the cases where n ≡ 0, 1 (mod 3)
and m ≡ 2 (mod 3). We take the same induced subgraph H as in Lemma 2.13.
The induced subgraph H = (Cn · P2 · Cm ) \ {x1 } of Cn · P2 · Cm is given as the
union of a path of length n − 1 and the cycle Cm , i.e., H = Pn−1 ∪ Cm .
By Theorem 2.14, for the cases n ≡ 0, 1 (mod 3) and m ≡ 2 (mod 3), we have
m
n
reg I(Cn · P2 · Cm ) = ν(Cn · P2 · Cm ) + 2 = b c + b c + 2,
3
3
and from [1, Theorem 1.1] we have
m
n
reg I(H) = ν(H) + 2 = ν(Pn−1 ) + ν(Cm ) + 2 = b c + b c + 2.
3
3
Hence, we get reg I(Cn · P2 · Cm ) = reg I(H). Finally, using [1, Theorem 1.2] and
[6, Corollary 4.3], we get the inequality
reg I(Cn · P2 · Cm )q ≥ reg I(H)q = 2q +reg I(H)−2 = 2q +reg I(Cn · P2 · Cm )−2.

Theorem 4.12. For the dumbbell graph Cn · Pl · Cm with l ≤ 2, we have
reg I(Cn · Pl · Cm )q = 2q + reg I(Cn · Pl · Cm ) − 2
for all q ≥ 1.
Proof. It follows by Theorem 4.10, Theorem 1.9 and Theorem 4.11.



Remark 4.13. One may ask whether
reg I(Cn · Pl · Cm )q = 2q + reg I(Cn · Pl · Cm ) − 2
always holds for given n, m, l and q. Unfortunately, this is not the case. In fact,
it can be checked that
reg I(C5 · P3 · C5 )2 < 4 + reg I(C5 · P3 · C5 ) − 2.

REGULARITY OF BICYCLIC GRAPHS AND THEIR POWERS

29

Acknowledgments
This project is originated from the summer school “Pragmatic 2017”. The
authors would like to sincerely express their gratitude to the organizers Alfio
Ragusa, Elena Guardo, Francesco Russo, and Giuseppe Zappalà, and to the lecturers Brian Harbourne, Adam Van Tuyl, Enrico Carlini, and Tài Huy Hà. We
are deeply grateful to the last lecturer for introducing this topic to us and for
his mentoring. The computer algebra system Macaulay2 [14], was very helpful to
compute several examples in the preparation of this paper.
References
[1] A. Alilooee, S. Beyarslan, and S. Selvaraja, Regularity of Powers of Unicyclic Graphs, ArXiv
e-prints (February 2017), available at 1702.00916.
[2] Ali Alilooee and Arindam Banerjee, Powers of edge ideals of regularity three bipartite graphs,
J. Commut. Algebra 9 (2017), no. 4, 441–454. MR3713523
[3] N. Altafi, N. Nemati, S. A. Seyed Fakhari, and S. Yassemi, Free resolution of powers of
monomial ideals and Golod rings, Math. Scand. 120 (2017), no. 1, 59–67. MR3624006
[4] Arindam Banerjee, The regularity of powers of edge ideals, J. Algebraic Combin. 41 (2015),
no. 2, 303–321.
[5] Arindam Banerjee, Selvi Beyarslan, and Huy Tai Ha, Regularity of edge ideals and their
powers, arXiv preprint arXiv:1712.00887 (2017).
[6] Selvi Beyarslan, Huy Tài Hà, and Trân Nam Trung, Regularity of powers of forests and
cycles, J. Algebraic Combin. 42 (2015), no. 4, 1077–1095.
[7] T. Biyikoglu and Y. Civan, Bounding Castelnuovo-Mumford regularity of graphs via Lozin’s
transformation, ArXiv e-prints (February 2013), available at 1302.3064.
[8]
, Castelnuovo-Mumford regularity of graphs, ArXiv e-prints (March 2015), available
at 1503.06018.
[9] Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein, Introduction
to algorithms, Second, MIT Press, Cambridge, MA; McGraw-Hill Book Co., Boston, MA,
2001.
[10] S. Dale Cutkosky, Jürgen Herzog, and Ngô Viêt Trung, Asymptotic behaviour of the
Castelnuovo-Mumford regularity, Compositio Math. 118 (1999), no. 3, 243–261. MR1711319
[11] Hailong Dao, Craig Huneke, and Jay Schweig, Bounds on the regularity and projective dimension of ideals associated to graphs, J. Algebraic Combin. 38 (2013), no. 1, 37–55. MR3070118
[12] David Eisenbud and Joe Harris, Powers of ideals and fibers of morphisms, Math. Res. Lett.
17 (2010), no. 2, 267–273. MR2644374
[13] N. Erey, Powers of Edge Ideals with Linear Resolutions, ArXiv e-prints (March 2017), available at 1703.01561.
[14] Daniel R. Grayson and Michael E. Stillman, Macaulay2, a software system for research in
algebraic geometry.
[15] Huy Tài Hà, Regularity of squarefree monomial ideals, Connections between algebra, combinatorics, and geometry, 2014, pp. 251–276. MR3213523
[16] Huy Tài Hà and Adam Van Tuyl, Monomial ideals, edge ideals of hypergraphs, and their
graded Betti numbers, J. Algebraic Combin. 27 (2008), no. 2, 215–245. MR2375493
[17] Takayuki Hibi, Akihiro Higashitani, Kyouko Kimura, and Akiyoshi Tsuchiya, Dominating
induced matchings of finite graphs and regularity of edge ideals, J. Algebraic Combin. 43
(2016), no. 1, 173–198. MR3439306
[18] Le Tuan Hoa and Nguyen Duc Tam, On some invariants of a mixed product of ideals, Arch.
Math. (Basel) 94 (2010), no. 4, 327–337.
[19] A. Jayanthan and S Selvaraja, Asymptotic behavior of Castelnuovo-Mumford regularity of
edge ideals of very well-covered graphs, ArXiv e-prints (August 2017), available at 1708.
06883.
[20] Gil Kalai and Roy Meshulam, Intersections of Leray complexes and regularity of monomial
ideals, J. Combin. Theory Ser. A 113 (2006), no. 7, 1586–1592. MR2259083
[21]
, Intersections of Leray complexes and regularity of monomial ideals, J. Combin.
Theory Ser. A 113 (2006), no. 7, 1586–1592.

30

YAIRON CID-RUIZ, SEPEHR JAFARI, NAVID NEMATI, AND BEATRICE PICONE

[22] Mordechai Katzman, Characteristic-independence of Betti numbers of graph ideals, J. Combin. Theory Ser. A 113 (2006), no. 3, 435–454. MR2209703
[23] Vijay Kodiyalam, Asymptotic behaviour of Castelnuovo-Mumford regularity, Proc. Amer.
Math. Soc. 128 (2000), no. 2, 407–411. MR1621961
[24] V. V. Lozin, On maximum induced matchings in bipartite graphs, Inform. Process. Lett. 81
(2002), no. 1, 7–11. MR1866807
[25] M. Moghimian, S. A. Seyed Fakhari, and S. Yassemi, Regularity of powers of edge ideal of
whiskered cycles, Comm. Algebra 45 (2017), no. 3, 1246–1259. MR3573376
[26] P. Norouzi, S. A. Seyed Fakhari, and S. Yassemi, Regularity of Powers of edge ideal of very
well-covered graphs, ArXiv e-prints (July 2017), available at 1707.04874.
[27] Russ Woodroofe, Matchings, coverings, and Castelnuovo-Mumford regularity, J. Commut.
Algebra 6 (2014), no. 2, 287–304. MR3249840
Department de Matemàtiques i Informàtica, Facultat de Matemàtiques i Informàtica,
Universitat de Barcelona, Gran Via de les Corts Catalanes, 585; 08007 Barcelona,
Spain.
E-mail address: ycid@ub.edu
Dipartimento di Matematica, Universit degli studi di Genova, Via Dodecaneso,
35, 16146 Genova GE, Italy
E-mail address: sepehr@dima.unige.it
Institut de Mathématiques de Jussieu, UPMC, 75005 Paris, France
E-mail address: navid.nemati@imj-prg.fr
Dipartimento di Matematica e Informatica, Viale A. Doria, 6 - 95100 - Catania,
Italy
E-mail address: picone@dmi.unict.it

