arXiv:1211.6555v1 [] 28 Nov 2012

Vertex covers and sensor networks
MAURIZIO IMBESI
Faculty of Sciences, Department of Mathematics,
University of Messina
Viale Ferdinando Stagno d’Alcontres, 31 − I 98166 Messina, Italy
e-mail: imbesim@unime.it
MONICA LA BARBIERA
Faculty of Sciences, Department of Mathematics,
University of Messina
Viale Ferdinando Stagno d’Alcontres, 31 − I 98166 Messina, Italy
e-mail: monicalb@unime.it

Abstract
We consider algebraic developments of graph theory through suitable applications in real
connection problems. We investigate ideals of vertex covers for the edge ideals associated
to a significative class of connected graphs. It is shown that algebraic procedures linked to
minimal vertex covering of such graphs are good instruments concerned about how sensor
networks can be encoded and their properties measured. Moreover algebraic properties of
such ideals are studied. Using the notion of linear quotients, standard algebraic invariants
are computed and these ideals are stated to be Cohen-Macaulay.
AMS 2010 Subject Classification: 05C25, 05E40, 13C15.
Key words and phrases: Ideals of vertex covers. Sensor network. Linear quotients and
standard invariants.

Introduction
In this paper we are interested in studying standard properties of monomial
ideals arising from a class of graphs in order to explain how algebraic models,
built through graph theory, are useful for setting suitable solutions of several
problems concerning network areas (infrastructure nets, circuits electrical
workers, urban and territorial analysis, wireless sensor networks, etc...).
In the last years, Commutative and Combinatorial Algebra have paid particular attention to large classes of monomial ideals derived from graphs in
order to describe algebraic properties of them. Such ideals turn out to be

very interesting from a combinatorial point of view too. Classical topics include graph algebraic theory, in particular the edge ideals, namely monomial
ideals generated in degree two which descend from the edges of a graph.
Moreover, using the notion of minimal covering for the nodes of a graph,
recent results show that it is possible to attach to graphs the so-called ideals of vertex covers; an intensive study of them carries to solve interesting
and unthinkable problems related to these fields. More precisely, the ideals
of vertex covers of a wide class of simple graphs are examined and useful
properties are studied. Moreover, we explain how algebraic methods arising
from graph theory are suitable solutions for several problems concerning the
wireless sensor networks.
Wireless sensor networks (WSNs) are an important technology for large-scale
monitoring, providing sensor measurements at high temporal and spatial resolution. A sensor network is composed of a large number of sensor nodes,
which are densely deployed either inside the phenomenon or very close to it.
These sensor nodes, which consist of sensing, data processing, and communicating components, leverage the idea of sensor networks based on collaborative effort of a large number of nodes. Sensor nodes are fitted with an
on-board processor. Instead of sending the raw data to the nodes responsible
for the fusion, sensor nodes use their processing abilities to locally carry out
simple computations and transmit only the required and partially processed
data. The above described features ensure a wide range of monitoring applications for sensor networks. Some of the application areas are environmental,
military, security and commercial ([1]).
We consider the problem of the placement of as few as possible leader nodes
which collect the information received by the sensors and send them to a base
station, so that each sensor is near to at least one of them. This problem is
related to the energy saving of the sensors. The suitable model to represent
this situation is a simple graph G and the problem is linked to the study
of the minimal vertex covers of G. We introduce a class of simple graphs
and some algebraic aspects linked to the minimal vertex covers are analyzed.
We show that the algebraic procedures introduced are good instruments concerned how this problem related to wireless sensor networks can be encoded
and solved.
Let G be a graph on n vertices v1 , . . . , vn . An algebraic object attached to G
is the edge ideal I(G), a monomial ideal of the polynomial ring in n variables
R = K[X1 , . . . , Xn ], K a field.
When G is a simple graph, I(G) is generated by squarefree
 monomials of
degree two in R, I(G) = {Xi Xj | {vi , vj } is an edge of G } .
The ideal of vertex covers of I(G), denoted by Ic (G) is the ideal of R generated by all the monomials Xi1 · · · Xik such that (Xi1 , . . . , Xik ) is an associated
2

