PRIME GRAPHS, MATCHINGS AND THE CASTELNUOVO-MUMFORD REGULARITY

Biyikoglu T., CİVAN Y.

JOURNAL OF COMMUTATIVE ALGEBRA, vol.11, no.1, pp.1-27, 2019 (SCI-Expanded) identifier identifier

  • Publication Type: Article / Article
  • Volume: 11 Issue: 1
  • Publication Date: 2019
  • Doi Number: 10.1216/jca-2019-11-1-1
  • Journal Name: JOURNAL OF COMMUTATIVE ALGEBRA
  • Journal Indexes: Science Citation Index Expanded (SCI-EXPANDED), Scopus
  • Page Numbers: pp.1-27
  • Süleyman Demirel University Affiliated: Yes

Abstract

We demonstrate the effectiveness of prime graphs for the calculation of the (Castelnuovo-Mumford) regularity of graphs. Such a notion allows us to reformulate the regularity as a generalized induced matching problem and perform regularity calculations in specific graph classes, including (C-3; P-5)-free graphs, P-6-free bipartite graphs and all Cohen-Macaulay graphs of girth at least five. In particular, we verify that the five cycle graph C-5 is the unique connected graph satisfying the inequality im(G) < reg(G) = m(G). In addition, we prove that, for each integer n >= 1, there exists a vertex decomposable perfect prime graph G(n) with reg(G(n)) = n.