Critical ideals of signed graphs with twin vertices

Abstract

This paper studies critical ideals of graphs with twin vertices, which are vertices with the same neighbors. A pair of such vertices are called replicated if they are adjacent, and duplicated, otherwise. Critical ideals of graphs having twin vertices have good properties and show regular patterns. Given a graph $G=(V,E)$ and $\mathbf{d}\in {\mathbb{Z}}^{|V|}$, let $G^{\mathbf{d}}$ be the graph obtained from $G$ by duplicating ${\mathbf{d}}_v$ times or replicating $-{\mathbf{d}}_v$ times the vertex $v$ when ${\mathbf{d}}_v>0$ or ${\mathbf{d}}_v<0$, respectively. Moreover, given $\delta \in \{0,1,-1{\}}^{|V|}$, let \[ \mathcal{T}_δ(G)=\{G^{\bf d}: {\bf d}\in \mathbb{Z}^{|V|} \text{ such that } {\bf d}_v=0 \text{ if and only if }δ_v=0 \text{ and } {\bf d}_vδ_v>0 \text{ otherwise}\} \] be the set of graphs sharing the same pattern of duplication or replication of vertices. More than one half of the critical ideals of a graph in ${\mathcal{T}}_{\delta }(G)$ can be determined by the critical ideals of $G$. The algebraic co-rank of a graph $G$ is the maximum integer $i$ such that the $i$-{\it th} critical ideal of $G$ is trivial. We show that the algebraic co-rank of any graph in ${\mathcal{T}}_{\delta }(G)$ is equal to the algebraic co-rank of $G^{\delta }$. For a large enough $\mathbf{d}\in {\mathbb{Z}}^{V(G)}$, we show that the critical ideals of $G^{\mathbf{d}}$ have similar behavior to the critical ideals of the disjoint union of $G$ and some set $\{K_{n_v}{\}}_{\{v\in V(G)|d_v<0\}}$ of complete graphs and some set $\{T_{n_v}{\}}_{\{v\in V(G)|{\mathbf{d}}_v>0\}}$ of trivial graphs. Additionally, we pose important conjectures on the distribution of the algebraic co-rank of the graphs with twins vertices. These conjectures imply that twin-free graphs have a large algebraic co-rank, meanwhile a graph having small algebraic co-rank has at least one pair of twin vertices.

26 pages, 9 figures. Major changes from the previous version. Accepted in Advanced in Applied Mathematics