prime ideal of I(G) ([9]). Under special situations, I(G) reflects properties of
Ic (G) and the study of I(G) states some properties of Ic (G). In particular, the
Cohen-Macaulay property of the ideals Ic (G) was studied by G. Lyubeznik
in [8] using graph theoretical methods; the central notion is that of chordal
graph, that is the right notion to express some homological properties of edge
ideals and the Cohen-Macaulay property of the ideal of vertex covers.
We examine a wide class of squarefree edge ideals associated to connected
graphs H consisting of the union of a complete graph Km and star graphs
with centers the vertices of Km . The ideals of vertex covers for the edge
ideals associated to the these graphs were described in [6]. The generators
of these ideals give all the minimal vertex covers and their cardinality. If H
is considered to be the model of a WSN, then the vertex covers with minimum cardinality give the position of the leaders in the sensor network that
H represents.
Moreover we study some algebraic aspects of the ideals Ic (H). We prove that
Ic (H) has linear quotients. In general, if a monomial ideal of R generated in
one degree has linear quotients, then it has a linear resolution ([2], Lemma
4.1). In our case, Ic (H) has linear quotients, but in general Ic (H) has not
a linear resolution because it is not generated in the same degree. Using
some properties of the graph H and of its edge ideal we can obtain conditions such that Ic (H) has a linear resolution and some algebraic invariants
are computed. Starting from theoretic properties of the graph H and of its
edge ideal we can obtain information about the Cohen-Macaulay property of
I(H) and of its ideal of vertex covers.
The work is subdivided as follows. In section 1 we describe the developments
of graph theory to networks concerning of problems of minimal vertex covers.
The class of graphs H and the ideals of vertex covers Ic (H) are analyzed as
a geometric model of a WSN using computational and algebraic methods.
In section 2 we examine algebraic properties of Ic (H). We prove that these
ideals have linear quotients and we investigate conditions such that they
have a linear resolution. Moreover using the technique of studying the linear
quotients of such ideals, as previously employed in [7], standard algebraic
invariants are calculated.

1

Developments of graph theory to networks

The aim of this section is to explain how algebraic and geometric models,
built through graph theory, are useful for setting suitable solutions of several
problems concerning the wireless sensor networks.
A wireless sensor network (WSN) consists of spatially distributed autonomous
3

sensors (called sensor nodes) to monitor physical or environmental conditions
(such as temperature, sound, vibration, pressure, humidity,...) and to pass
their data through the network to a main location. The sensors collect data
of interest and send them to special gateway nodes, which collect the information received by the sensors and send them to a base station. The sensor
networks can improve the quality of information: for example, can guarantee
a high fidelity, can provide information in real time and can reduce the cost
of transmitting the same information.
Current research indicates highly developments for this type of wireless networks which are already in use in many fields. Useful applications of sensor
networks are environmental, military, and commercial. Area monitoring is
a common application of WSNs that are deployed over a region where some
phenomenons are to be monitored: the urban traffic or natural phenomena
such as glaciers, volcanoes and earthquakes. Some environmental applications of sensor networks include tracking the movements of small animals;
detecting foreign chemical agents in the air and the water, irrigation; precision agriculture; environmental monitoring in marine; forest fire detection;
meteorological or geophysical research. Some of the commercial applications
are monitoring product quality; interactive museums; monitoring disaster
area; transportation; vehicle tracking and detection ([1]).
Consider a sensor network in which each sensor must send information it
has collected to the nearest gateway node. The problem is the placement
of as few as possible gateway nodes so that each sensor is near to at least
one of them. This problem is related to the energy saving of the sensors.
The formalization of the model to represent the sensor network is given by
a graph G = (V (G), E(G)), V (G) = {v1 , . . . , vn } is the set of nodes and
E(G) = {{vi , vj }|vi 6= vj , vi , vj ∈ V (G)} is the set of edges (if two nodes v1
and v2 are adjacent then {v1 , v2 } ∈ E(G)).
Our problem consists of finding a set of nodes leaders (gateway nodes) to be
responsible to send messages to nodes belonging to the higher level. Such
leaders must have the feature of being near to all nodes. This means that we
want to find a subset of nodes C ⊂ V (G) such that each node in V (G) \ C
is joined to a node in C. This is a problem of minimum vertex cover. The
optimization problem of minimum vertex cover is looking for a covering of
vertices of a graph that has minimum cardinality. The corresponding decision problem of vertex cover is, given a graph G and an integer k, if there is
a vertex covering of G of minimal cardinality k or of cardinality at most k.
The basic network topologies are represented by complete graphs, meshes,
star graphs, trees. A single network may consist of several interconnected
subnets of different topologies. We consider as a network topology a class of
simple graphs union of a complete graph and star graphs, and some algebraic
4

