Critical ideals of signed graphs with twin vertices (Q515809): Difference between revisions
From MaRDI portal
Created a new Item |
Changed an Item |
||
Property / review text | |||
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\). | |||
Property / review text: 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\). / rank | |||
Normal rank | |||
Property / reviewed by | |||
Property / reviewed by: Kuei-Nuan Lin / rank | |||
Normal rank | |||
Property / Mathematics Subject Classification ID | |||
Property / Mathematics Subject Classification ID: 13F20 / rank | |||
Normal rank | |||
Property / Mathematics Subject Classification ID | |||
Property / Mathematics Subject Classification ID: 13P10 / rank | |||
Normal rank | |||
Property / Mathematics Subject Classification ID | |||
Property / Mathematics Subject Classification ID: 05C50 / rank | |||
Normal rank | |||
Property / Mathematics Subject Classification ID | |||
Property / Mathematics Subject Classification ID: 05E99 / rank | |||
Normal rank | |||
Property / zbMATH DE Number | |||
Property / zbMATH DE Number: 6695774 / rank | |||
Normal rank | |||
Property / zbMATH Keywords | |||
critical ideals | |||
Property / zbMATH Keywords: critical ideals / rank | |||
Normal rank | |||
Property / zbMATH Keywords | |||
algebraic co-rank | |||
Property / zbMATH Keywords: algebraic co-rank / rank | |||
Normal rank | |||
Property / zbMATH Keywords | |||
twin vertices | |||
Property / zbMATH Keywords: twin vertices / rank | |||
Normal rank | |||
Property / zbMATH Keywords | |||
replication | |||
Property / zbMATH Keywords: replication / rank | |||
Normal rank | |||
Property / zbMATH Keywords | |||
duplication | |||
Property / zbMATH Keywords: duplication / rank | |||
Normal rank | |||
Property / zbMATH Keywords | |||
critical group | |||
Property / zbMATH Keywords: critical group / rank | |||
Normal rank |
Revision as of 05:06, 1 July 2023
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Critical ideals of signed graphs with twin vertices |
scientific article |
Statements
Critical ideals of signed graphs with twin vertices (English)
0 references
16 March 2017
0 references
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\).
0 references
critical ideals
0 references
algebraic co-rank
0 references
twin vertices
0 references
replication
0 references
duplication
0 references
critical group
0 references