On the critical ideals of graphs
Let \(G\) be a digraph and \(X_G=\{x_u \mid u\in V(G)\}\) the set of variables indexed by the vertices of \(G\). The generalized Laplacian matrix of \(G\) is given by \[ L(G,X)_{u,v}=\begin{cases} x_u, &\text{if }u=v \\ -m_{(u,v)} &\text{otherwise},\end{cases} \] where \(m_{(u,v)}\) is the number of arcs with initial vertex \(u\) and terminal vertex \(v\). The critical ideals of a graph are the determinantal ideals of the generalized Laplacian matrix associated to a graph. More explicitly they are given by \[ I_i(G,X)=\langle \text{minors}_i(L(G,X))\rangle \subseteq P[X_G], \] for all \(1\leq i\leq n\), where \(\text{minors}_i(L(G,X))\) are the minors of \(L(G,X)\) of size \(i\) and \(P[X_G]\) is the polynomial ring over \(P\) on \(X_G\). Moreover, when \(G\) is a simple connected graph, its critical group denoted by \(K(G)\) is given by \[ K(G)\oplus\mathbb{Z}=\mathbb{Z}^V/\text{Im} L(G)^t, \] for more see [\textit{A. M. Duval} et al., Ann. Comb. 17, No. 1, 53--70 (2013; Zbl 1263.05124)] and [\textit{D. J. Lorenzini}, Discrete Math. 91, No. 3, 277--282 (1991; Zbl 0755.05079)]. There is a very close relation between critical groups and their critical ideals. In addition critical ideals of a graph are very useful for understanding and producing information about critical groups. More especially, critical ideals generalize the critical group and the characteristic polynomials of the adjacency and Laplacian matrices of a digraph. In this article the authors are studying the critical ideals of graphs. Firstly, they are giving some useful properties of the critical ideals to connect them with the critical group. They are proving that the critical ideals recover the corresponding critical group of a graph in the case that \(P=\mathbb{Z}\). Next they connect critical ideals with some combinatorics of a graph, such as the stability number and the clique number of a graph \(G\). In a more analytical way, they are studying the critical ideals in the special cases when the graph is either the complete graph \(K_n\) on \(n\) vertices or a cycle \(C_n\) of length \(n\). The authors in their main results are computing the reduced Gröbner basis of \(I_m(K_n,X)\) in the case of complete graph \(K_n\), for the graded lexicographic order. They get a minimal set of generators of the \((n-1)\)-th critical ideal of the cycle \(C_n\). Finally they are computing the reduced Gröbner basis of \(I_{n-1}(C_n,X)\), where the graph \(G\) is a cycle of length \(n\), giving two types of bases, which depend on the case that \(n\) is either odd or even. In the case that \(n\) is odd the reduced Gröbner basis is with respect to any graded lexicographic order while when \(n\) is even is with respect to a graded lexicographic order.
- A finite group attached to the laplacian of a graph
- Arithmetical graphs
- Chromatic number and the 2-rank of a graph
- Critical groups of simplicial complexes
- Graphs with two trivial critical ideals
- scientific article; zbMATH DE number 638938 (Why is no real title available?)
- scientific article; zbMATH DE number 2203240 (Why is no real title available?)
- On the critical ideals of graphs
- Polynomial ideals for sandpiles and their Gröbner bases
- Smith normal form and Laplacians
- Small clique number graphs with three trivial critical ideals
- Graphs with real algebraic co-rank at most two
- Codeterminantal graphs
- On graphs with 2 trivial distance ideals
- Graphs with few trivial characteristic ideals
- Critical ideals, minimum rank and zero forcing number
- Distance ideals of graphs
- Arithmetical structures on graphs
- On the critical ideals of graphs
- Graphs with two trivial critical ideals
- The structure of sandpile groups of outerplanar graphs
- A note on the critical ideals of a cycle
- Arithmetical structures on graphs with connectivity one
- Graphs with few trivial critical ideals
- Tutte short exact sequences of graphs
- On the critical ideals of complete multipartite graphs
- Critical ideals of signed graphs with twin vertices
- Digraphs with at most one trivial critical ideal
- Critical groups of generalized de Bruijn and Kautz graphs and circulant matrices over finite fields
- The critical polynomial of a graph
- Critical ideals of digraphs
- Critical ideals and applications
- The degree-distance and transmission-adjacency matrices
- Distance ideals of digraphs
- Graphs with two trivial distance ideals over the ring of polynomials with integer coefficients
- The critical polynomials of simple connected graphs
- Robust graph ideals
This page was built for publication: On the critical ideals of graphs
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2435580)