aspects linked to this problem of minimal vertex covers are analyzed.
Let’s introduce some preliminary notions.
Let G be a graph. A cycle of G of length q is a subgraph Cq of G such that
E(Cq ) = {{vi1 , vi2 }, {vi2 , vi3 }, . . . , {viq−1 , viq }, {viq , vi1 }}, where {vi1 , . . . , viq } ∈
V (G) and vij 6= vik if ij 6= ik . A chord of a cycle Cq is an edge {vij , vik } of G
such that vij and vik are vertices of Cq with {vij , vik } ∈
/ E(Cq ). A graph G is
said chordal or triangulated if every cycle Cq in G, q > 3, has a chord.
A graph G on n vertices v1 , . . . , vn is complete if there exists an edge for all
pairs {vi , vj } of vertices of G.
 It is denoted by Kn .
A star graph on vertex set {vi }, {v1 , . . . , vi−1 , vi+1 , vn } with center vi , denoted by stari (n), i = 1, . . . , n , is a complete bipartite graph of the form
K1, n−1 . The complementary graph of a graph G on {v1 , . . . , vn } is the graph
G on {v1 , . . . , vn } whose edge set E(G) consists of those 2-element subset
{vi , vj } for which {vi , vj } ∈
/ E(G).
If V (G) = {v1 , . . . , vn } and R = K[X1 , . . . , Xn ] is the polynomial ring
over a field K such that each variable Xi corresponds to the vertex vi , the
edge ideal I(G) associated to G is the ideal {Xi Xj | {vi , vj } ∈ E(G)} ⊂ R .
Definition 1.1. Let G be a graph with vertex set V (G) = {v1 , . . . , vn }. A
subset C of V (G) is said a minimal vertex cover for G if:
(1) every edge of G is incident with one vertex in C;
(2) there is no proper subset of C with this property.
If C satisfies condition (1) only, then C is called a vertex cover of G and
C is said to cover all the edges of G. The smallest number of vertices in any
minimal vertex cover of G is said vertex covering number. We denote it by
α0 (G).
We consider some algebraic aspects linked to the minimal vertex covers of
a graph G with set of edges E(G). More precisely, starting by the notion
of minimal vertex cover, recent results show that is possible to attach to
graphs the so-called ideals of vertex covers ([9]). There exists a one to one
correspondence between the minimal vertex covers of G and the minimal
prime ideals of I(G). In fact, ℘ is a minimal prime ideal of I(G) if and only
if ℘ = (C), for some minimal vertex cover C of G ([9], Prop. 6.1.16). Hence
ht(I(G)) = α0 (G). Thus the primary decomposition of the edge ideal of G is
given by I(G) = (C1 ) ∩ · · · ∩ (Cp ), where C1 , . . . , Cp are the minimal vertex
covers of G.
Definition 1.2. The ideal of vertex covers of I(G), denoted by Ic (G) , is the
ideal of R generated by all monomials Xi1 · · · Xik such that (Xi1 , . . . , Xik ) is
an associated prime ideal of I(G).

5

