arXiv:1803.01239v1 [] 3 Mar 2018

Krull dimension and regularity of binomial edge
ideals of block graphs
Carla Mascia, Giancarlo Rinaldo
University of Trento

∗

March 6, 2018

Abstract
We give a lower bound for the Castelnuovo-Mumford regularity of
binomial edge ideals of block graphs by computing the two distinguished
extremal Betti numbers of a new family of block graphs, called flower
graphs. Moreover we present a linear time algorithm to compute the
Krull dimension of binomial edge ideals of block graphs.

Introduction
In 2010, binomial edge ideals were introduced in [3] and appeared independently also in [13]. Let S = K[x1 , . . . , xn , y1 , . . . , yn ] be the polynomial ring in
2n variables with coeﬃcients in a ﬁeld K. Let G be a graph on vertex set [n]
and edges E(G). The ideal JG of S generated by the binomials fij = xi yj − xj yi
such that i < j and {i, j} ∈ E(G), is called the binomial edge ideal of G. Any
ideal generated by a set of 2-minors of a 2 × n-matrix of indeterminates may be
viewed as the binomial edge ideal of a graph.
For a set T ⊂ [n], let G[n]\T be the induced subgraph of G with vertex set
[n] \ T and G1 , . . . , Gc(T ) the connected components of G[n]\T . T is a cutset
of G if c(T \ {i}) < c(T ) for each i ∈ T , and we denote by C(G) the set of all
cutsets for G. In [3] and [13] the authors gave a nice description of the primary
decomposition of JG in terms of prime ideals induced by the set C(G) (see (2)).
Thanks to this result the following formula for the Krull dimension is obtained
dim(S/JG ) = max {n + c(T ) − |T |}.
T ∈C(G)

(1)

The second author in [14] described an algorithm to compute the primary decomposition (2), and hence the Krull dimension. Unfortunately, this algorithm
is exponential in time and space.
A block graph, also known as clique tree, is a graph whose blocks are cliques.
In general, computing the depth of a ring is a diﬃcult task. In [4] the authors
prove that when G is a block graph, depth S/JG = n + c and, equivalently,
proj dim S/JG = n − c where c is the number of connected components of G.
∗ Email

addresses: carla.mascia@unitn.it, giancarlo.rinaldo@unitn.it

1

Given any block graph, such a nice formula for the Krull dimension does not
exist, and we believe that is hard to obtain something that is better than (1).
Nevertheless the block graphs are the easier but not trivial class where we
can obtain a good algorithm to compute the Krull dimension. For example, by
an easy combinatorial argument we have that the cutsets of G are all and only
sets of cutpoints of G. In Proposition 2.5 we present an algorithm that in linear
time and space computes the Krull dimension. The idea is to ﬁnd a minimal
prime ideal of minimal height since it induces the Krull dimension of S/JG . We
have implemented the algorithm using CoCoA (see [2]), in the case G is a tree.
Another fundamental invariant that has been studied in deep is the Castelnuovo-Mumford regularity of binomial edge ideal. Lower and upper bounds
for the regularity are known by Matsuda and Murai [12] and Kiani and Saeedi
Madani [9]. The case of the so called proper interval graphs has been studied by
by Ene and Zarojanu [5]. Furthermore, Kiani and Saeedi Madani characterized
all graphs whose binomial edge ideal have regularity 2 and regularity 3, see [10]
and [11].
It is still an open problem to determine the regularity of the binomial edge
ideal for block graphs in terms of the combinatorics of the graph. Recently, Herzog and the second author [7] computed one of the distinguished extremal Betti
number of the binomial edge ideal of a block graph and classify all block graphs
admitting precisely one extremal Betti number giving a natural lower bound for
the regularity of any block graph. Jananthan et al in an yet unpublished paper
and revised version of [8] obtained a related result for trees, a subclass of block
graphs.
Inspired by these results we deﬁne a new class of graphs, namely the ﬂower
graphs (see Deﬁnition 3.1 and Fig. 1), for which we compute the superextremal
Betti numbers (see Theorem 3.4) and the regularity (see Corollary 3.5). As a
consequence we obtain new lower bounds in Theorem 3.6 and Corollary 3.7 for
the regularity of any block graph.

