Two-connected signed graphs with maximum nullity at most two

DOI10.1016/J.LAA.2020.12.002zbMATH Open1461.05102arXiv1407.2525OpenAlexW3112354382MaRDI QIDQ2228486FDOQ2228486

Frank J. Hall, Hein van der Holst, Marina Arav, Zhongshan Li

Publication date: 17 February 2021

Published in: Linear Algebra and its Applications (Search for Journal in Brave)

Abstract: A signed graph is a pair $(G,Sigma)$, where $G=(V,E)$ is a graph (in which parallel edges are permitted, but loops are not) with $V=1,ldots,n$ and $SigmasubseteqE$. The edges in $Sigma$ are called odd and the other edges of $E$ even. By $S(G,Sigma)$ we denote the set of all symmetric $nimesn$ matrices $A=[a_{i,j}]$ with $a_{i,j}<0$ if $i$ and $j$ are adjacent and connected by only even edges, $a_{i,j}>0$ if $i$ and $j$ are adjacent and connected by only odd edges, $a_{i,j}inmathbbR$ if $i$ and $j$ are connected by both even and odd edges, $a_{i,j}=0$ if $iot=j$ and $i$ and $j$ are non-adjacent, and $a_{i,i}inmathbbR$ for all vertices $i$. The parameters $M(G,Sigma)$ and $xi(G,Sigma)$ of a signed graph $(G,Sigma)$ are the largest nullity of any matrix $AinS(G,Sigma)$ and the largest nullity of any matrix $AinS(G,Sigma)$ that has the Strong Arnold Hypothesis, respectively. In a previous paper, we gave a characterization of signed graphs $(G,Sigma)$ with $M(G,Sigma)leq1$ and of signed graphs with $xi(G,Sigma)leq1$. In this paper, we characterize the $2$-connected signed graphs $(G,Sigma)$ with $M(G,Sigma)leq2$ and the $2$-connected signed graphs $(G,Sigma)$ with $xi(G,Sigma)leq2$.

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

Recommendations

• Signed graphs with stable maximum nullity at most two
• On mesh geometries of root Coxeter orbits and mesh algorithms for corank two edge-bipartite signed graphs
• Signed graphs with maximum nullity two
• Signed graphs whose signed Colin de Verdière parameter is two
• On the inertia set of a signed tree with loops
• Canonical-sign-compatibility of some signed graphs
• On signed graphs with at most two eigenvalues unequal to \(\pm 1\)
• On the multiplicity of \(\alpha\) as an \(A_\alpha(\varGamma)\)-eigenvalue of signed graphs with pendant vertices
• The nullity of bicyclic signed graphs
• Rank decompositions and signed bigraphs

zbMATH Keywords

signed graphsymmetricnullity

Mathematics Subject Classification ID

Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50) Signed and weighted graphs (05C22) Vector spaces, linear dependence, rank, lineability (15A03)

Cites Work

• Signed graphs
• Title not available (Why is that?)
• The inertia set of a signed graph
• The graphs for which the maximum multiplicity of an eigenvalue is two
• A variant on the graph parameters of Colin de Verdiere: Implications to the minimum rank of graphs
• Forbidden minors for the class of graphs \(G\) with \(\xi (G) \leqslant 2\)
• A characterization of tridiagonal matrices

Cited In (5)

• Signed graphs with stable maximum nullity at most two
• The maximum corank of graphs with a 2-separation
• No signed graph with the nullity \(\eta(G,\sigma)=|V(G)|-2m(G)+2c(G)-1\)
• Graphs whose positive semi-definite matrices have nullity at most two
• Signed graphs with maximum nullity two

This page was built for publication: Two-connected signed graphs with maximum nullity at most two

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