Hence Ic (G) = ({Xi1 · · · Xik | {vi1 , . . . , vik } is a vertex cover of G}) and
the minimal generators of Ic (G) correspond to the minimal vertex covers.
Now we study this topic for a wide class of connected graphs and we
show how it is possible to apply the results to the problem related to wireless sensor networks. More precisely, H is the connected graph on n vertices
v1 , . . . , vn consisting of the union of a complete graph Km and star graphs
in the vertices of Km : H = Km ∪ starj (k), where Km is the complete graph
on m vertices v1 , . . . , vm , m < n, and starj (k) is the star graph on k vertices with center vj , for some j = 1, . . . , m, k ≤ n − m. We observe that
V (starj (k)) ∩ V (Km ) = {vj } for j = 1, . . . , m. We denote |E(starj (k))| = ij ,
for j = 1, . . . , m. The edge ideal I(H) ⊂ R = K[X1 , . . . , Xn ] is stated in [6]:
I(H) = (X1 Xm+1 , X1 Xm+2 , . . . , X1 Xm+i1 , X1 X2 , X2 Xm+i1 +1 , X2 Xm+i1 +2 , . . . ,
X2 Xm+i1 +i2 , X2 X3 , X1 X3 , X3 Xm+i1 +i2 +1 , X3 Xm+i1 +i2 +2 , . . . , X3 Xm+i1 +i2 +i3 ,
X3 X4 , X2 X4 , X1 X4 , . . . , Xm Xm+i1 +i2 +···+im−1 +1 , Xm Xm+i1 +i2 +···+im−1 +2 , . . . ,
Xm Xm+i1 +i2 +···+im−1 +im ).
Remark 1.1. I(H) has a linear resolution ([6], Prop 1.1). R. Fröberg proved
that the edge ideal of a simple graph has a linear resolution if and only if its
complementary graph is chordal ([3]; [4], Th. 9.2.3). Hence H is chordal.
In [6] it is given the structure of the ideal of vertex cover of I(H). In
order to describe Ic (H) we rename the vertices of the complete graph Km
vα1 , . . . , vαm , 1 6 α1 < α2 < . . . < αm = n, and α1 = 1 if there is not the
star graph with center vα1 .
The following proposition gives explicitly the generators of the ideals of
vertex covers for the edge ideals I(H) when at least a vertex of Km has degree
m − 1.
Proposition 1.1. ([6], Prop. 2.1)
Let H = Km ∪ starj (k) with n vertices v1 , . . . , vn and Km , m < n, with
vertices vα1 , . . . , vαm , 1 6 α1 < α2 < . . . < αm = n. Let starj (k) be of
the type starα1 (α1 ) on vertices v1 , . . . , vα1 , or starαi (αi − αi−1 ), for some
i = 2, . . . , m. Then Ic (H) has m monomial squarefree generators and it is:
(X1 ··· Xα1 −1 Xα2 ··· Xαm , Xα1 Xα3 ··· Xαm , . . . , Xα1 ··· Xαm−1 ), if i = 1,
or
(Xα2 ··· Xαm , . . . , Xα1 ··· Xαi−1 Xαi−1 +1··· Xαi+1−1 Xαi+1 ··· Xαm , . . . , Xα1 ··· Xαm−1 ),
otherwise.
More in general, it is given the structure of the ideal of vertex covers of
I(H) when all the vertices of Km have degree at least m.

6

Theorem 1.1. ([6], Th. 2.1)
Let H = Km ∪ starj (k) with m star graphs with centers each of the vertices
of Km . The ideal of vertex covers of I(H) has m + 1 monomial squarefree
generators and Ic (H) is
(Xα1 Xα2 ··· Xαm , X1··· Xα1 −1 Xα2 ··· Xαm , Xα1 Xα1 +1··· Xα2 −1 Xα3 ··· Xαm , . . . , Xα1 ·
·· Xαm−2 Xαm−2 +1 ··· Xαm−1 −1 Xαm , Xα1 ··· Xαm−1 Xαm−1 +1 ··· Xαm −1 ) .
The monomial ideal Ic (H) is generated in degree ≥ m. Hence using the
previous results we give the answer to the decision problem of vertex cover :
given the graph H there is a vertex covering of H of minimum cardinality m,
where m is the number of vertices of the complete graph Km . Moreover the
generators of Ic (H) give the structure of each vertex covering of H.
Example 1.1. Let H be the simple graph with V (H) = {v1 , . . . , v11 }
H = K4 ∪ star2 (2) ∪ star6 (4) ∪ star8 (2) ∪ star11 (3).
This graph is the model of a wireless sensor network.

