2012/05/31 by Hugo Corrales, Carlos E. Valencia
Computer Science · Mathematics · #Adjacency matrix #Advanced Combinatorial Mathematics #Combinatorics #Digraph #Discrete mathematics #Graph #Graph theory and applications #Laplacian matrix #Mathematics #Topological and Geometric Data Analysis #math.AC #math.CO #msc:05C50 #msc:05E99 #msc:13F20 #msc:13P10
paper · pdf · doi:10.1016/j.laa.2013.10.011
published as Linear Algebra and its Applications 439 (2013) 3870-3892 · 23 pages. Some changes over the previous version. Accepted in Linear algebra and its Applications
arxiv created 2013/10/23 · openalex publication_date 2013/10/28 · arxiv updated 2014/02/21 · openalex created_date 2025/10/10 · openalex updated_date 2026/08/05
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 Grobner 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.