1

On the height of minimimal prime ideals of JG
and decomposability of block graphs

We start this section recalling the formula to compute the primary decomposition of a binomial edge ideal JG . Let deﬁne
!
[
PT (G) =
{xi , yi }, JG̃1 , . . . , JG̃c(T ) ⊆ S
i∈T

where G̃i , for i = 1, . . . , c(T ), denotes the complete graph on V (Gi ). PT (G) is
a prime ideal of height n − c(T ) + |T |, where |T | denotes the cardinality of T .
It holds
\
PT (G).
(2)
JG =
T ∈C(G)

We denote by M(G) the minimal prime ideals of JG , by Minh(G) ⊆ M(G) the
minimal prime ideals PT (G) of minimum height and by Maxh(G) ⊆ M(G) the
minimal prime ideals PT (G) of maximum height.

2

A subset C of V (G) is called a clique of G if for all i, j ∈ C, with i 6= j,
one has {i, j} ∈ E(G). A maximal clique is a clique that cannot be extended
by including one more adjacent vertex. A vertex v of a graph G is called a free
vertex if it belongs to only one maximal clique of G.
A connected subgraph of G that has no cutpoint and is maximal with respect
to this property is a block. G is called block graph if all its blocks are complete
graphs. One can see that a graph G is a block graph if and only if it is a chordal
graph in which every two maximal cliques have at most one vertex in common.
Let G be a block graph. An endblock is a block having exactly one cutpoint.
Definition 1.1 Let G be a graph and v ∈ V (G). The clique degree of v, denoted
by cdeg(v), is the number of maximal cliques which v belongs to.
Definition 1.2 A graph G is decomposable if exists a decomposition
G = G1 ∪ G2

(3)

with V (G1 ) ∩ V (G2 ) = {v} such that v is a free vertex of G1 and G2 . By a
recursive decomposition (3) applied to each G1 and G2 , after a finite number of
steps we obtain
G = G1 ∪ · · · ∪ Gr
(4)
where G1 , . . . , Gr are indecomposable and for 1 ≤ i < j ≤ r either V (Gi ) ∩
V (Gj ) = ∅ or V (Gi ) ∩ V (Gj ) = {v} and v is a free vertex of Gi and Gj . The
decomposition (4) is unique up to ordering and we say that G is decomposable
into indecomposable graphs G1 , . . . , Gr .
Lemma 1.3 Let G be a graph decomposable into G1 and G2 , with V (G1 ) ∩
V (G2 ) = {v}. Let PT (G) ∈ M(G). If v ∈ T , then height(PT \{v} (G)) =
height(PT (G)).
Proof. Let H1 , . . . , Hc denote the connected components induced by T , and
then height(PT (G)) = n − c + |T |. Suppose v ∈ T , v induces exactly two
connected components, we may suppose H1 and H2 . The connected components
induced by T \ {v} are H1 ∪ H2 ∪ {v}, H3 , . . . , Hc , hence height(PT \{v} (G)) =
n − (c − 1) + (|T | − 1) = height(PT (G)).
Proposition 1.4 Let G be a block graph. The following are equivalent:
(i) G is indecomposable;
(ii) if v ∈ V (G), then cdeg(v) 6= 2;
(iii) Maxh(G) = {P∅ (G)}.
Proof.
(i) ⇔ (ii) It is trivial.
(ii) ⇒ (iii) We can suppose G connected. Since height(P∅ (G)) = n−1, we want
to prove that for any T 6= ∅, height(PT (G)) < n − 1 . Let T ∈ C(G), with
height(PT (G)) ≥ n − 1, that is c(T ) − |T | ≤ 1. If T = {v}, then c(T ) ≤ 2

3

or equivalently cdeg(v) ≤ 2, but v is a cutpoint, then it is not a free vertex,
and then cdeg(v) = 2, which is in contradiction with the hypothesis. Let
T = {v1 , . . . , vr }, with r ≥ 2, such that height(PT (G)) ≥ n − 1 and
suppose it is minimal with respect to this property. In a block graph, also
T1 = T \ {vr } is a cutset. By deﬁnition, c(T1 ) < c(T ) and |T1 | = |T | − 1,
then c(T1 )−|T1 | < 2, then height(PT1 (G)) ≥ n−1, but it is in contradiction
with the hypothesis on the minimality of T .
(iii) ⇒ (ii) Suppose by absurd that exists a vertex v ∈ V (G) such that
cdeg(v) = 2. Let T = {v}, then height(PT (G)) = height(P∅ (G)) = n − 1,
then also PT (G) ∈ Maxh(G), which is in contradiction with the hypothesis.

We observe that for a generic graph G is not true that if G is indecomposable
then cdeg(v) 6= 2 for any v ∈ V (G). It is suﬃcient to consider G = C4 : all its
vertices have clique degree equal to 2, but G is indecomposable. For a generic
graph, also G indecomposable is not equivalent to the fact that P∅ (G) is the
prime ideal of the maximum height in the primary decomposition of JG . In
fact, consider G = C4 with V (G) = {1, . . . , 4} and E(G) = {{i, i + 1}|i =
1, . . . , 3}∪{1, 4}. The subset T = {1, 3} is a cutset for G and height(PT (G)) = 4,
whereas height(P∅ (G)) = 3.

2

Krull dimension of binomial edge ideals of block
graphs

If G is any graph with n vertices, it is well-known that the Krull dimension
of S/JG is given by dim(S/JG ) = maxT ⊆C(G) {n + c(T ) − |T |}, and then, in
general, to compute it one must investigate all the possible cutsets of G. For
some classes of graphs, there exists an immediate way to compute the Krull
dimension. For example, if G is a complete graph or a graph obtained by gluing
free vertices of complete graphs and such that any vertices v ∈ V (G) is or a free
vertex or has cdeg(v) = 2, then dim(S/JG ) = n + 1. For a generic block graph
G, in Proposition 2.5, we show an algorithm to compute the Krull dimension of
S/JG in linear time.
From now on, we consider only connected block graphs, since the Krull dimension of a graph with r connected components, G1 , . . . , Gr , is given by the
sum of the Krull dimension of Si /JGi , with i = 1, . . . , r and Si = K[xj , yj ]j∈V (Gi ) .
Before showing the aforementioned algorithm, we need some auxiliary results.
Lemma 2.1 Let G be a block graph and v ∈ V (G). Let PT (G) ∈ Minh(G). If
v belongs to exactly two endblocks, then PT ∪{v} (G) ∈ Minh(G); if v belongs
to at least three endblocks, then v ∈ T .
Proof. Let PT (G) ∈ Minh(G) and let v belong to r endblocks, B1 , . . . , Br ,
with r ≥ 2, and let G1 , . . . , Gc be the connected components of G[n]\T , then
height(PT (G)) = n − c + |T |. Suppose that v 6∈ T . Without loss of generality,
we can suppose v ∈ G1 . The connected components induced by T ∪ {v} are
B1′ , . . . , Br′ , G′1 , G2 , . . . , Gc , where Bi′ = Bi \ {v} for i = 1, . . . , r and G′1 =
4

G1 \ {B1 , . . . , Br }. If r ≥ 3 or r = 2 and G′1 6= ∅, the number of connected
components induced by T ∪ {v} is at least r + c − 1 and hence it is greater
than or equal to c + 2. Thus, height(PT ∪{v} (G)) ≤ n − (c + 2) + (|T | + 1) <
height(PT (G)), which is in contradiction with the minimality of PT (G). If
r = 2 and G′1 = ∅, then height(PT ∪{v} (G)) = height(PT (G)), and then also
PT ∪{v} (G) ∈ Minh(G).
Lemma 2.2 Let G be a block graph. There exists at least one minimal prime
ideal PT (G) ∈ Minh(G) such that T does not contain any vertices v with
cdeg(v) = 2.
Proof. Let T ∈ C(G) be such that PT (G) ∈ Minh(G). Let {v1 , . . . , vr } ⊆ T be
all the vertices in T with clique degree equal to 2. Let T ′ = T \ {v1 , . . . , vr }, we
prove that height(PT ′ (G)) = height(PT (G)), and then also PT ′ (G) ∈ Minh(G).
We use induction on r. If r = 0, there is nothing to prove. Otherwise, let
T1 = T \ {vr }. By induction hypothesis, we have height(PT ′ ) = height(PT1 ),
and by the Lemma 1.3, we get height(PT1 ) = height(PT ), and then we have
done.
Remark 2.3. By Lemma 2.1 and Lemma 2.2, it follows that there exists at least
one minimal prime ideal PT (G) associated to JG of minimum height such that
T contains all the vertices that belong to at least two endblocks and if v ∈ T ,
then v belongs to at least three blocks.
Remark 2.4. If G is a block graph, and v ∈ V (G) is a vertex with cdeg(v) =
r ≥ 2, then v is a cutpoint and the number of connected components of G[n]\{v}
is exactly r.
In the following we show a linear time algorithm to obtain the Krull dimension of a block graph.
Proposition 2.5 Let G be a block graph. Then the following algorithm computes the Krull dimension of S/JG :
• Input: A block graph G with n vertices
• Output: The Krull dimension d of S/JG
1. d := n + 1;
2. LG := {G};
3. LI := {};
4. for every graph H ∈ LG
4a. decompose H into its indecomposable subgraphs I = {G1 , . . . , Gr };
4b. remove from I the subgraphs which are blocks;
4c. LI := LI ∪ I;
4d. for every graph I ∈ LI
4e. S := {v ∈ I|v belongs to at least 2 endblocks};
4f. for every v ∈ S

5

4g. d := d + cdeg(v) − 2;
4h. remove from I the vertices of the endblocks that
contain v;
4i. if I is not a block, then LG = LG ∪ I;
5. return d.
Proof. The aim of the algorithm is to compute the Krull dimension through the
formula n + c(T ) − |T |, where T ⊆ [n] is a cutset such that PT (G) ∈ Minh(G)
and of the form described in Remark 2.3. The algorithm works in the following
way: ﬁrstly, T = ∅, and then d = n + 1. We denote by LG the list of graphs
that are to consider still. Given a graph H in LG, any vertex of H with clique
degree equal to 2 does not belong to T and then we decompose H into its
indecomposable subgraphs and we collect them on LI, discarding blocks, since
all the vertex of a block are free vertices, and then they don’t belong to T . For
every subgraph I in LI, any vertex v ∈ I which belongs to at least 2 endblocks
and to at least 3 blocks must be in T and hence we update the Krull dimension.
In particular, at this step the contribute of v for the Krull dimension is equal to
the number of the connected components that it induces less the cardinality of
the cutset, which is 1. By Remark 2.4, the number of the connected components
of IV (I)\{v} is equal to cdeg(v), less 1, because one connected component is just
considered starting from d = n + 1. Then, the vertices of the endblocks that
contain v are removed from I and the remaining subgraphs are added to LG.
The algorithm continues on all the subgraphs on LG, until it is empty.
We have implemented the algorithm proposed in the Proposition 2.5 using
CoCoA [2] version 4.7 in order to compute eﬀectively the Krull dimension of
S/JG , whenever G is a tree. We underline that the time complexity is linear
with respect to number of vertices of G, in fact it is suﬃcient an unique visit of
G to compute the Krull dimension of S/JG .

3

Regularity bounds for binomial edge ideals of
block graphs

The main result of this section is the lower bound for the CastelnuovoMumford regularity of binomial edge ideals of block graphs (Theorem 3.6).
To reach our result, we compute the regularity and the superextremal Betti
numbers of special block graphs, called flower graphs, Figure 1.
Let M be a ﬁnitely graded S-module. A Betti number βi,i+j (M ) 6= 0 is
called extremal if βk,k+ℓ = 0 for all pairs (k, ℓ) 6= (i, j), with k ≥ i, ℓ ≥ j. Let
q = reg(M ) and p = projdim(M ), then there exist unique numbers i and j
such that βi,i+q (M ) and βp,p+j (M ) are extremal Betti numbers. We call them
the distinguished extremal Betti numbers of M . Let k be the maximal integer
j such that βi,j 6= 0 for some i. It is clear that βi,k (M ) is an extremal Betti
number for all i with βi,k 6= 0, and that there is at least one such i. These Betti
numbers are distinguished by the fact that they are positioned on the diagonal
{(i, k − 1)|i = 0, . . . , k} in the Betti diagram, and that all Betti numbers on the
right lower side of the diagonal are zero. The Betti numbers βi,k , for i = 0, . . . , k,

6

are called superextremal, regardless of whether they are zero or not. We refer
the reader to [6, Chapter 11] for further details.
Definition 3.1 A flower graph Fh,k (v) is a connected block graph constructed
by joining h copies of the cycle graph C3 and k copies of the bipartite graph
K1,3 with a common vertex v, where v is one of the free vertices of C3 and of
K1,3 .
We observe that any ﬂower graph Fh,k (v) has 2h+3k+1 vertices and 3(h+k)
edges. The clique degree of v is given by h + k, and the number of inner vertices
is i(Fh,k (v)) = k + 1 and all of them are cutpoints for Fh,k (v). When it is
unnecessary to make explicit the parameters h and k, we refer to Fh,k (v) as
F (v).

q q q q
r
r
✡❏
✡❏
✡
✡
❏
❏
✡
✡
❏
❏❏r
r✡
❏rr✡
❅
v
❅
❅r
r
r
r
r

r
q q q q
Figure 1: A ﬂower graph Fh,k (v)
Remark 3.2. Let G be a ﬂower graph F (v). By the result [15, Corollary 1.5],
obtained from G by connecting all the
G = JG′ ∩ Qv where G′ is the graph
T
vertices adjacent to v, and Qv = T ∈C(G),v∈T PT (G). We observe that in this
case Qv = (xv , yv ) + JG′′ , where G′′ is obtained from G by removing v, and then
we can write
JG = JG′ ∩ ((xv , yv ) + JG′′ )
Let G be a graph. We denote by i(G) the number of inner vertices of G
and by f (G) the number of free vertices of G. Before stating the distinguished
extremal Betti numbers of the binomial edge ideal of a ﬂower graph, we need
the following remark.
Remark 3.3. Let G be a disconnected block graph with G1 , . . . , Gr its connected components. If all the Gj have precisely one extremal Betti number,
βnj −1,nj +i(Gj ) (Sj /JGj ), for any j = 1, . . . , r, with Sj = K[xi , yi ]i∈V (Gj ) and
nj = |V (Gj )|, then S/JG has precisely one extremal Betti number and it is
given by
r
Y
βnj −1,nj +i(Gj ) (Sj /JGj ).
βn−r,n+i(G) (S/JG ) =
j=1

Theorem 3.4 Let G be a flower graph F (v), with cdeg(v) ≥ 3. The following
are extremal Betti numbers of S/JG :
(a) βn−1,n+i(G) (S/JG ) = f (G) − 1;
7

(b) βn−cdeg(v)+1,n+i(G) (S/JG ) = 1.
In particular, they are the only non zero superextremal Betti numbers.
Proof. The fact (a) is proved in [7]. As regards (b), we focus on the cutpoint v
of G. Thanks to the decomposition quoted in the Remark 3.2, we consider the
following exact sequence
0 −→ S/JG −→ S/JG′ ⊕ S/((xv , yv ) + JG′′ ) −→ S/((xv , yv ) + JH )

(5)

where G′ is the graph obtained from G by connecting all the vertices adjacent to
v, G′′ is obtained from G by removing v and H is obtained from G′ by removing
v. We observe that G′ and H are block graphs satisfying [7, Theorem 2.4 (b)],
with i(G′ ) = i(H) = i(G) − 1, and then reg(S/JG′ ) = reg(S/((xv , yv ) + JH )) =
i(G). The graph G′′ has cdeg(v) connected components G1 , . . . , Gcdeg(v) : all of
them are K2 or paths P2 of length 2. The latter are decomposable into two K2
and it holds reg(S ′ /JP2 ) = 2 = i(P2 ) + 1, with S ′ = K[xi , yi ]i∈V (P2 ) . Then, by
[7, Theorem 2.4 (b)] and since the ring S/((xv , yv ) + JG′′ ) is the tensor product
of Sj /JGj , with j = 1, . . . , cdeg(v) and Sj = K[xi , yi ]i∈V (Gj ) , we have
reg



S
(xv , yv ) + JG′′



cdeg(v)

=

X
j=1

reg



Sj
JGj



cdeg(v)

=

X

(i(Gj )+1) = i(G)−1+cdeg(v).

j=1

We get the following bound on the regularity of S/JG







S
S
S
, reg
, reg
+ 1}
JG′
(xv , yv ) + JG′′
(xv , yv ) + JH
= max{i(G), i(G) − 1 + cdeg(v), i(G) + 1} = i(G) − 1 + cdeg(v).