Ic (H) is generated by {X1 X6 X8 X11 , X2 X6 X8 X11 , X2 X6 X7 X11 , X2 X6 X8 X9 X10 ,
X2 X3 X4 X5 X8 X11 }. The minimal vertex covers of H are:
C1 = {v1 , v6 , v8 , v11 }, C2 = {v2 , v6 , v8 , v11 }, C3 = {v2 , v6 , v7 , v11 },
C4 = {v2 , v6 , v8 , v9 , v10 }, C5 = {v2 , v3 , v4 , v5 , v8 , v11 }.
Choose C1 = {v1 , v6 , v8 , v11 } among the three vertex covers with minimum
cardinality. C1 gives the position of the leaders in the sensor network that
H represents:

7

2

Algebraic properties of Ic(H)

The class of monomial ideals Ic (H) is a suitable algebraic model to solve
problems of minimal vertex covers. Moreover Ic (H) is an interesting class of
monomial ideals for its good algebraic properties. In this section we study
some of them.
Let R = K[X1 , . . . , Xn ] be the polynomial ring in n variables over a field K
with deg Xi = 1, for all i = 1, . . . , n. For a monomial ideal I ⊂ R we denote
by G(I) its unique minimal set of monomial generators.
Definition 2.1. A monomial ideal I ⊂ R has linear quotients if there is an
ordering u1 , . . . , ut of monomials belonging to G(I) such that the colon ideal
(u1 , . . . , uj−1) : (uj ) is generated by a subset of {X1 , . . . , Xn }, for 2 6 j 6 t .
For a monomial ideal I of R having linear quotients with respect to the
ordering u1 , . . . , ut of the monomials of G(I), let qj (I) denote the number of
the variables which is required to generate the ideal (u1 , . . . , uj−1) : (uj ).
Set q(I) = max26j6t qj (I). The integer q(I) is independent on the choice of
the ordering of the generators that gives linear quotients ([5]).
Proposition 2.1. Ic (H) has linear quotients.
Proof. 1) If at least a vertex of Km has degree m − 1 (Proposition 1.1), then
Ic (H) has m monomial squarefree generators. We have the following cases:
a) H is formed by the union of a complete graph Km , m < n, with vertices vα1 , . . . , vαm , 1 6 α1 < α2 < . . . < αm = n, and of a star graph
starα1 (α1 ) on vertices v1 , . . . , vα1 . Then we set the following order for the
monomial generators of Ic (H): f1 = Xα1 ··· Xαm−1 , f2 = Xα1 ··· Xαm−2 Xαm ,
. . ., fm−1 = Xα1 Xα3 ··· Xαm , fm = X1 ··· Xα1 −1 Xα2 ··· Xαm .
It results: (f1 ) : (f2 ) = (Xαm−1 ), (f1 , f2 ) : (f3 ) = (Xαm−2 ), . . ., and so on up
to (f1 , . . . , fm−1 ) : (fm ) = (Xα1 ).
b) H is formed by the union of a complete graph Km , m < n, with vertices vα1 , . . . , vαm , 1 6 α1 < α2 < . . . < αm = n, and of a star graph
starαi (αi − αi−1 ), for some i = 2, . . . , m . Then we set the following order for
the monomial generators of Ic (H): f1 = Xα1 ··· Xαm−1 , f2 = Xα1 ··· Xαm−2 Xαm ,
. . ., fm−1 = Xα1 Xα2 ··· Xαm , fm = Xα2 ··· Xαm . Hence: (f1 ) : (f2 ) = (Xαm−1 ),
(f1 , f2 ) : (f3 ) = (Xαm−2 ), . . ., and so on up to (f1 , . . . , fm−1 ) : (fm ) = (Xα1 ).
2) If all the vertices of Km have degree at least m (Theorem 1.1), then we set
the following order for the monomial generators of Ic (H): f1 = Xα1 Xα2···Xαm ,
f2 = Xα1 ··· Xαm−1 Xαm−1 +1··· Xαm −1 , f3 = Xα1 ··· Xαm−2 Xαm−2 +1··· Xαm−1 −1 Xαm ,
. . . , fm = Xα1 Xα1 +1···Xα2 −1 Xα3···Xαm , fm+1 = X1···Xα1 −1 Xα2···Xαm . It results:
(f1 ) : (f2 ) = (Xαm ), (f1 , f2 ) : (f3 ) = (Xαm−1 ), (f1 , f2 , f3 ) : (f4 ) = (Xαm−2 ),
8

