arXiv:1605.02956v1 [math.CO] 10 May 2016

PROJECTIVE DIMENSION OF (HYPER)GRAPHS AND THE
CASTELNUOVO-MUMFORD REGULARITY OF BIPARTITE GRAPHS
TÜRKER BIYIKOĞLU AND YUSUF CIVAN
Abstract. We prove that proj-dimpHq ď regpLpHqq holds for any (hyper)graph H,
where LpHq denotes the Levi graph (the incidence bipartite graph) of H. This in particular brings the use of regularity’s upper bounds on the calculation of proj-dimpHq.
When G is just a (simple) graph, we prove that there exists an induced subgraph H of
G such that proj-dimpGq “ regpSpHqq, where LpHq “ SpHq is the subdivision graph of
H. Moreover, we show that known upper bounds on proj-dimpGq involving domination
parameters are in fact upper bounds to regpSpGqq. By way of application, we prove that
proj-dimpDompGqq “ ΓpGq for any graph G, where DompGq is the dominance complex
of G and ΓpGq is the upper domination number of G. As a counterpart of prime graphs
introduced for the regularity calculations of graphs, we call a connected graph G as a
projectively prime graph over a field k if proj-dimk pG ´ xq ă proj-dimk pGq holds for any
vertex x P V pGq. Such a notion allows us to create examples of graphs showing that
most of the known lower and upper bounds on the projective dimension of graphs are
far from being tight.

