On the critical ideals of graphs

Hugo Corrales, Carlos E. Valencia

Research output: Contribution to journalArticlepeer-review

16 Scopus citations


We introduce some determinantal ideals of the generalized Laplacian matrix associated to a digraph G, that we call critical ideals of G. Critical ideals generalize the critical group and the characteristic polynomials of the adjacency and Laplacian matrices of a digraph. The main results of this article are the determination of some minimal generator sets and the reduced Gröbner basis for the critical ideals of the complete graphs, the cycles and the paths. Also, we establish a bound between the number of trivial critical ideals and the stability and clique numbers of a graph.

Original languageEnglish
Pages (from-to)3870-3892
Number of pages23
JournalLinear Algebra and Its Applications
Issue number12
StatePublished - 15 Dec 2013
Externally publishedYes


  • Clique number
  • Complete graph
  • Critical group
  • Critical ideals
  • Cycle
  • Determinantal ideal
  • Generalized Laplacian matrix
  • Gröbner basis
  • Stability number


Dive into the research topics of 'On the critical ideals of graphs'. Together they form a unique fingerprint.

Cite this