. . ., and so on up to (f1 , . . . , fm ) : (fm+1 ) = (Xα1 ).
Hence Ic (H) has linear quotients.
Remark 2.1. If a monomial ideal I of R generated in one degree has linear
quotients, then I has a linear resolution ([2], Lemma 4.1). Ic (H) has linear
quotients, but in general it has not a linear resolution because it is not
generated in the same degree.
Using some properties of the graph H and of its edge ideal I(H) we can
obtain the conditions for which Ic (H) has a linear resolution.
Theorem 2.1. (([6], Th. 1.1)
Let R = K[X1 , . . . , Xn ] and I(H) ⊂ R, H = Km ∪ starj (k). Let |E(starj (k))| =
ij , for j = 1, . . . , m. Then:
1) dimR (R/I(H)) = n − m .
2) pdR (R/I(H)) = m + max16j6m ij − 1 .
3) depthR (R/I(H)) = n − m − max16j6m ij + 1 .
4) regR (R/I(H)) = 1 .
Proposition 2.2. Let I(H) ⊂ R = K[X1 , . . . , Xn ]. I(H) is Cohen Macaulay
if and only if k = 2.
Proof. Let I(H) be the edge ideal of the graph H as described in section 1.
By Theorem 2.1 one has dimR (R/I(H)) = n−m and depthR (R/I(H)) = n−
m−max16j6m ij +1. I(H) is Cohen Macaulay if and only if dimR (R/I(H)) =
depthR (R/I(H)). Hence the equality holds if and only if max16j6m ij = 1.
This is equivalent to say that |E(starj (k))| = 1 for all j = 1, . . . , m, i.e.
starj (k) has k = 2 vertices for all j = 1, . . . , m.
Proposition 2.3. Let H = Km ∪ starj (k). Then Ic (H) has linear resolution
if and only if k = 2.
Proof. I(H) has linear resolution ([6], Prop. 1.1), that is equivalent to say
that the complementary graph of H is chordal ([4], Th. 9.2.3). By Proposition 2.2, k = 2 if and only if I(H) is Cohen-Macaulay. Hence by [9] (Prop.
6.7.15) this is equivalent to say that Ic (H) has linear resolution.
\
(Xi , Xj ).
In general for a graph G one has Ic (G) =
Xi Xj ∈I(G)

i6=j

Hence Ic (G) is an unmixed ideal of height two ([9]). But in general it is
not Cohen-Macaulay. The Cohen-Macaulay property of the ideal Ic (G) was
9

