Critical ideals of signed graphs with twin vertices

DOI10.1016/J.AAM.2017.01.005zbMATH Open1391.13036arXiv1504.06257OpenAlexW2963426954MaRDI QIDQ515809FDOQ515809

Hugo Corrales, Carlos A. Alfaro, Carlos Valencia

Publication date: 16 March 2017

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

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.

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

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

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)

Cites Work

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

Cited In (10)

• Title not available (Why is that?)
• A note on the critical ideals of a cycle
• Digraphs with at most one trivial critical ideal
• The structure of sandpile groups of outerplanar graphs
• Graphs with few trivial critical ideals
• Distance ideals of graphs
• Graphs with real algebraic co-rank at most two
• On graphs with 2 trivial distance ideals
• Critical ideals, minimum rank and zero forcing number
• Small clique number graphs with three trivial critical ideals

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)