Critical ideals of signed graphs with twin vertices (Q515809): Difference between revisions

Given a multidigraph \(G\) and a vertex \(v\in V(G)\), duplicating the vertex \(v\) consists in adding a new vertex \(v^{1}\) to \(V(G)\) and making it adjacent to each neighbor of \(v\), respecting the multiplicities and signs of arcs. Let \(d(G,v)\) denote the multidigraph obtained from \(G\) after duplicating the vertex \(v\). Similarly, replicating the vertex \(v\) consists in duplicating \(v\) and adding the arcs \(vv^{1}\) and \(v^{1}v\). Let \(r(G,v)\) denote the multidigraph obtained from \(G\) by replicating the vertex \(v\). Two vertices \(u\) and \(v\) are called twins if they have the same neighborhood. A signed multidigraph \(G_{\sigma}\) is a pair that consists of multidigraph \(G\) and a function \(\sigma\), called the sign, from the arcs of \(G\) into the set \(\{1,-1\}\). Given a set of variables \(X_{G}=\{x_{u}:u\in V(G)\}\) indexed by the vertices of \(G\) and a principal ideal domain (PID) \(\mathcal{P}\), the generalized Laplacian matrix \(L(G_{\sigma},X_{G})\) of \(G_{\sigma}\) is the matrix whose entries are given by \[ L(G_{\sigma},X_{G})_{uv}=\begin{cases} x_{u} & \text{if }u=v,\\ -\sigma(uv)m_{uv}1_{\mathcal{P}} & \text{otherwise,} \end{cases} \] where \(m_{uv}\) is the number of arcs leaving \(u\) and entering \(v\), and \(1_{\mathcal{P}}\) is the identity of \(\mathcal{P}\). Moreover, if \(\mathcal{P}[X_{G}]\) is the polynomial ring over \(\mathcal{P}\) in the variables \(X_{G}\), then the critical ideals of \(G_{\sigma}\) are the determinantal ideals given by \[ I_{i}(G_{\sigma},X_{G})=<\{\text{det}(m):m\text{ is an }i\times i\text{ submatrix of }L(G_{\sigma},X_{G})\}>\subseteq\mathcal{P}[X_{G}], \] for all \(1\leq i\leq|V(G)|\). The main goal of this article is to give a description of the critical ideals of signed multidigraphs with twin vertices. More precisely, given a graph \(G\) and \(\delta\in\{0,1,-1\}^{|V|}\), let \[ \mathcal{T}_{\delta}(G)=\{G^{\mathbf{d}}:\mathbf{d}\in\mathbb{Z}^{|V|}\text{ such that supp}(\mathbf{d})=\delta\}, \] where \[ \text{supp}(\mathbf{d})_{v}=\begin{cases} -1 & \text{if }\mathbf{d}_{v}<0,\\ 1 & \text{if }\mathbf{d}_{v}>0,\\ 0 & \text{otherwise.} \end{cases} \] The authors prove that more than one half of the critical ideals of the graphs in \(\mathcal{T}_{\delta}(G)\) are determined by the critical ideals of \(G\), see Theorems 3.4 and 3.8. Moreover, the algebraic co-rank of any graph in \(\mathcal{T}_{\delta}(G)\) is equal to the algebraic co-rank of \(G^{\delta}\) (see Corollary 2.9), which is less than or equal to the number of vertices of \(G\) and is determined by a simple evaluation of the critical ideals of \(G\).