studied in [8]. The notion of chordal graph is used to express this algebraic
property and to study an interesting duality between I(G) and Ic (G) ([3]).
For the class of graphs H starting by some properties of the graph H and of
its edge ideal, we state information about the Cohen-Macaulay property of
Ic (H).
Proposition 2.4. Ic (H) is Cohen-Macaulay.
Proof. I(H) has linear resolution ([6], Prop. 1.1). Hence the complementary
graph H of H is chordal ([4], Th. 9.2.3). This is equivalent to say that Ic (H)
is Cohen-Macaulay ([8]).
The study of the linear quotients is useful in order to investigate algebraic invariants of R/Ic (H): the dimension, dimR (R/Ic (H)), the depth,
depth(R/Ic (H)), the projective dimension, pdR (R/Ic (H)).
Lemma 2.1. Let R = K[X1 , . . . , Xn ] and Ic (H) ⊂ R. Then q(Ic (H)) = 1.
Proof. By the computation of the linear quotients (Proposition 2.1), the
number of the variables which is required to generate the ideal (f1 , . . . , fh−1 ) :
(fh ) is 1, for all h = 1, . . . , t, t ≤ m + 1.
Theorem 2.2. Let R = K[X1 , . . . , Xn ] and Ic (H) ⊂ R. Then:
1) pdR (R/Ic (H)) = 2
2) depthR (R/Ic (H)) = n − 2
3) dimR (R/Ic (H)) = n − 2
4) regR (R/Ic (H)) = max{deg(vαi )} − 1, i = 1, . . . , m.
Proof. 1) The length of the minimal free resolution of R/Ic (H) over R is
equal to q(Ic (H)) + 1 ([5], Corollary 1.6). Then pdR (R/Ic (H)) = 2 .
2) As a consequence of 1), by Auslander-Buchsbaum formula, one has
depthR (R/Ic (H)) = n − pdR (R/Ic (H)) = n − 2.
3) By Proposition 2.4 Ic (H) is Cohen-Macaulay, hence dimR (R/Ic (H)) =
depthR (R/Ic (H)) = n − 2.
4) By [2] (Lemma 4.1) the Castelnuovo-Mumford regularity is regR (R/Ic (H)) =
max{deg(f )| f minimal generator of Ic (H)} − 1. By the structure of generators of Ic (H) it follows that max{deg(f )| f minimal generator of Ic (H)} =
m − 1 − max{deg(vαi )} − (m − 1) = max{deg(vαi )}, i = 1, . . . , m. Hence
regR (R/Ic (H)) = max{deg(vαi )} − 1, i = 1, . . . , m.

10

Example 2.1. Let H = K3 ∪ star1 (2) ∪ star2 (2) ∪ star3 (2) on vertices
{v1 , . . . , v6 }.
R = K[X1 , . . . , X6 ], I(H) = (X1 X2 , X2 X6 , X2 X4 , X4 X6 , X3 X4 , X5 X6 ).
Ic (H) = (X2 X4 X6 , X2 X4 X5 , X2 X3 X6 , X1 X4 X6 ) is generated in the same degree 3. Ic (H) has linear quotients, hence linear resolution:
0 → R3 (−4) → R4 (−3) → R → R/Ic (H) → 0
One has:
1) pdR (R/Ic (H)) = 2 .
2) dimR (R/Ic (H)) = depthR (R/Ic (H)) = 4 .
3) regR (R/Ic (H)) = 2

References
[1] Akyildiz I.F., Su W., Sankarasubramaniam Y., Cayirci E. - Wireless
sensor networks: a survey. Computer Networks 38 (2002), 393-422.
[2] Conca, A., and Herzog, J. - Castelnuovo-Mumford regularity of product
of ideals. Collect. Math. 54 (2003), 137–152.
[3] Fröberg, R. - On Stanley-Reisner rings. Topics in Algebra (1990), 57–70.
[4] Herzog, J., and Hibi, T. - Monomial Ideals. Springer, Graduate Texts
in Mathematics 260 (2011).
[5] Herzog, J., and Takayama, Y. - Resolutions by mapping cones. Homology, Homotopy Appl. 4, 2 (2002), 277–294.
[6] Imbesi, M., and La Barbiera M. - Monomial ideals of graphs with loops.
Anal. Sţiinţ. Univ. Al. I Cuza din Iaşi, Sect. Mat., In press.
[7] La Barbiera M. - On a class of monomial ideals generated by s-sequences.
Math. Reports, 12(62), 3 (2010), 201–216.
[8] Lyubeznik, G. - The minimal non-Cohen-Macaulay monomial ideals. J.
Pure and Applied Algebra, 51 (1988), 261–266.
[9] Villarreal, R.H. - Monomial Algebras. M. Dekker Inc., New York, Pure
and Appl. Math. 238 (2001).

11