reg(S/JG ) ≤ max{reg

By [4, Theorem 1.1], the depth of S/JG for any block graph G over [n] is equal
to n+c, where c is the number of connected components of G. Then, we know the
depth of all quotient rings involved in (5), and by Auslander-Buchsbaum formula
we get proj dim S/JG = proj dim S/JG′ = n − 1, proj dim S/((xv , yv ) + JH ) = n,
and proj dim S/((xv , yv ) + JG′′ ) = n − cdeg(v) + 1.
Let j > i(G), then
Tm,m+j (S/JG′ ) = Tm,m+j (S/((xv , yv ) + JH )) = 0

for any m,

and
for any m > n − cdeg(v) + 1,

Tm,m+j (S/((xv , yv ) + JG′′ )) = 0

S
where Tm,m+j
(M ) stands for TorSm,m+j (M, K) for any S-module M , and S is
omitted if it is clear from the context. Of course, all the above Tm,m+j (−) are
zero when j > i(G) − 1 + cdeg(v).
Therefore, for m = n − cdeg(v) + 1 and j = i(G) − 1 + cdeg(v) we obtain
the following long exact sequence

· · · → Tm+1,m+1+(j−1) (S/((xv , yv ) + JH )) → Tm,m+j (S/JG ) →
Tm,m+j (S/JG′ ) ⊕ Tm,m+j (S/((xv , yv ) + JG′′ )) → Tm,m+j (S/((xv , yv ) + JH )) → · · ·
8

In view of the above, all the functors on the left of Tm,m+j (S/JG ) in the long
exact sequence are zero, and Tm,m+j (S/JG′ ) = Tm,m+j (S/((xv , yv ) + JH )) = 0
too. It follows
Tm,m+j (S/JG ) ∼
= Tm,m+j (S/((xv , yv ) + JG′′ )).
It means that βn−cdeg(v)+1,n+i(G) (S/JG ) = βn−cdeg(v)+1,n+i(G) (S/((xv , yv ) +
JG′′ )). We observe that
S
S
(S /JG′′ ).
Tm,m+j
(S/((xv , yv ) + JG′′ )) ∼
= Tm−2,m−2+j
′

′′

′′

where S = S/(xv , yv ). Since any connected components G1 , . . . , Gcdeg(v) of G′′
is or a K2 or a path of length 2, they have an unique extremal Betti number
βnj −1,nj +i(Gj ) (Sj /JGj ), which is equal to 1, where nj = |V (Gj )|. Therefore, by
Remark 3.3, we have
cdeg(v)
′′

βm−2,m−2+j (S /JG′′ ) =

Y

βnj −1,nj +i(Gj ) (Sj /JGj ) = 1.

j=1

Observe that for m = n − cdeg(v) + 1 and j = i(G) − 1 + cdeg(v) we get that
m + j = n + i(G) is the maximal integer such that βi,m+j (S/JG ) 6= 0 for some i.
We want to prove that βi,n+i(G) 6= 0, only for i = n − cdeg(v) + 1 and i = n − 1.
Let i be an integer such that βi,n+i(G) 6= 0. Since proj dim(S/JG ) = n − 1 and
reg(S/JG ) ≤ i(G)+cdeg−1 then we have to examine n−cdeg(v)+1 ≤ i ≤ n−1.
Consider the following long exact sequence


 
S
S
· · · → Ti+1,n+i(G)
→ Ti,n+i(G)
→
(xv , yv ) + JH
JG






S
S
S
⊕Ti,n+i(G)
→ Ti,n+i(G)
→ ···
Ti,n+i(G)
JG′
(xv , yv ) + JG′′
(xv , yv ) + JH
If n − cdeg(v) + 1 < i < n − 1, since i > proj dim(S/((xv , yv ) + JG′′ )) and
n + i(G) − i > reg(S/JG′ ), reg(S/((xv , yv ) + JH )), it holds
Tori,n+i(G) (M ) = 0, for M ∈ {S/JG′ , S/((xv , yv ) + JG′′ ), S/((xv , yv ) + JH )},
and then we can conclude that also Tori,n+i(G) (S/JG ) = 0.
An immediate consequence of the proof of the Theorem 3.4 is the regularity
of any ﬂower graphs F (v), with cdeg(v) ≥ 3, that depends only on the clique
degree of v and the number of inner vertices. We observe that if cdeg(v) = 2,
then the ﬂower graph is decomposable into G1 ∪G2 , where the Gi ’s, with i = 1, 2,
are K2 or K1,3 , and it is clear by a simple computation that also in this case
reg(S/JF (v) ) = i(F (v)) + cdeg(v) − 1.
Corollary 3.5 Let F (v) be a flower graph, then
reg(S/JF (v) ) = i(F (v)) + cdeg(v) − 1.
If F (v) is an induced subgraph of a block graph G, we denote by cdegF (v)
the clique degree of v in F (v). Note that if F (v) is the maximal ﬂower induced subgraph of G and all the blocks of G containing v are C3 or K1,3 , then
cdegF (v) = cdeg(v), otherwise cdegF (v) < cdeg(v).
9

Theorem 3.6 Let G be an indecomposable block graph and let F (v) be an
induced subgraph of G. Then
reg(S/JG ) ≥ i(G) + cdegF (v) − 1.
Proof. We use induction on the number of blocks of G that are not in F (v). If
G = F (v), the statement follows from Corollary 3.5. Suppose now G contains
properly F (v) as induced subgraph. Since G is connected, there exists an endblock B of G and a subgraph G′ of G such that G = G′ ∪ B, G′ contains F (v)
as induced subgraph, V (G′ ) ∩ V (B) = {w}, and all the blocks containing w are
endblocks, except for one, that one which is in G′ . cdegF (v) does not change
and since G is supposed indecomposable, cdeg(w) ≥ 3. If cdeg(w) = 3, then G′
is decomposable into G1 ∪ G2 , and reg(S/JG′ ) = reg(S/JG1 ) + reg(S/JG2 ). We
may suppose that G1 contains F (v), and then i(G1 ) = i(G) − 1, but cdegF (v)
is still the same. Whereas, G2 is a block and reg(S/JG2 ) = 1. Then by using
induction, we may assume that reg(S/JG1 ) ≥ i(G) + cdeg(v) − 2. Therefore,
reg(S/JG′ ) = reg(S/JG1 ) + reg(S/JG2 ) ≥ i(G) + cdegF (v) − 1.
If cdeg(w) > 3, then i(G′ ) = i(G) and cdegF (v) is still the same. Then, by
using induction on the number of blocks of G, we may assume reg(S/JG′ ) ≥
i(G) + cdegF (v) − 1. By [12, Corollay 2.2] of Matsuda and Murai, one have that
reg(S/JG ) ≥ reg(S/JG′ ).
and then reg(S/JG ) ≥ i(G) + cdegF (v) − 1, as desired.
Putting together the result [7, Theorem 2.4] and the above theorem, we
ﬁnally obtain a bound for the regularity for any binomial edge ideal of block
graphs.
Corollary 3.7 Let G be a block graph.
(i) If G does not contain a flower graph as induced subgraph, then reg(S/JG ) =
i(G) + 1.
(ii) If G contains r flower graphs F1 (v1 ), . . . , Fr (vr ) as induced subgraphs,
then reg(S/JG ) ≥ i(G) + max {cdegFi (vi )} − 1.
i=1,...,r

References
[1] F. Chaudhry, A. Dokuyucu, R. Irfan, On the binomial edge ideals of block
graphs, An. Şt. Univ. Ovidius Constanta, Vol. 24, 2016, 149-158.
[2] CoCoATeam, CoCoA: a system for doing Computations in Commutative
Algebra, Available at http://cocoa.dima.unige.it
[3] J. Herzog, T. Hibi, F. Hreinsdottir, T. Kahle, J. Rauh, Binomial edge
ideals and conditional independence statements, Adv. in Appl. Math., Vol.
45, 2010, pp. 317–333.
[4] V. Ene, J. Herzog, T. Hibi, Cohen-Macaulay binomial edge ideals, Nagoya
Math. J., Vol. 204, 2011, pp. 57–68.
10

[5] V. Ene, A. Zarojanu. On the regularity of binomial edge ideals, Math.
Nachrichten Vol. 288, 2015, pp. 19–24.
[6] J. Herzog, T. Hibi, Monomial Ideals, Grad. Texts in Math. 260, Springer,
London, 2010.
[7] J. Herzog, G. Rinaldo On the extremal Betti numbers of binomial edge
ideals of block graphs arXiv:1802.06020, 2018, 1–9
[8] A. V. Jayanthan, N. Narayanan, and B. V. Raghavendra Rao, Regularity of
binomial edge ideals of certain block graphs, arXiv:1601.01086, 2017, 1–9.
[9] D. Kiani, S. Saeedi Madani, The Castelnuovo-Mumford regularity of binomial edge ideals, Journal of Combinatorial Theory, Series A, Vol. 139, 2016,
pp. 80–86.
[10] S. Saeedi Madani, D. Kiani, Binomial edge ideals of graphs, Electron. J.
Combin. Vol. 19, 2012, Paper #P44.
[11] S. Saeedi Madani, D. Kiani, Binomial edge ideals of regularity 3,
arXiv:1706.09002, 2017,
[12] K. Matsuda, S. Murai, Regularity bounds for binomial edge ideals, Journal
of Commutative Algebra. Vol. 5, 2013, pp. 141–149.
[13] M. Ohtani, Graphs and ideals generated by some 2-minors, Comm. Algebra,
Vol. 39, 2011, pp. 905–917.
[14] G. Rinaldo, Cohen-Macaulay binomial edge ideals of small deviation, Bull.
Math. Soc. Sci. Math. Roumanie, Tome 56(104) No. 4, 2013, 497–503.
[15] G. Rinaldo, Cohen-Macaulay binomial edge ideals of cactus graphs,
arXiv:1704.07106 , 2017, 1–17.

11