1. Introduction
Let R “ krV s be a polynomial ring with a finite set V of indeterminates over a
field k. When I is a monomial ideal in R, there are two central invariants associated
to I, the regularity regpIq :“ maxtj ´ i : βi,j pIq ‰ 0u and the projective dimension
proj-dimpIq :“ maxti : βi,j pIq ‰ 0 for some ju, that in a sense, they measure the complexity of computing the graded Betti numbers βi,j pIq of I. In particular, if I is a squarefree
monomial ideal, these invariants are related by a well-known duality result of Terai [24]
stating that proj-dimpIq “ regpR{I _ q, where I _ is the Alexander dual of I.
The main purpose of the current work is to explore the nature of the Terai’s duality
from the combinatorial point of view. Recall that if I is minimally generated by squarefree monomials m1 , . . . , mr , then the family ∆ :“ tK Ď V : Fi Ę K for any i P rrsu, where
Fi :“ txj : xj |mi u is a simplicial complex on V “ tx1 , . . . , xn u such that whose minimal
non-faces exactly correspond to minimal generators of I. Under such an association, the
ideal I is said to be the Stanley-Reisner ideal of the simplicial complex ∆, denoted by
I “ I∆ , and the simplicial complex ∆I :“ ∆ is called the Stanley-Reisner complex of the
ideal I. Furthermore, the pair HpIq :“ pV, tF1 , . . . , Fr uq is a (simple) hypergraph (known
Date: January 12, 2018.
2010 Mathematics Subject Classification. 13F55, 05E40, 05E45, 05C70, 05C75, 05C76.
Key words and phrases. Edge ring, projective dimension, Castelnuovo-Mumford regularity, dominance complex, induced matching number, Helly number, Levi graph, subdivision graph, vertex-edge
and edge-vertex domination numbers.
Both authors are supported by TÜBİTAK (grant no: 111T704), and the first author is also supported
by ESF EUROCORES TÜBİTAK (grant no: 210T173).
1

2

TÜRKER BIYIKOĞLU AND YUSUF CIVAN

also as a clutter ) on the set V , and under such a correspondence, the ideal I is called the
edge ideal of the hypergraph HpIq.
These interrelations can be reversible in the following way. Let H “ pV, Eq be a hypergraph on V . Then the family of subsets of V containing no edges of H forms a
simplicial complex IndpHq on V , the independence complex of H, and the corresponding
Stanley-Reisner ideal IH :“ IIndpHq is exactly the edge ideal of H. Under such settings,
the regularity of a simplicial complex is defined by regp∆q :“ regpR{I∆ q from which we
set regpHq :“ regpIndpHqq for any (hyper)graph H.
In the topological combinatorial side, the classical combinatorial Alexander duality has
already some fruitful consequences. For instance, Csorba [6] proved that the independence
complex IndpSpGqq of the subdivision graph SpGq of any graph G is homotopy equivalent
to the suspension of the Alexander dual IndpGq_ . However, his result becomes a special
case when we consider the result of Nagel and Reiner [21] on the homotopy type of the
suspension of an arbitrary simplicial complex. In detail, they show that if ∆ is a simplical
complex on V with the set of facets F∆ , and Bp∆q is the bipartite graph that can be
obtained by taking the bipartite complement of the Levi graph of ∆ (or the incidence
graph of the set system pV, F∆ q), then the homotopy equivalence IndpBp∆qq » Σp∆q
holds (see Section 3 for details). Even if the regularity of a simplicial complex is not a
homotopy invariant, we show that it behaves well under such a homotopy equivalence,
that is, we prove that the inequality regp∆q ` 1 ď regpBp∆qq holds for any simplicial
complex ∆ (Theorem 3.5). When we combine such a result with the Terai’s duality, we
conclude that proj-dimpHq ď regpLpHqq for any hypergraph H, where LpHq is the Levi
graph of H. In the case where H “ H is just a (simple) graph, such an inequality becomes
proj-dimpHq ď regpSpHqq that corresponds to the Csorba’s special case in the algebraic
language. In particular, we prove that every graph H has an induced subgraph H 1 such
that proj-dimpHq “ regpSpH 1qq.
Such interrelations naturally bring the question of whether the known lower and upper
bounds on the projective dimension of graphs and the regularity of (bipartite) graphs are
comparable? Firstly, we show that the induced matching number of the bipartite graph
Bp∆q is closely related to the Helly number of the simplicial complex ∆ (Corollary 3.10).
On the other hand, we verify that upper bounds on proj-dimpHq involving domination
parameters of H invented by Dao and Schweig in a series of papers [8, 9, 10] are in fact
upper bounds to regpSpHqq. Interestingly, the induced matching and cochordal cover
numbers of SpHq can be expressed in terms of the domination parameters of H that may
be of independent interest. Indeed, we show that the equalities impSpHqq “ |H| ´ γpHq
and cochordpSpHqq “ |H| ´ τ pHq hold for any graph H without any isolated vertex
(Proposition 4.5 and Corollary 4.11), where γpHq is the domination number of H, whereas
τ pHq is the independence domination number of H.
As a counterpart of prime graphs introduced for the regularity calculations of graphs [4],
we call a connected graph G as a projectively prime graph over a field k if proj-dimk pG ´
xq ă proj-dimk pGq holds for any vertex x P V pGq. Moreover, we say that G is a perfect
projectively prime graph if it is projectively prime graph over any field. In particular,
we verify that the join of any two graphs is a perfect projectively prime graph. In one
hand, such a notion turns the projective dimension calculations of graphs into generalized
(weighted) induced matching problems, on the other hand, it allows us to create examples

PROJECTIVE DIMENSION OF GRAPHS AND THE REGULARITY OF BIPARTITE GRAPHS

3

of graphs showing that most of the known lower and upper bounds on the projective
dimension is far from being tight.
2. Preliminaries
2.1. (Hyper)graphs. By a (simple) graph G, we will mean a finite undirected graph
without loops or multiple edges. If G is a graph, V pGq and EpGq (or simply V and E)
denote its vertex and edge sets. If U Ă V , the graph induced on U is written GrUs, and
in particular, we abbreviate GrV zUs to G ´ U, and write G ´ x whenever U “ txu. For a
given subset U Ď V , the (open) neighbourhood of U is defined by NG pUq :“ YuPU NG puq,
where NG puq :“ tv P V : uv P Eu, and similarly, NG rUs :“ NG pUq Y U is the closed
neighbourhood of U. Furthermore, if F “ te1 , . . . , ek u is a subset of edges of G, we write
NG rF s for the set NG rV pF qs, where V pF q is the set of vertices incident to edges in F .
We write G˝ for the graph obtained from G by removing isolated vertices (if any).
Throughout Kn , Cn and Pn will denote the complete, cycle and path graphs on n
vertices respectively.
We say that G is H-free if no induced subgraph of G is isomorphic to H. A graph G is
called chordal if it is Cr -free for any r ą 3. Moreover, a graph is said to be cochordal if
its complement is a chordal graph.
A hypergraph is a (finite) set system H “ pV, Eq, where V is a set, the set of vertices of
H, and E Ď 2V is the set of edges of H. The hypergraphs that we consider do not have
loops, that is, E can not contain singletons as edges. A hypergraph H “ pV, Eq is said to
be simple if A Ę B and B Ę A for any two edges A, B P E. Through our work, we only
deal with simple hypergraphs.
When S Ď V , the induced subhypergraph of H by the set S is defined to be the hypergraph HrSs :“ tA P E : A Ď Su.
Recall that a subset M Ď E is called a matching of H if no two edges in M share a
common vertex. Moreover, a matching M “ tF1 , . . . , Fk u of H is an induced matching if
the edges in M are exactly the edges of the induced subhypergraph of H over the vertices
contained in Yki“1 Fi , and the cardinality of a maximum induced matching is called the
induced matching number of H and denoted by impHq.
Definition 2.1. For a given hypergraph H “ pV, Eq, the bipartite graph LpHq on V Y E
defined by px, F q P EpLpHqq if and only if x P F is called the Levi graph (or the incidence
graph 1) of H.
If we drop the condition of being simple for hypergraphs, any bipartite graph appears
as the Levi graph of some hypergraph, even if such a representation is not unique. Since
we only deal with simple hypergraphs, the resulting bipartite graphs are of special types.
Let B be a bipartite graph with a bipartition V pBq “ X0 YX1 . Then B is called a Sperner
bipartite graph (or shortly an Sp-bipartite graph) on Xi , if Xi contains no pair of vertices
u and v such that NB puq Ď NB pvq. Observe that a bipartite graph B satisfies B – LpHq
for some (simple) hypergraph H if and only if B is a Sp-bipartite graph.
We also note that when H “ H is just a graph, its Levi graph LpHq is known as the
subdivision graph of H, denoted by SpHq, which can be obtained from H by subdividing
1It

seems that this terminology is not standard, both stemming from incidence geometry.

4

TÜRKER BIYIKOĞLU AND YUSUF CIVAN

each edge of H exactly once. The characterization of subdivision graphs is rather simple,
namely that there exists a graph G such that B – SpGq if and only if B is C4 -free and
degB pvq “ 2 for all v P Xi for some i “ 0, 1.
2.2. Domination parameters of graphs. We next recall the definitions of some domination parameters of graphs that will be in use throughout the sequel. We note that the
relationship between projective dimension of graphs and various domination parameters
firstly explored by Dao and Schweig in a series of papers [8, 9, 10]. However, some of their
newly defined notions turn out to be already known in the literature [1, 17, 22].
A subset A Ď V is called a dominating set for G if NG rAs “ V pGq, and the minimum
size γpGq of a dominating set for G is called the domination number of G, while the
maximum size ΓpGq of a minimal dominating set of G is known as the upper domination
number of G. Moreover, the least cardinality ipGq of an independent dominating set for
G is called the independent domination number of G.
When S Ď V , a vertex x P V zS is said to be a private neighbour of a vertex s P S
with respect to S in G if NG pxq X S “ tsu, and the set of private neighbours of s P S is
denoted by PGS psq.
A subset F Ď E is called an edge dominating set of G if each edge of G either belongs
to F or is incident to some edge in F , and the edge domination number γ 1 pGq of G is the
minimum cardinality of an edge dominating set of G. We remark that γ 1 pGq equals to
the minimum size of a maximal matching for any graph G [25].
For given subsets X, Y Ď V , we say that X dominates Y in G if Y Ď NG pXq, and let
γpY, Gq denote the least cardinality of a subset X that dominates Y in G.
τ pGq :“ maxtγpA, G˝ q : A Ď V pG˝ q is an independent setu
is called the independence domination number of G.
Remark 2.2. We note that the independence domination number τ pGq seems to first
appear in the work of Aharoni, Berger and Ziv [1] (see also [2]) in which it is denoted by
γ i pGq.
2.2.1. Vertex-edge and edge-vertex dominations in graphs. Most of the research on graph
parameters involved domination mainly concentrates either sets of vertices dominating
all other vertices or sets of edges dominating all other edges in graphs. On the contrary,
Peters [22] has introduced vertex-edge and edge-vertex dominations in graphs. Since
then there has been little research on such a mixing theory of graph dominations [5, 17].
However, the recent results of Dao and Schweig [8, 9, 10] have validated the usefulness of
such notions in the calculation of projective dimension of (hyper)graphs that we describe
next.
A vertex u P V is said to vertex-wise dominate an edge e “ xy P E, if u P NG res. A
subset S Ď V is called a vertex-wise dominating set, if for any edge e P E, there exists a
vertex s P S that vertex-wise dominates e. Furthermore, a vertex-wise dominating set S
of G is called minimal, if no proper subset of S is vertex-wise dominating for G. When S
is a minimal vertex-wise dominating set for G, every vertex in S has a private neighbour
in E, that is, e is a vertex-wise private neighbour of s P S if s vertex-wise dominates e
while no vertex in Sztsu vertex-wise dominates the edge e in G.

PROJECTIVE DIMENSION OF GRAPHS AND THE REGULARITY OF BIPARTITE GRAPHS

5

p1q ΥpGq :“ maxt|S| : S is a minimal vertex-wise dominating set of Gu is called the
upper vertex-wise domination number of G.
p2q βpGq :“ maxt|S| : S is a minimal independent vertex-wise dominating set of Gu is
called the upper independent vertex-wise domination number of G.
Observe that the inequality βpGq ď ΥpGq holds for any graph G as a result of the
definitions.
An edge e “ xy of G is said to edge-wise dominate a vertex u P V if u P NG res. A
subset F Ď E is called an edge-wise dominating set, if for any vertex u P V pG˝ q, there
exists an edge f P F that edge-wise dominates u. Moreover, a vertex v is said to be an
edge-wise private neighbour of f P F if f edge-wise dominates v while no edge in F ztf u
edge-wise dominates v.
p3q ǫpGq :“ mint|F | : F Ď E is an edge-wise dominating set of Gu is called the edgewise domination number of G.
We remark that the parameter ǫpGq can also be considered as the minimum size of an
edge-wise dominating matching of G (compare to Theorem 73 in [17]).
Remark 2.3. We note that Peters [22] chooses to call vertex-wise and edge-wise dominating sets by ve-dominating and ev-dominating sets respectively, and denotes parameters
ΥpGq and ǫpGq by Γve pGq and γev respectively. However, we prefer to follow the most
recent notations of Dao and Schweig [8] in order to overcome the difficulty of readability
caused by the prefixes ve- and ev-.
2.3. Simplicial complexes. An (abstract) simplicial complex ∆ on a finite set V is a
family of subsets of V such that tvu P ∆ for all v P V , and if F P ∆ and H Ă F , then
H P ∆. The elements of ∆ are called faces of it; the dimension of a face F is dimpF q :“
|F | ´ 1, and the dimension of ∆ is defined to be dimp∆q :“ maxtdimpF q : F P ∆u. The 0
and 1-dimensional faces of ∆ are called vertices and edges while maximal faces are called
facets. In particular, we denote by F∆ , the set of facets of ∆. For a given face A P ∆, the
subcomplex lk∆ pAq :“ tF P ∆ : F X A “ H and F Y A P ∆u is called the link of A in ∆.
When ∆ “ IndpGq for some graph G, the existence of vertices satisfying some extra
properties is useful when dealing with the homotopy type:
Theorem 2.4. [12, 18] If NG puq Ď NG pvq, then there is a homotopy equivalence IndpGq »
IndpG´vq. On the other hand, if NG rus Ď NG rvs, then the homotopy equivalence IndpGq »
IndpG ´ vq _ Σ IndpG ´ NG rvsq holds.
In [4] we introduced prime simplicial complexes that constitute building blocks for the
regularity calculations. In detail, a simplicial complex ∆ on V is said to be a prime
simplicial complex over a field k provided that regk p∆ ´ xq ă regk p∆q for any vertex
x P V . In particular, a graph G is called a prime graph (over k) whenever IndpGq is a
prime simplicial complex.
The notion of the Alexander dual of a simplicial complex plays a prominent role on
the calculation of the projective dimension of ∆ due to the Terai’s duality. However, for
its definition, we need to relax the definition of a simplicial complex first. A generalized
simplicial complex ∆ on a vertex set V is simply a family of subsets of V , closed under
inclusion. In particular, vertp∆q :“ tx P V : txu P ∆u is called the set of actual vertices of
∆. Observe that when ∆ “ IndpGq for some graph G, then v R vertpIndpGq_ q if and only

6

TÜRKER BIYIKOĞLU AND YUSUF CIVAN

if v is incident to any edge e P E, i.e., G – K1,n for some n ě 1, where v is the vertex
with degG pvq “ n.
Definition 2.5. Let ∆ be a (generalized) simplicial complex on V . Then the Alexander
dual of ∆ is defined to the simplicial complex ∆_ :“ tF Ď V : V zF R ∆u.
Observe that the equality p∆_ q_ “ ∆ always holds. Furthermore, we recall that
when ∆ “ IndpGq for some (hyper)graph G, the minimal non-faces of IndpGq_ exactly
correspond to minimal vertex covers of G, where a subset U Ď V is a vertex cover of G if
V zU P IndpGq. For this reason, the edge ideal IG_ :“ IIndpGq_ of G _ :“ HpIndpGq_ q is also
known as the vertex cover ideal of G.
3. Bounding the regularity of simplicial complexes from their Levi
graphs
In this section, we prove that the regularity of any simplicial complex (or any hypergraph) can be bounded from above by the regularity of a bipartite graph. This, in
particular, implies together with the Terai’s duality that the regularity of the Levi graph
LpHq of any hypergraph H provides an upper bound to the projective dimension of H.
For that purpose, we first provide a local version of Nagel and Reiner’s result [21]. Along
the way, we show that the induced matching number of the associated bipartite graph
can be derived from the combinatorics of the underlying simplicial complex.
Definition 3.1. Let ∆ be a simplicial complex on V . We define a bipartite graph BS p∆q
for each S Ď V by V pBS p∆qq :“ S Y F∆ and ps, F q P EpBS p∆qq if and only if s R F for
any s P S and F P F∆ , where F∆ is the set of facets of ∆. In particular, we abbreviate
BV p∆q to Bp∆q.
We note that if we consider ∆ as a hypergraph Hp∆q “ pV, F∆ q, the graph Bp∆q is
just the bipartite complement of the Levi graph of Hp∆q.
The following theorem of Nagel and Reiner [21] (see also Jonsson [13]) is our main
motivation for the definition of Bp∆q:
Theorem 3.2. [21] The homotopy equivalence IndpBp∆qq » Σp∆q holds for any simplicial complex ∆, where Σp∆q is the (unreduced) suspension ∆.
We first provide a local version of Theorem 3.2.
Lemma 3.3. Let ∆ be a simplicial complex. Then IndpBS p∆qq » IndpBp∆rSsqq for any
S ĎV.
Proof. Assume that F∆rSs “ tH1 , . . . , Hk u, and define Fi :“ tF P F∆ : Hi Ď F u for each
i P rks, AS :“ tC P F∆ : H ‰ C X S R F∆rSs u and BS :“ tD P F∆ : D X S “ Hu. Note
that if ps, Hi q P EpBp∆rSsqq for some s P S and i P rks, then ps, F q P EpBS p∆qq for
any F P Fi . Suppose otherwise Hi Y tsu P ∆ that in turn implies that Hi Y tsu P ∆rSs.
However, the latter is impossible due to the fact that Hi is a facet of ∆rSs. It then follows
that
NBS p∆q pF q “ NBS p∆q pF 1 q “ NBS p∆rSsq pHi q
for any F, F 1 P Fi and i P rks. If we fix a facet, say Fi P Fi for each i P rks, the homotopy
equivalence IndpBS p∆qq » IndpBS p∆qq ´ pFi zFi qq holds by Theorem 2.4. In other words,

PROJECTIVE DIMENSION OF GRAPHS AND THE REGULARITY OF BIPARTITE GRAPHS

7

we can remove the facets in Fi one by one until there remains only a single facet without
altering the homotopy type.
On the other hand, if C P AS , then C X S is a non empty face of ∆rSs which is not
maximal. So, it is contained by a facet, say Hi . However, the containment C X S Ď Hi
forces that NBS p∆q pFi q Ď NBS p∆q pCq, where Fi P Fi is the facet that we fixed earlier.
Therefore, the removal of any such vertex from IndpBS p∆qq does not alter the homotopy
type. Similarly, if D P BS , then we have NBS p∆q pFi q Ď NBS p∆q pDq for any i P rks so that
IndpBS p∆qq » IndpBS p∆q ´ BS q.
Finally, if we define CS :“ Yki“1 pFi zFi q Y AS Y BS , we conclude that
IndpBS p∆qq » IndpBS p∆q ´ CS q – IndpBS p∆qrS Y tF1 , . . . , Fk usq.
However, the graph BS p∆qrS Y tF1 , . . . , Fk us is isomorphic to BS p∆rSsq that proves the
claim.

Corollary 3.4. IndpBS p∆qq » Σp∆rSsq for any S Ď V .
Proof. Since Σp∆rSsq » IndpBS p∆rSsqq by Theorem 3.2. Thus, the result follows from
Lemma 3.3.

Theorem 3.5. The inequality regpBp∆qq ě regp∆q ` 1 holds for any simplicial complex
∆.
r n´1 p∆rSsq ‰ 0, we
Proof. Suppose that regp∆q “ n. If S Ď V is a subset such that H
r n pIndpBS p∆qqq ‰ 0 by Corollary 3.4 so that regpBp∆qq ě n ` 1.
then have H


We remark that the gap between regp∆q and regpBp∆qq could be arbitrarily large. For
instance, if we define Fn :“ W pKn q for some n ě 3, where W pKn q is the graph obtained
by attaching a pendant vertex to each vertex of Kn (the whisker of the complete graph),
then regpBpIndpFn qqq ě n, while regpIndpFn qq “ 1 since Fn is cochordal.
The relation between a simplicial complex ∆ and its bipartite graph Bp∆q can be
reversible over the class of Sperner bipartite graphs.
Proposition 3.6. If B is an Sp-bipartite graph on Xi , then the family
∆i pBq :“ tF Ď Xi : F Ď Xi zNB pvq for some v P X1´i u
is a simplicial complex on Xi for i “ 0, 1. In particular, we have regp∆i pBqq`1 ď regpBq.
Proof. The first claim is obvious. For the second, observe that the facets of ∆i pBq are
of the form Xi zNB pvq for v P X1´i ; hence, we have Bp∆i pBqq – B so that the stated
inequality follows from Theorem 3.5.

Our next goal is to determine the induced matching number of Bp∆q from the combinatorics of the simplicial complex ∆ that peculiarly involves the Helly number of ∆.
Definition 3.7. Let ∆ be a simplicial complex on V , and let m ě 3 be an integer. An
m-flower of ∆ is a set tpx1 , F1 q, . . . , pxm , Fm qu of pairs pxi , Fi q P V ˆ F∆ such that the set
tx1 , . . . , xm u is a face of ∆, and xi R Fj if and only if i “ j. We say that ∆ is flower-free,
if it has no k-flower for any k ě 3. We then define
#
0,
if ∆ is flower-free,
(3.8)
νp∆q :“
maxtk P N : ∆ has a k ´ floweru, otherwise,

8

TÜRKER BIYIKOĞLU AND YUSUF CIVAN

as the flower number of ∆.
Corollary 3.9. impBp∆qq ě maxt2, νp∆qu for any simplicial complex ∆ other than a
simplex.
Proof. Observe first that since ∆ is not a simplex, it has at least two facets F1 , F2 together
with x P F1 zF2 and y P F2 zF1 . However, we then have Bp∆qrx, y, F1, F2 s – 2K2 , which
forces impBp∆qq ě 2.
On the other hand, it is clear that any m-flower tpx1 , F1 q, . . . , pxm , Fm qu of ∆ gives rise
to an induced matching of Bp∆q.

Recall that a subset K Ď V is said to be a minimal non-face of ∆, if K is itself not
a face of ∆ while any proper subset of it is. The maximum size of minimal non-faces of
∆ is known as the Helly number of ∆, denoted by hp∆q [23]. This is consistent with the
classical definition of the Helly number for set systems [11]. Indeed, if F is a finite set
system, then its Helly number can be defined by hpF q :“ hpN pF qq, where N pF q is the
nerve complex of F . Observe that the inequality hp∆q ď regp∆q ` 1 ď regpBp∆qq holds2,
since if K is a minimal non-face in ∆ of size hp∆q, then ∆rKs – S hp∆q´2 , where S m is the
m-dimensional sphere.
Corollary 3.10. impBp∆qq “ maxt2, νp∆q, hp∆qu for any simplicial complex ∆ other
than a simplex.
Proof. Suppose that impBp∆qq “ m, and let tpx1 , F1 q, . . . , pxm , Fm qu is a maximum induced matching of size m ě 3. If K :“ tx1 , . . . , xm u P ∆, then tpx1 , F1 q, . . . , pxm , Fm qu
is an m-flower so that νp∆q ě m. On the other hand, if K R ∆, then K is a minimal
non-face of ∆ that implies hp∆q ě m.

One of the major open problem concerning our results in this section is the decision of
whether any possible gap between regp∆q and regpBp∆qq is caused because of a combinatorial or an algebraic property of the underlying simplicial complex ∆. In other words,
we wonder whether there exists a combinatorially defined positive integer ηp∆q such that
the equality regpBp∆qq “ regp∆q ` ηp∆q holds for any simplicial complex ∆ (over any
field k). In the particular case of prime simplicial complexes, we predict that ηp∆q “ 1.
Problem 3.11. Does the equality regk p∆q`1 “ regk pBp∆qq hold for any prime simplicial
complex ∆ over k?
3.1. Projective dimension and regularity of hypergraphs. Once we have Theorem 3.5 for arbitrary simplicial complexes, we may naturally interpret it for the projective dimension and the regularity of hypergraphs. For that purpose, if we set BpHq :“
BpIndpHqq, then Theorem 3.5 directly implies the following.
Corollary 3.12. regpHq ` 1 ď regpBpHqq for any hypergraph H.
We note that if B is an Sp-bipartite graph on Xi , then the hypergraph Hi pBq on Xi
with edges NB pvq for v P X1´i satisfies that LpHi pBqq – B for i “ 0, 1. This in particular
implies that regpHi pBqq ` 1 ď regpBq as a result of Corollary 3.12.
2The

first part of this inequality also appears in [16] for finite set systems.

PROJECTIVE DIMENSION OF GRAPHS AND THE REGULARITY OF BIPARTITE GRAPHS

9

We next show that the induced matching numbers of a hypergraph H and that of BpHq
are in fact comparable. We recall first that if tF1 , . . . , Fk u is an induced matching of H,
ř
then the inequality ki“1 p|Fi | ´ 1q ď regpHq holds [19].
ř
Proposition 3.13. If tF1 , . . . , Fk u is an induced matching of H, then ki“1 p|Fi | ´ 1q ď
impBpHqq.
Proof. We let Fi “ txi1 , . . . , xiki u for each i P rks, and define
Lij :“

k
ď

pFt ztxt1 uq Y pFi ztxij uq

t“1
t‰i

for any i P rks and 2 ď j ď ki . Since tF1 , . . . , Fk u is an induced matching, each set Lij is
an independent set in H. So, for each such set, there exists a maximal independent set
Sji in H such that Lij Ď Sji and xij R Sji . Now, the set tpxij , Sji q : 1 ď i ď k and 2 ď j ď ki u
ř
of edges forms an induced matching in BpHq of size ki“1 p|Fi | ´ 1q.


Remark 3.14. We note that the equality is possible in Proposition 3.13. For example,
if we consider the graph 2K2 , we have Bp2K2 q – C8 so that impBp2K2 qq “ imp2K2 q “ 2.
When we employ the Terai’s duality, Theorem 3.5 takes the following form:
Corollary 3.15. proj-dimpHq ď regpLpHqq for any hypergraph H.

_
q “ regpIndpHq_ q ` 1, where the first equality is
Proof. Since proj-dimpHq “ regpIH
the Terai’s duality, the claim follows from Theorem 3.5 together with the fact that
BpIndpHq_ q – LpHq, since any facet of IndpHq_ is of the form V zF , where F P E.


We remark that the Helly number hpIndpHq_ q of the Alexander dual of IndpHq exactly
equals to |V | ´ ipHq, where ipHq is the least cardinality of a maximal independent set of
H, since any facet F of IndpHq corresponds to a minimal non-face V zF of IndpHq_ . This
in particular implies that hpIndpHq_ q ď proj-dimpHq.
Our next target is to provide an upper bound on the regularity of the Levi graph LpHq
in terms of the upper independent vertex-wise domination number. However, we first
recall the following result of Há and Woodroofe:
Theorem 3.16. [14] For any simplicial complex ∆, we have regp∆q to be at most the
maximum size of a minimal face A with the property that lk∆ pAq is a simplex.
Let ∆ be a simplicial complex on V . We call a face A P ∆, an S-face of ∆ if lk∆ pAq is
a simplex. Furthermore, an S-face A is said to be minimal if no proper subset of A is an
S-face of ∆.
Proposition 3.17. An independent set L Ď V is a minimal S-face of IndpGq if and only
if L is a minimal vertex-wise dominating set for G.
Proof. Suppose first that L is a minimal S-face of IndpGq, while it is not vertex-wise
dominating for G. This means that there exists an edge e “ xy of G such that e is
not vertex-wise dominated by L. However, this forces that NG res X L “ H, that is,
txu, tyu P lkIndpGq pLq while tx, yu R lkIndpGq pLq, a contradiction.

10

TÜRKER BIYIKOĞLU AND YUSUF CIVAN

Assume now that L is a minimal vertex-wise dominating set of G. If L is not an S-face
of IndpGq, that is, lkIndpGq pLq is not a simplex, then there exist two vertices tuu, tvu P
lkIndpGq pLq with tu, vu R lkIndpGq pLq. Note that this can only be possible when f “ uv P E.
However, since L is vertex-wise dominating for G, we must have NG rf sXL ‰ H so that one
of the vertices x and y can not be contained by the link of L in IndpGq, a contradiction. 
Corollary 3.18. For any graph G with E ‰ H, we have
βpGq “ maxt|L| : L is a minimal S-face of IndpGqu.
We are now ready to provide an upper bound on the regularity of any graph in terms
of a domination parameter of the underlying graph that may be of independent interest.
Theorem 3.19. regpGq ď βpGq for any graph G with E ‰ H.
Proof. This immediately follows from Theorem 3.16 and Corollary 3.18.



We remark that, in general, the invariants βpGq and cochordpGq are incomparable,
where cochordpGq is the cochordal cover number of G, i.e., the least number of cochordal
subgraphs H1 , . . . , Hk of G satisfying EpGq “ YEpHi q. For example, cochordpP4 q “ 1
and βpP4 q “ 2, while βpC7 q “ 2 and cochordpC7 q “ 3. Furthermore, it is not difficult to
construct examples of graphs showing that the gap between regpGq and βpGq could be
arbitrarily large.
Corollary 3.20. proj-dimpHq ď βpLpHqq for any hypergraph H with E ‰ H.
Proof. Since proj-dimpHq ď regpLpHqq for any hypergraph H by Corollary 3.15, the claim
follows from Theorem 3.19.

3.2. An application: Projective dimension of the dominance complex of graphs.
In this subsection, we compute the projective dimension of the dominance complex of any
graph G, or equally that of the closed neighbourhood hypergraph of G as an application
of Corollary 3.20.
We first recall that for a given graph G “ pV, Eq, its dominance complex DompGq is
the simplicial complex on V whose faces are those subsets A Ď V such that the set V zA
is a dominating set for G [18]. Observe that there exists a one-to-one correspondence
between facets of DompGq and minimal dominating sets of G. In order to compute the
projective dimension of DompGq, we first view DompGq as an independence complex of a
hypergraph associated to G.
The closed neighbourhood hypergraph N rGs of a graph G is defined to be the hypergraph
on V whose edges are the minimal elements of the poset tNG rxs : x P V u ordered with
respect to the inclusion.
Lemma 3.21. DompGq – IndpN rGsq for any graph G.
Proof. Since any face of DompGq is clearly an independent set of N rGs, to prove the
claim, it suffices to verify that when X Ď V is an independent set of N rGs, the set V zX
is dominating for G. So, suppose that x P X. It then follows from the definition that
there exists x1 P NG rxs such that NG rx1 s P EpN rGsq. However, since X is an independent
set, we must have NG rx1 s Ę X so that there exists v P NG rx1 s such that v R X. Now,
since NG rx1 s Ď NG rxs, we conclude that vx P E; hence, the vertex x is dominated by
v P V zX.


PROJECTIVE DIMENSION OF GRAPHS AND THE REGULARITY OF BIPARTITE GRAPHS

11

Proposition 3.22. ΥpLpN rGsqq “ ΓpGq for any graph G.
Proof. Suppose that A is a vertex-wise dominating set of LpN rGsq for which we write
A “ Av Y Ae , where Av Ď V and Ae Ď EpN rGsq. Observe that if F P Ae , then there
exists x P V such that F “ NG rxs. Now, we define B :“ tx P V : NG rxs P Ae u, and claim
that the set C :“ Av Y B is a minimal dominating set for G. Let v P V zC be given. It
then follows from the definition that there exists v 1 P NG rvs such that NG rv 1 s P EpN rGsq.
If v 1 P C, then v is dominated by the vertex v 1 so that we may further assume that v 1 R C.
Now, consider the edge pv, NG rv 1 sq of LpN rGsq. Since A is vertex-wise dominating, the
edge pv, NG rv 1 sq must be vertex-wise dominated by a vertex in A. If u P Av is a vertex
that vertex-wise dominates the edge pv, NG rv 1 sq, then u P NG rv 1 s Ď NG rvs so that uv P E,
that is, u dominates v in G. On the other hand, if there exists a vertex w P V such
that NG rws P Ae vertex-wise dominates the edge pv, NG rv 1 sq, then we have v P NG rws.
However, it means that the vertex w P B dominates v in G. This proves that C is a
dominating set for G.
For the other direction, suppose that S Ď V is a dominating set for G. We claim
that it is also a vertex-wise dominating set for LpN rGsq. Consider an edge px, NG rysq
of LpN rGsq. Since S is a dominating set for G, we must have NG rys X S ‰ H. This in
particular forces that there exists s P S such that sy P E. However, it then follows that
the vertex s vertex-wise dominates the edge px, NG rysq.

Theorem 3.23. proj-dimpDompGqq “ ΓpGq for any graph G.
Proof. We clearly have ipN rGsq “ |G| ´ ΓpGq so that hpDompGqq “ |G| ´ ipN rGsq “
ΓpGq ď proj-dimpDompGqq. On the other hand, we have
proj-dimpDompGqq “ proj-dimpN rGsq ď regpLpN rGsqq
ď βpLpN rGsqq ď ΥpLpN rGsqq “ ΓpGq
by Proposition 3.22.



4. Projective dimension of graphs and regularity of subdivisions
In this section, we provide a detail analysis on the consequences of Corollary 3.15 when
H “ H is just a graph. This will include the comparison of upper and lower bounds both
on projective dimension of a graph G and those of the regularity of its subdivision graph
SpGq. However, we first restate Corollary 3.15 in the graph’s case for completeness:
Corollary 4.1. proj-dimpGq ď regpSpGqq for any graph G.
Proposition 4.2. For any graph G, there exists a subgraph H (not necessarily induced)
of G such that proj-dimpHq “ regpSpGqq.
Proof. Suppose that regpSpGqq “ m, and let R Ď V and F Ď E be subsets satisfying
r m´1 pSpGqrR Y F sq ‰ 0 for which we may assume that both sets R and F are minimal
H
with this property. Now, we define H :“ pV pF q, F q and claim that it satisfies the required
property. In order to prove that it suffices to verify the homotopy equivalence SpHq »
SpGqrR Y F s, since we already have ΣpIndpHq_ q » SpHq. If x P V pF qzR and x P
NSpGqrRYF s pf q for some f P F , then degSpGqrRYF s pf q “ 1 by the minimality of the sets
R and F ; hence, if y is the only neighbour of f in SpGqrR Y F s, then we must have

12

TÜRKER BIYIKOĞLU AND YUSUF CIVAN

NSpHq pyq Ď NSpHq pxq, which in turn implies that SpHq » SpHq ´ x. It then follows that
we can remove any vertex in V pF qzR without altering the homotopy type of SpHq, that
is, SpHq » SpHq ´ pV pF qzRq – SpGqrR Y F s.

Lemma 4.3. Let G “ pV, Eq be a graph with regpSpGqq “ m ą 0. Then for any
m ą k ě 0, there exists an induced subgraph Hk of G such that regpSpHk qq “ k.
Proof. By the prime factorization theorem of [4], the graph SpGq has a prime factorization,
say tR1 , . . . , Rs u. Now, if v P V pR1 q X V , we have regpR1 q “ regpR1 ´ NR1 rvsq ` 1, since
R1 is a prime graph. However, since the disjoint union pR1 ´ NR1 rvsq Y R2 Y . . . Y Rs is
an induced subgraph of SpGq ´ NSpGq rvs – SpG ´ vq; it then follows that
regpSpGqq ě regpSpG ´ vqq ě regpR1 ´ NR1 rvsq ` regpR2 q ` . . . ` regpRs q
“pregpR1 q ´ 1q ` regpR2 q ` . . . ` regpRs q
“ regpSpGqq ´ 1.
Therefore, we have either regpSpGqq “ regpSpG´vqq or else regpSpGqq “ regpSpG´vqq`1
so that the claim follows from the induction on the order of G.

One of the immediate consequence of Lemma 4.3 is the following:
Corollary 4.4. Any graph G has an induced subgraph H such that proj-dimpGq “
regpSpHqq.
We note that even if Corollary 4.4 does not exactly determines the corresponding induced subgraph H of G satisfying proj-dimpGq “ regpSpHqq, it naturally translates the
projective dimension of graphs to that of the regularity of bipartite graphs.
Our next aim is to compare various upper and lower bounds on the projective dimension
and the regularity of graphs. We begin with interpreting the relevant invariants of a graph
G in terms of those of the subdivision graph SpGq.
Proposition 4.5. impSpGqq “ |G| ´ γpGq for any graph G without any isolated vertices.
Proof. Suppose that γpGq “ |D| for some dominating set D Ď V . Then for any vertex
x P V zD, there exists a vertex d such that xd P E. Now, the set tpx, xdq : x P V zDu of
edges of SpGq forms an induced matching in SpGq; hence, we have impSpGqq ě |G|´γpGq.
On the other hand, let M “ tpx1 , e1 q, . . . , pxn , en qu be a maximum induced matching of
SpGq. We claim that the set D :“ V ztx1 , . . . , xn u is a dominating set for G so that
impSpGqq ď |G| ´ γpGq. Indeed, for any vertex xi P V zD, the other end vertex of ei , say
yi , must be contained in D, since otherwise the set M would not be an induced matching;
hence, we have xi P NG pDq.

We recall that the equality hpIndpGq_ q “ |G| ´ ipGq holds for any graph G by our
previous remark for hypergraphs. On the other hand, the flower number νpSpGqq :“
νpIndpGq_ q is rather complicated to describe.
We call a subset X Ď V as an unstable dominating set of G, if X is a dominating set
for G with EpGrXsq ‰ H. The least cardinality of an unstable dominating set is called
the unstable domination number of G and denoted by γus pGq. Observe that the inequality
γpGq ď γus pGq ď γpGq ` 1 always holds for any graph G.
Lemma 4.6. νpSpGqq “ |G| ´ γus pGq for any graph G without any isolated vertices.

PROJECTIVE DIMENSION OF GRAPHS AND THE REGULARITY OF BIPARTITE GRAPHS

13

Proof. Suppose that tpx1 , e1 q, . . . , pxn , en qu is a maximum flower in SpGq. This in particular implies that the set X :“ tx1 , . . . , xn u is face of IndpGq_ . However, this means that
X misses at least one edge of G. It then follows that V zX is an unstable dominating set
for G, since each vertex xi is dominated by the other end vertex of ei contained in V zX;
hence, νpSpGqq ď |G| ´ γus pGq.
Assume next that Y Ď V is an unstable dominating set for G with γus pGq “ |Y |.
Then, for each u P V zY , there exists a vertex y P Y such that uy P E. However, the set
tpu, uyq : u P V zY u forms a flower for SpGq, since EpGrY sq ‰ H; hence, we conclude that
|G| ´ γus pGq ď νpSpGqq.

We note that the equality maxt|G| ´ γus pGq, |G| ´ ipGqu “ |G| ´ γpGq clearly holds for
any graph G so that Proposition 4.5 also follows from Corollary 3.10.
Corollary 4.7. If γpGq “ ipGq, then impSpGqq ď proj-dimpGq ď regpSpGqq.
4.1. Domination bounds and the regularity of subdivisions. We prove in this
subsection that all known upper bounds to projective dimension of graphs are in fact
upper bounds to the regularity of subdivision graphs. Before we proceed further, we state
the following upper and lower bounds on the projective dimension of graphs due to Dao
and Schweig [8].
Theorem 4.8. [8] For any graph G,
|G| ´ ipGq ď proj-dimpGq ď |G| ´ maxtτ pGq, ǫpGqu.
We next verify that both upper bounds of Theorem 4.8 are in fact upper bounds to
regpSpGqq. For that purpose, we reformulate the related graph parameters of G in terms
of those of the graph SpGq.
We recall that for any graph G “ pV, Eq, the square G2 of G is defined to be the graph
on V pG2 q “ V such that xy P EpG2 q if and only if distG px, yq ď 2. Moreover, we denote
by αpGq, the independence number of the graph G.
Lemma 4.9. For any graph G, the equality τ pGq “ αpG2 q holds.
Proof. Assume that αpG2 q “ k, and let A “ ta1 , . . . , ak u be an independent set of G2 .
Note that distG pai , aj q ě 3 for any i ‰ j, and in particular, the set A is also an independent
set of G. If X Ď V is a subset satisfying A Ď NG pXq, we necessarily have |A| ď |X|,
since |A X NG pxq| ď 1 for any x P X. However, it then follows that k ď |X| ď τ pGq, that
is, αpG2 q ď τ pGq.
Suppose now that τ pGq “ n, and let A Ď V be an independent subset of G of minimal
order satisfying γpA; Gq “ n. Furthermore, we let X Ď V be a subset such that A Ď
NG pXq and |X| “ n. Since X is minimal, each vertex in X has at least one private
neighbour in A. In other words, we have PAX pxq ‰ H for any x P X.
On the other hand, since A is minimal, every vertex of A must be the private neighbour
of a vertex in X. In other words, for each a P A, there exists a unique xa P X such that
a P PAX pxa q. We then claim that A is an independent set of G2 . Assume otherwise
that there exist a, b P A such that distG pa, bq “ 2, and let u P NG paq X NG pbq be any
vertex. Observe that u R X by the minimality of A. However, it then follows that
A Ď NG pY q, where Y :“ pXztxa , xb uq Y tuu, a contradiction. Therefore, we conclude that
αpG2 q ě |A| ě |X| “ n. This completes the proof.


14

TÜRKER BIYIKOĞLU AND YUSUF CIVAN

The following result of Horton and Kilakos [15] relates the independence number of the
square of a graph to the edge domination number of the subdivision graph.
Theorem 4.10. [15] If G is a graph, then γ 1 pSpGqq ` αpG2 q “ |G|.
We now arrive the proof of the first part of our claim regarding the upper bounds of
Theorem 4.8.
Corollary 4.11. The equality cochordpSpGqq “ |G| ´ τ pGq holds for any graph G. In
particular, we have proj-dimpGq ď cochordpSpGqq.
Proof. We proved in [3] that if G is a graph with girthpGq ě 5, then cochordpGq “ γ 1 pGq.
Since girthpSpGqq ě 6, the result follows from Lemma 4.9 and Theorem 4.10. The last
claim is the consequence of Corollary 4.1 together with the fact that regpHq ď cochordpHq
for any graph H.

Corollary 4.12. If G is a chordal graph, then regpSpGqq “ impSpGqq “ |G| ´ γpGq.
Proof. The equality γpGq “ τ pGq holds for any chordal graph [2]; hence, the claim follows
from Proposition 4.5 and Corollary 4.11.

We next verify that the edge-wise domination number of G is closely related to the
upper vertex-wise domination number of the subdivision graph of G.
Theorem 4.13. ΥpSpGqqq “ |G| ´ ǫpGq for any graph G without any isolated vertex.
Proof. Let M be an edge-wise dominating matching of G with |M| “ ǫpGq, and let U :“
UpMq be the set of unmatched vertices of G with respect to M. We then claim that the
set U Y M is a minimal vertex-wise dominating set for SpGq. Observe that it only suffices
to prove that U Y M is minimal, since it is clearly a vertex-wise dominating set. If u P U,
then there exists a v P V pMq such that eu “ uv P E, since M is an edge-wise dominating
matching of G. In particular, the edge pu, eu q of SpGq is only dominated by the vertex
u, that is, the edge pu, eu q is a vertex-wise private neighbour of u. On the other hand, if
f “ xy P M, then the edge px, f q of SpGq is a vertex-wise private neighbour of f ; hence,
the claim follows. However, we then have |G| ´ ǫpGq “ |G| ´ |M| “ |U| ` |M| ď ΥpSpGqq.
We prove the reversed inequality in three steps. Note that when A is a vertex-wise
dominating set of SpGq, we write A “ Av Y Ae such that Av Ď V and Ae Ď E. We first
verify that there exists a vertex-wise dominating set A of SpGq of appropriate size such
that Ae ‰ H. We then show that among any such vertex-wise dominating sets, we can
find one A for which the set Ae is an edge-wise dominating matching of G.
Claim 1. For any connected graph G, there exists a minimal vertex-wise dominating
set A with ΥpSpGqq “ |A| such that Ae ‰ H.
Proof of Claim 1: Suppose that SpGq admits a minimal vertex-wise dominating set A
with ΥpSpGqq “ |A| such that Ae “ H, that is, A “ Av Ď V . We note that for each
x P A, there exists a vertex yx P NG pxq such that yx R A, since otherwise A could not
be minimal. We claim that such a vertex yx P NG pxq is unique for each x P A. Suppose
otherwise that there exist x P A together with y1 , . . . , yk P NG pxq such that y1 , . . . , yk R A.
However, it then follows that the set pAztxuq Y te1 , . . . , ek u, where ei “ yi x for i P rks,
would be a minimal vertex-wise dominating set for SpGq having larger size than A, which
is not possible. Therefore, the vertex yx must be unique for each x P A. Now, if we

PROJECTIVE DIMENSION OF GRAPHS AND THE REGULARITY OF BIPARTITE GRAPHS

15

let B :“ pAztxuq Y tex u, where ex :“ yx x P E, then the set B is a minimal vertex-wise
dominating set of SpGq with Be ‰ H and |B| “ |A| “ ΥpSpGqq.
Claim 2. For any connected graph G, there exists a minimal vertex-wise dominating
set A with ΥpSpGqq “ |A| such that Ae is an edge-wise dominating set for G.
Proof of Claim 2: We first verify that such a set Ae can be turned into an edge-wise
dominating set for G. Suppose that Ae is not edge-wise dominating for G. So, there exists
a vertex x P V such that x is neither an end vertex of an edge in Ae nor it is adjacent
to any end vertex of an edge in Ae . Assume first that x R Av . This in particular implies
that NG pxq Ď Av . Pick a neighbour, say y P NG pxq. Observe that if f is an edge of G
incident to y, then f R Ae . If NG pyqztxu Ď Av , then the set pAztyuq Y txyu is a minimal
vertex-wise dominating set of SpGq having size ΥpSpGqq such that x is dominated by the
edge xy in G. Thus, we may assume that the vertex y has at least one neighbour in G
other than x not contained by Av . We denote by Ly , the set of such vertices. We note
that the set Ly can not contain a vertex w such that any edge of G incident to w is not
contained by Ae . Indeed, if we add the edge yw to pAztyuq Y txyu for any such vertex
w P Ly , the resulting set would be a minimal vertex-wise dominating set for SpGq, which
is not possible. This forces that every vertex w in Ly has at least one incident edge in Ae .
However, it then follows that the set pAztyuq Y txyu is a minimal vertex-wise dominating
set of SpGq for which the vertex x is now dominated by the edge xy in G.
Assume next that x P Av . In such a case there must exist at least one vertex in NG pxq
not contained in Av by the minimality of A. We denote by Tx , the set of such vertices.
Observe that no incident edges to a vertex z in Tx can be contained in Ae by the choice
of x. However, this forces that any vertex adjacent to a vertex in Tx must belong to Av .
Now, if we define A1 :“ pAztxuq Y txz : z P Tx u, then the set A1 is clearly a minimal
vertex-wise dominating set for SpGq. However, since |A| “ ΥpSpGqq, this could be only
possible when |Tx | “ 1. If Tx “ tzu, then the set pAztxuq Y txzu is a minimal vertex-wise
dominating set for SpGq for which the vertex x is dominated by the edge xz in G.
As a result, since we only replace a vertex in V by an edge in E for A, the resulting set
Ae is always an edge-wise dominating set of G.
Claim 3. For any connected graph G, there exists a minimal vertex-wise dominating
set A with ΥpSpGqq “ |A| such that Ae is an edge-wise dominating matching for G.
Proof of Claim 3: Suppose that A is a vertex-wise dominating set with ΥpSpGqq “ |A|
satisfying the following properties:
piq Ae is an edge-wise dominating set for G of minimum possible size among any minimal vertex-wise dominating sets for SpGq of maximum size,
piiq the set Ae contains least number of pairs of incident edges in G among sets satisfying the condition piq.
Let e “ xy and f “ yz be two such edges in Ae . This in particular implies that neither x
nor z can belong to Av . Moreover, no edge incident to either x or z can be contained in Ae
by the minimality of A. Note also that we must have degG pxq, degG pzq ą 1. For instance,
if degG pxq “ 1, then the set B :“ pAzteuq Y txu is a minimal vertex-wise dominating set
for SpGq in which Be has fewer pairs of adjacent edges than Ae , a contradiction. So, let
w be a neighbour of x in G. If w R Av , we then define C :“ pAzteuq Y txwu so that the

16

TÜRKER BIYIKOĞLU AND YUSUF CIVAN

set C provides a minimal vertex-wise dominating set for SpGq in which Ce has fewer pairs
of incident edges than Ae . Therefore, we must have NG pxqztyu Ď Av . We claim that
not every vertex in NG pxqztyu can be edge-wise dominated by some edge in Ae . Since
otherwise, the set B :“ pAzteuq Y txu would be a minimal vertex-wise dominating set for
SpGq for which |Be | ă |Ae |, violating the condition piq. So, we define Kx to be the subset
of NG pxqztyu consisting of those vertices being the edge-wise private neighbours of the
edge e “ xy. If we pick a vertex, say p P Kx , and define D :“ pAzteuq Y txpu, then the
set D is a minimal vertex-wise dominating set for SpGq with |D| “ |A|. In particular,
De is an edge-wise dominating set for G having fewer pairs of incident edges than Ae , a
contradiction. This completes the proof of Claim 3.
Finally, we conclude that ΥpSpGqq “ |A| “ |Av |`|Ae | ď |G|´|Ae |, where the inequality
is due to the fact that Ae is a matching for G. On the other hand, since Ae is an edgewise dominating set for G, we must have |Ae | ě ǫpGq from which we conclude that
ΥpSpGqq ď |G| ´ ǫpGq.

The first part of the proof of Theorem 4.13 together with the fact that βpHq ď ΥpHq
for any graph H give rise to the following fact.
Corollary 4.14. βpSpGqq “ ΥpSpGqq “ |G| ´ ǫpGq for any graph G.
We remark that it is not known in general whether the equality βpHq “ ΥpHq holds
for any graph H [17].
The following result completes the proof of our claim regarding the upper bounds of
Theorem 4.8:
Corollary 4.15. regpSpGqq ď ΥpSpGqq “ |G| ´ ǫpGq for any graph G.
Proof. The claim follows from Theorems 3.19 and 4.13.



We close this section by showing that the regularity of any bipartite graph can be
bounded from above by its induced matching number from which we may readily deduced
an upper bound on the projective dimension of graphs.
Theorem 4.16. If B is a bipartite graph with a bipartition V pBq “ X YY , then regpBq ď
1
pimpBq ` mint|X|, |Y |uq.
2
Proof. We only prove the inequality regpBq ď 12 pimpBq ` |Y |q from which the general
claim follows.
We start with the graph B0 :“ B having the bipartition X0 :“ X and Y0 :“ Y . We
then introduce a reduction process that creates a bipartite graph Bi in each state i ě 0,
and associate a pair of integers pprci , imci q to Bi by letting prc0 :“ 0 and imc0 :“ 0 at
the bottom.
Now, pick a vertex xi P Xi for i ě 0, and assume first that xi is not a prime vertex
of Bi . If degBi pxi q ě 2, we define Bi`1 to be the bipartite graph having the bipartition
V pBi`1 q “ Xi`1 Y Yi`1 , where Xi`1 :“ Xi ´ xi , Yi`1 :“ Yi together with pprci`1 , imci`1 q “
pprci , imci q.
On the other hand, if degBi pxi q “ 1 and yi is the only neighbour of it in Bi , we let
Bi`1 to be the bipartite graph with Xi`1 :“ Xi ´ NBi pyi q, Yi`1 :“ Yi ´ yi , and set
imci`1 :“ imci `1, while prci`1 :“ prci (compare to Lemma 3.25 of [4]).

PROJECTIVE DIMENSION OF GRAPHS AND THE REGULARITY OF BIPARTITE GRAPHS

17

If xi is a prime vertex of Bi , we take Bi`1 to be the bipartite graph with Xi`1 :“ Xi ´xi ,
Yi`1 :“ Yi ´NBi pxi q, and set prci`1 :“ prci `1 and imci`1 :“ imci . We proceed this process
until there exists a j ě 0 such that Xj “ H or Yj “ H.
Observe that regpBq “ prcj ` imcj and that the inequalities imcj ď impBq and prcj ď
1
p|Y | ´ imcj q hold. However, we then have
2
1
regpBq “ prcj ` imcj ď p|Y | ´ imcj q ` imcj
2
1
“ p|Y | ` imcj q
2
1
ď p|Y | ` impBqq.
2

Corollary 4.17. For any graph G, we have proj-dimpGq ď |G| ´ 21 γpGq.
Proof. Since impSpGqq “ |G| ´ γpGq by Proposition 4.5, it then follows from Corollary 4.1
together with Theorem 4.16 that
1
1
1
proj-dimpGq ď regpSpGqq ď pimpSpGqq ` |G|q “ p|G| ´ γpGq ` |G|q “ |G| ´ γpGq.
2
2
2

Observe that the bound of Corollary 4.17 is sharp as the graph C4 satisfies that
proj-dimpC4 q “ 3 “ regpC8 q “ |C4 | ´ 12 γpC4 q “ 3.
We leave it open the discussion whether the hypergraph versions of the domination
parameters, the independence domination number τ pHq and the edge-wise domination
number ǫpHq of a hypergraph H as they are introduced in [9, 10] provide upper bounds on
the regularity of the Levi graph of H. However, we prefer to state an interesting connection
between the parameter ǫpHq and the induced matching number of the corresponding Levi
graph.
Definition 4.18. Let B be a bipartite graph with a bipartition X Y Y containing no
isolated vertex. We define hX pBq to be the least cardinality of a subset S Ď X such that
for every y P Y there exists an s P S satisfying distB ps, yq ď 3 (the parameter hY pBq can
be defined analogously).
Lemma 4.19. ǫpHq “ hE pLpHqq ď impLpHqq for any hypergraph H “ pV, Eq.
Proof. The equality is a direct consequence of the definitions, and for the inequality,
suppose that tE1 , . . . , Ek u Ď E is a minimal edge-wise dominating set of cardinality ǫpHq.
By the minimality, there exists a vertex vi P Ei which is privately edge-wise dominated
by Ei in LpHq. However, the set tpv1 , E1 q, . . . , pvk , Ek qu forms an induced matching in
LpHq.

Observe that Theorem 4.16 naturally implies that regpLpHqq ď |H| ´ hE pHq whenever
impLpHqq ď |H|{3 or regpLpHqq ď |H|{2. On the other hand, the inequality τ pHq `
hV pLpHqq ď |H| trivially holds for any hypergraph H. In particular, we wonder whether
such a special notion of a distance-three domination on bipartite graphs always provides
an upper bound to the regularity of such graphs.

18

TÜRKER BIYIKOĞLU AND YUSUF CIVAN

Question 4.20. Does the inequality regpBq ď maxt|X| ´ hY pBq, |Y | ´ hX pBqu hold for
any bipartite graph with a bipartition X Y Y containing no isolated vertex?
5. Projectively prime graphs
In this section, in analogy with the notion of prime graphs introduced for the regularity
calculations of graphs [4], we demonstrate that a similar notion could be useful for the
projective dimension of graphs as well.
Definition 5.1. A connected graph G is called a projectively prime graph over a field
k, if proj-dimk pG ´ xq ă proj-dimk pGq for any vertex x P V pGq. Furthermore, we call a
connected graph G as a perfect projectively prime graph if it is a projectively prime graph
over any field.
Obvious examples of perfect projectively prime graphs can be given by the paths P3k
and P3k`2 for any k ě 1, and cycles Cn for any n ě 3. The primeness of the corresponding paths directly follows from Corollary 4.7 together with the fact that regpSpPm qq “
impSpPm qq “ t 2m´1
u for any m ě 2. Apart from these, our next result shows that the
3
join of any two graphs is a perfect projectively prime graph.
When G and H are two graphs on the disjoint set of vertices, we write G ˚ H, the
join of G and H, for the graph obtained from the disjoint union G Y H by inserting an
edge between any two vertices x P V pGq and y P V pHq. The calculation of projective
dimension of the graph G ˚ H seems to first appear in [20], while we here provide an
independent proof.
Proposition 5.2. If G and H are two graphs on the disjoint sets of vertices, then the
graph G˚H is a perfect projectively prime graph. In particular, we have proj-dimpG˚Hq “
regpSpG ˚ Hqq “ |G| ` |H| ´ 1.
Proof. We prove the second claim from which the projectively primeness of G ˚ H directly
follows. Since ǫpG ˚ Hq “ 1, we have proj-dimpG ˚ Hq ď regpSpG ˚ Hqq ď |G| ` |H| ´ 1
by Corollary 4.15. On the other hand, the Alexander dual of IndpG ˚ Hq triangulates a
p|G| ` |H| ´ 3q-dimensional sphere. Indeed, the complex IndpG ˚ Hq_ is just the simplicial
join of the boundary complexes of corresponding simplexes on V pGq and V pHq. Therefore,
we have |G| ` |H| ´ 1 ď proj-dimpG ˚ Hq from which we conclude the claim.

We note that the complete multipartite graph Kn1 ,...,nm for any ni ě 1 and m ě 2 is a
perfect projectively prime graph as a result of Proposition 5.2.
As in the case of prime graphs, the notion of projectively prime graphs allows us
to reformulate the projective dimension as a generalized (weighted) induced matching
problem that we describe next.
Definition 5.3. Let G be a graph and let R “ tR1 , . . . , Rr u be a set of pairwise vertex
disjoint induced subgraphs of G such that |V pRi q| ě 2 for each 1 ď i ď r. Ť
Then R is
said to be an induced decomposition of G if the induced subgraph of G on ri“1 V pRi q
contains no edge of G that is not contained in any of EpRi q, and and R is maximal with
this property. The set of induced decompositions of a graph G is denoted by IDpGq.

PROJECTIVE DIMENSION OF GRAPHS AND THE REGULARITY OF BIPARTITE GRAPHS

19

Definition 5.4. Let R “ tR1 , . . . , Rr u be an induced decomposition of a graph G. If each
Ri is a projectively prime graph, then we call R as a projectively prime decomposition of
G, and the set of projectively prime decompositions of a graph G is denoted by PDpGq.
Obviously, the set PDpGq is non-empty for any graph G.
Theorem 5.5. For any graph G and any field k, we have
r
ÿ
proj-dimk pGq “ maxt proj-dimk pHi q : tH1 , . . . , Hr u P PDk pGqu.
i“1

Proof. If G is itself a projectively prime graph, there is nothing to prove. Otherwise there
exists a vertex x P V such that proj-dimpGq “ proj-dimpG ´ xq. If G ´ x is a projectively
prime graph, then tG ´řxu P PDpGq so that the result follows. Otherwise, we have
proj-dimpG ´ xq “ maxt ti“1 proj-dimpSi q : tS1 , . . . , St u P PDpG ´ xqu by the induction.
However, since PDpG ´ xq Ď PDpGq for such a vertex, the claim follows.


By taking the advantage of Theorem 5.5, we next present examples of graphs showing
that most of the bounds on the projective dimension of graphs involving domination
parameters are in fact far from being tight. Beforehand, we need the following well-known
fact first.
Lemma 5.6. [7] For any vertex x of a graph G,
(5.7)

proj-dimpGq ď maxtproj-dimpG ´ NG rxsq ` degG pxq, proj-dimpG ´ xq ` 1u.

Proposition 5.8. For each integer a ě 1, there exists a graph Ga satisfying
(5.9)

|Ga | ´ ipGa q ` a ă proj-dimpGa q ă |Ga | ´ γpGa q ´ a.

Proof. Assume that k and r are two positive integers with k ą r ` 1. Let Tk :“ Kk,k
be the complete bipartite graph and fix a vertex v P V pTk q. We take Sr :“ rP3s`1 ,
which is the disjoint r copies of the path on 3s ` 1 vertices (s ě 1) together with a
leave vertex xi from each copy. Now, we from the graph G2k,r on V pTk q Y V pSr q such
that EpG2k,r q “ EpTk q Y EpSr q Y txi v : i P rrsu. Observe that ipG2k,r q “ sr ` k and
γpGr q “ sr ` 2. Since tKk,k , rP3s u is a projectively prime decomposition of G2k,r , we
have 2k ´ 1 ` 2rs ď proj-dimpG2k,r q by Theorem 5.5. Moreover, proj-dimpG2k,r ´ vq “
p2k ´2q`2rs and proj-dimpG2k,r ´NG2k,r rvsq “ 2rs so that proj-dimpGr q “ 2k `2rs´1 by
the inequality (5.7). Consequently, if we choose k “ 2r, we then have proj-dimpG4r,r q ´
p|G4r,r | ´ ipG4r,r qq “ r ´ 1 and p|G4r,r | ´ γpG4r,r qq ´ proj-dimpG4r,r q “ r ´ 1. This in
particular implies that if we define Ga :“ G4pa`2q,a`2 , then
p|Ga | ´ ipGa qq ` a ă proj-dimpGa q ă p|Ga | ´ γpGa qq ´ a
as claimed.



Proposition 5.10. For each integer b ě 1, there exists a graph Hb satisfying
(5.11)

|Hb | ´ γpHb q ` b ă proj-dimpHb q ă |Hb | ´ ǫpHb q ´ b.

Proof. We assume that k and r are two positive integers with k ą r ` 2.
Lk,r :“ rKk,k and pick a vertex vi from each copy of Kk,k . Then, define Rk,r
graph on V pLk,r q Y txu, where x is a vertex disjointly chosen from V pLk,r q,
EpRk,r q :“ EpLk,r q Y txvi : i P rrsu. Observe that |Rk,r | “ 2rk ` 1, γpRk,r q

We take
to be the
such that
“ 2r and

20

TÜRKER BIYIKOĞLU AND YUSUF CIVAN

ǫpRk,r q “ r. Furthermore, we have proj-dimpRk,r q “ p2k ´ 1qr, which follows from the
inequality (5.7) together with the fact that trKk,k u is a projectively prime decomposition
of Rk,r .
Secondly, we define another graph Zk,r on V ppr ` 1qKk,k q Y ty2 , . . . , yr`1 u by EpZk,r q “
Eppr ` 1qKk,k q Y tv1 yj , vj yj : j P t2, 3, . . . , r ` 1uu, where the vertex vl is chosen from the
lth -copy of Kk,k . Observe that |Zk,r | “ 2kpr ` 1q ` r, γpZk,r q “ 2pr ` 1q and ǫpZk,r q “ r ` 1.
Again, by considering the vertex v1 in the inequality (5.7) together with the projectively
prime decomposition tpr ` 1qKk,k u of Zk,r , we note that proj-dimpZk,r q “ p2k ´ 1qpr ` 1q.
Now, assuming that we construct Rk,r and Zk,r on the disjoint sets of vertices, we form
a new graph Hk,r on V pRk,r q Y V pZk,r q by EpHk,r q :“ EpRk,r q Y EpZk,r q Y txv1 u. It
then follows that |Hk,r | “ 2kp2r ` 1q ` r ` 1, γpHk,r q “ 2p2r ` 1q and ǫpHk,r q “ 2r ` 1.
Once again, the inequality (5.7) with respect to the vertex v1 of Hk,r together with the
projectively prime decomposition trKk,k , pr ` 1qKk,k u, where the first prime arises from
Rk,r and the second comes up from Zk,l yields that proj-dimpHk,r q “ p2k ´ 1qp2r ` 1q.
Finally, if we define Hb :“ Hb`4,b`1 , we conclude that proj-dimpHb q ´ p|Hb | ´ γpHb qq “
b ` 1 and p|Hb | ´ ǫpHb qq ´ proj-dimpHb q “ b ` 2 so that the claimed inequality
|Hb | ´ γpHb q ` b ă proj-dimpHb q ă |Hb | ´ ǫpHb q ´ b
holds.



Regarding the results of Propositions 5.8 and 5.10 together with Theorem 5.5, the most
prominent question would be investigation of the structural properties of projectively
prime graphs as well as operations on graphs that preserve projectively primeness. It
would be interesting to determine under what conditions on a projectively prime graph
G, the inequality proj-dimpGq ď |G|´γpGq holds. We predict that C3k`1 -free projectively
prime graphs satisfy such an inequality.

References
[1] R. Aharoni, E. Berger and R. Ziv, A tree version of König’s theorem, Combinatorica,
22, (2002), 335-343.
[2] R. Aharoni and T. Szabó, Vizing’s conjecture for chordal graphs, Discrete Math.,
309, (2009), 1766-1768.
[3] T. Bıyıkoğlu and Y. Civan, Vertex-decomposable graphs, codismantlability, CohenMacaulayness, and Castelnuovo-Mumford regularity, Electronic J. Combin., 21:1,
(2014), #P1, 1-17.
[4] T. Bıyıkoğlu and Y. Civan, Castelnuovo-Mumford regularity of graphs, available at
arXiv:1503.06018(v1), (2015), 43pp.
[5] R. Boutrig, M. Chellali, T.W Haynes and S.T. Hedetniemi, Vertex-edge domination
in graphs, Aequat. Math., 90, (2016), 355-366.
[6] P. Csorba, Subdivision yields Alexander duality on independence complexes, Electronic J. Combin., 16:2, (2009), #P11, 1-7.
[7] H. Dao, C. Huneke and J. Schweig, Bounds on the regularity and projective dimension
of ideals associated to graphs, J. Algebraic Combin., 38:1, (2013), 37-55.

PROJECTIVE DIMENSION OF GRAPHS AND THE REGULARITY OF BIPARTITE GRAPHS

21

[8] H. Dao and J. Schweig, Projective dimension, graph domination parameters, and
independence complex homology, J. Combin. Theory, Series A, 432:2, (2013), 453469.
[9] H. Dao and J. Schweig, Bounding the projective dimension of a squarefree monomial
ideal via domination in clutters, Proc. Amer. Math. Soc., 143, (2015), 555-565.
[10] H. Dao and J. Schweig, Further applications of clutter domination parameters to
projective dimension, J. Algebra, 432, (2015), 1-11.
[11] E.C. de Verdière, G. Ginot and X. Goaoc, Helly numbers of acyclic families, Advances
Math., 253, (2014), 163-193.
[12] A. Engström, Complexes of directed trees and independence complexes, Discrete
Math., 309:10, (2009), 3299-3309.
[13] J. Jonsson, On the topology of independence complexes of triangle-free graphs, unpublished manuscript, (2011), available at math.kth.se/ jakobj.
[14] H.T. Há and R. Woodroofe, Results on the regularity of squarefree monomial ideals,
Adv. Appl. Math, 58, (2014), 21-36.
[15] J.D. Horton and K. Kilakos, Minimum edge dominating sets, Siam J. Disc. Math.,
6:5, (1993), 375-387.
[16] G. Kalai and R. Meshulam, Leray numbers of projections and a topological Helly type
theorem, J. Topology, 1, (2008), 551-556.
[17] J. Lewis, Vertex-edge and Edge-vertex Parameters in Graphs, Phd Thesis, Clemson
University, (2007).
[18] M. Marietti and D. Testa, A uniform approach to complexes arising from forests,
Elect. J. Comb., 15, (2008), #R101.
[19] S. Morey and R.H. Villarreal, Edge ideals: algebraic and combinatorial properties, In
Progress in Commutative Algebra, Combinatorics and Homology, Vol.1, De Gruyter,
Berlin, (2012), pp. 85-126.
[20] A. Mousivand, Algebraic properties of product of graphs, Commun. Algebra, 40,
(2012), 4177-4194.
[21] U. Nagel and V. Reiner, Betti numbers of monomial ideals and shifted skew shapes,
Electronic J. Combin., 16:2, (2009), #R3.
[22] J.W. Peters, Theoretical and Algorithmic Results on Domination and Connectivity,
Phd Thesis, Clemson University, (1986).
[23] M. Tancer, Intersection patterns of convex sets via simplicial complexes, a survey,
Thirty Essays on Geometric Graph Theory, Springer, New York (2013), 521-540.
[24] N. Terai, Alexander duality theorem and Stanley-Reisner rings, Free resolution of
coordinate rings of projective varieties and related topics (Japanese) (Kyoto, 1998).
Surikaisekikenkyusho Kokyuroku, No:1078, (1999), 174-184.
[25] M. Yannakakis and F. Gavril. Edge dominating sets in graphs, SIAM J. on Applied
Math., 38:3, (1980), 364-372.

Department of Mathematics, Suleyman Demirel University, Isparta, 32260, Turkey.
E-mail address: tbiyikoglu@gmail.com and yusufcivan@sdu.edu.tr

