On the critical ideals of graphs (Q2435580): Difference between revisions

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.