Regularity, matchings and Cameron-Walker graphs

Let \(G\) be a graph with vertex set \(\{1,\dots,n\}\), let \(k[x_1,\dots,x_n]\) be a polynomial ring over a field \(k\) and denote by \(I(G)\subset k[x_1,\dots,x_n]\) the edge ideal of \(G\). This article gives a characterization of the graphs for which the Castelnuovo--Mumford regularity of \(I(G)\) coincides with the matching number of \(G\) plus \(1\). The starting point for this investigation is: \[ \nu(G) \leq \operatorname{reg} K[x_1,\dots,x_n]/I(G) \leq \beta(G), \] where, in the notation of the article, \(\beta(G)\) denotes the matching number of \(G\) and \(\nu(G)\) the induced matching number of \(G\). The lower bound was obtained by \textit{M. Katzman} [J. Comb. Theory, Ser. A 113, No. 3, 435--454 (2006; Zbl 1102.13024)] and the upper bound by \textit{H. T. Hà} and \textit{A. Van Tuyl} [J. Algebr. Comb. 27, No. 2, 215--245 (2008; Zbl 1147.05051)]. The upper bound has been improved by \textit{R. Woodroofe} [J. Commut. Algebra 6, No. 2, 287--304 (2014; Zbl 1330.13040)]. Graphs with \(\nu(G)=\beta(G)\) are called Cameron-Walker graphs and have been classified in [\textit{K. Cameron} and \textit{T. Walker}, Discrete Math. 299, No. 1--3, 49--55 (2005; Zbl 1073.05054)] and also in [\textit{T. Hibi} et al., J. Algebra 422, 257--269 (2015; Zbl 1303.05218)]. It is known that \(\operatorname{reg} K[x_1,\dots,x_n]/I(G)\) is additive on the connected components of \(G\). The author shows that if \(G\) is connected and \(\operatorname{reg} I(G) = \beta(G)+1\) then either \(G\) is cycle of length \(5\) or \(G\) is a Cameron-Walker graph.

Recommendations

Cites work

Cited in

(23)

Describes a project that uses

Uses Software

Macaulay2

This page was built for publication: Regularity, matchings and Cameron-Walker graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2301245)