tailieunhanh - An upper bound of regularity of edge ideals

Let G be a simple graph. We give an upper bound for reg I(G) in terms of the induced matching number of its spanning trees. | Trường Đại học Vinh Tạp chí khoa học, Tập 47, Số 1A (2018), tr. 21-26 AN UPPER BOUND OF REGULARITY OF EDGE IDEALS Dao Thi Thanh Ha Vinh University Received on 25/12/2017, accepted for publication on 10/4/2018 Abstract: Let G be a simple graph. We give an upper bound for reg I(G) in terms of the induced matching number of its spanning trees. 1 Introduction Let R = k[x1 , . . . , xn ] be a polynomial ring over a field k. Let G be a simple graph with vertex set V (G) = {1, . . . , n} and edge set E(G). One associate to G a quadratic square-free monomial ideal I(G) = (xi xj | {i, j} ∈ E(G)) in R, which is called the edge ideal of G. The Castelnuovo-Mumford regularity (or regularity for short) of an edge ideal of a finite simple graph has been studied in many articles including [1, 2, 4, 8, 10, 11, 12]. A set M ⊆ E(G) is a matching of G if two different edges in M are disjoint; and the matching number of G, denoted by ν(G), is defined by ν(G) := max{|M| | M is a matching of G}. A set M = {a1 b1 , . . . , ar br } ⊆ E(G) is an induced matching of G if the induced subgraph of G on the vertex set {a1 , b1 , . . . , ar , br } consists of just r disjoint edges; and the induced matching number of G, denoted by ν0 (G), is defined by ν0 (G) := max{|M| | M is an induced matching of G}. Then, the basic inequalities that relate reg I(G) to the matching number and the induced matching number of G are ν0 (G) + 1 6 reg I(G) 6 ν(G) + 1, where the first inequality is proved by Katzman [10] and the second one is proved by Hà and Van Tuyl [8]. The aim of this paper is to give another upper bound of reg I(G) in terms of spanning trees of G. This result is an improvement of the second inequality above. Recall that a 1) Email: thahanh@ 21 Dao Thi Thanh Ha/ An upper bound of regularity of edge ideals spanning tree T of a connected graph G is a subgraph of G that is a tree which includes all of the vertices of G. The main result of the paper is the following .