Critical ideals of signed graphs with twin vertices

DOI10.1016/J.AAM.2017.01.005MaRDI QIDQ515809zbMATHOpenAlexFDO

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

zbMATH Keywords

replicationcritical groupduplicationalgebraic co-rankcritical idealstwin vertices

Mathematics Subject Classification ID

Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50) 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) Algebraic combinatorics (05E99)

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 $deltain{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 $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 $$, 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}}_{vinV(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.

Recommendations

• On the critical ideals of graphs
• Graphs with two trivial critical ideals
• On the critical ideals of complete multipartite graphs
• Graphs with few trivial critical ideals
• Small clique number graphs with three trivial critical ideals

Cites work

• scientific article; zbMATH DE number 510847 (Why is no real title available?)
• A finite group attached to the laplacian of a graph
• Chip-firing and the critical group of a graph
• Eigenvalue location in cographs
• Graphs with two trivial critical ideals
• On the critical ideals of graphs
• On the sandpile group of dual graphs
• On the sandpile group of the cone of a graph
• Sandpile groups and spanning trees of directed line graphs
• Smith normal form and Laplacians
• The chip-firing game
• The critical group of a clique-inserted graph
• The critical group of a line graph
• The lattice of integral flows and the lattice of integral cuts on a finite graph
• Unimodular equivalence of graphs

Cited in

(11)

• Distance ideals of graphs
• Small clique number graphs with three trivial critical ideals
• A note on the critical ideals of a cycle
• Replication in critical graphs and the persistence of monomial ideals
• The structure of sandpile groups of outerplanar graphs
• On graphs with 2 trivial distance ideals
• Graphs with few trivial critical ideals
• Critical ideals, minimum rank and zero forcing number
• Digraphs with at most one trivial critical ideal
• On the critical ideals of complete multipartite graphs
• Graphs with real algebraic co-rank at most two

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)