TY - JOUR

T1 - Critical ideals of signed graphs with twin vertices

AU - Alfaro, Carlos A.

AU - Corrales, Hugo

AU - Valencia, Carlos E.

PY - 2017/5/1

Y1 - 2017/5/1

N2 - © 2017 Elsevier Inc. 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 d∈Z|V|, let Gd be the graph obtained from G by duplicating dv times or replicating −dv times the vertex v when dv>0 or dv<0, respectively. Moreover, given δ∈{0,1,−1}|V|, let Tδ(G)={Gd:d∈Z|V| such that dv=0Tδ(G)={Gd:if and only if δv=0 and dvδv>0 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 Tδ(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-th critical ideal of G is trivial. We show that the algebraic co-rank of any graph in Tδ(G) is equal to the algebraic co-rank of Gδ. Moreover, the algebraic co-rank can be determined by a simple evaluation of the critical ideals of G. For a large enough d∈ZV(G), we show that the critical ideals of Gd have similar behavior to the critical ideals of the disjoint union of G and some set {Knv}{v∈V(G)|dv<0} of complete graphs and some set {Tnv}{v∈V(G)|dv>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.

AB - © 2017 Elsevier Inc. 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 d∈Z|V|, let Gd be the graph obtained from G by duplicating dv times or replicating −dv times the vertex v when dv>0 or dv<0, respectively. Moreover, given δ∈{0,1,−1}|V|, let Tδ(G)={Gd:d∈Z|V| such that dv=0Tδ(G)={Gd:if and only if δv=0 and dvδv>0 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 Tδ(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-th critical ideal of G is trivial. We show that the algebraic co-rank of any graph in Tδ(G) is equal to the algebraic co-rank of Gδ. Moreover, the algebraic co-rank can be determined by a simple evaluation of the critical ideals of G. For a large enough d∈ZV(G), we show that the critical ideals of Gd have similar behavior to the critical ideals of the disjoint union of G and some set {Knv}{v∈V(G)|dv<0} of complete graphs and some set {Tnv}{v∈V(G)|dv>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.

UR - https://www.scopus.com/inward/record.uri?partnerID=HzOxMe3b&scp=85012257178&origin=inward

UR - https://www.scopus.com/inward/citedby.uri?partnerID=HzOxMe3b&scp=85012257178&origin=inward

U2 - 10.1016/j.aam.2017.01.005

DO - 10.1016/j.aam.2017.01.005

M3 - Article

SP - 99

EP - 131

JO - Advances in Applied Mathematics

JF - Advances in Applied Mathematics

SN - 0196-8858

ER -