Critical ideals of signed graphs with twin vertices

DOI10.1016/J.AAM.2017.01.005MaRDI QIDQ515809zbMATH OpenOpenAlexFDO

Authors Carlos A. Alfaro, Hugo Corrales, Carlos Valencia

Publication date 16 March 2017

Published in Advances in Applied Mathematics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1504.06257

algebraic co-rank critical group critical ideals duplication replication twin vertices

Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50) Algebraic combinatorics (05E99) Polynomial rings and ideals; rings of integer-valued polynomials (13F20) Gröbner bases; other bases for ideals and modules (e.g., Janet and border bases) (13P10)

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

, let

be the graph obtained from

G

by duplicating

times or replicating

times the vertex

v

when

or

, respectively. Moreover, given

d e l t a i n {0, 1, - 1}^{| V |}

, let [ mathcal{T}_{delta}(G)={G^{�f d}: {�f d}in mathbb{Z}^{|V|} ext{ such that } {�f d}_v=0 ext{ if and only if }delta_v=0 ext{ and } {�f d}_vdelta_v>0 ext{ 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

m a t h c a l T_{d e l t a} (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

m a t h c a l T_{d e l t a} (G)

is equal to the algebraic co-rank of

G^{d e l t a}

. For a large enough

, we show that the critical ideals of

have similar behavior to the critical ideals of the disjoint union of

G

and some set

{K_{n_{v}}}_{v i n V (G) | d_{v} < 0}

of complete graphs and some set

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.

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\).

Recommendations

Cites work

Cited in

(12)

This page was built for publication: Critical ideals of signed graphs with twin vertices

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q515809)