Critical ideals of signed graphs with twin vertices (Q515809): Difference between revisions
From MaRDI portal
Created a new Item |
ReferenceBot (talk | contribs) Changed an Item |
||
(5 intermediate revisions by 4 users not shown) | |||
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 | |||
Property / MaRDI profile type | |||
Property / MaRDI profile type: MaRDI publication profile / rank | |||
Normal rank | |||
Property / OpenAlex ID | |||
Property / OpenAlex ID: W2963426954 / rank | |||
Normal rank | |||
Property / arXiv ID | |||
Property / arXiv ID: 1504.06257 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: On the sandpile group of the cone of a graph / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Graphs with two trivial critical ideals / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: The lattice of integral flows and the lattice of integral cuts on a finite graph / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: The critical group of a line graph / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Chip-firing and the critical group of a graph / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: The critical group of a clique-inserted graph / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: On the sandpile group of dual graphs / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: On the critical ideals of graphs / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q4281315 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Eigenvalue location in cographs / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Sandpile groups and spanning trees of directed line graphs / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: A finite group attached to the laplacian of a graph / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Smith normal form and Laplacians / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: The chip-firing game / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Unimodular equivalence of graphs / rank | |||
Normal rank | |||
links / mardi / name | links / mardi / name | ||
Latest revision as of 14:15, 13 July 2024
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