Two-connected signed graphs with maximum nullity at most two

DOI10.1016/J.LAA.2020.12.002MaRDI QIDQ2228486zbMATH OpenOpenAlexFDO

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

Publication date 17 February 2021

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

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

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)

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$.

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

Cites work

• scientific article; zbMATH DE number 1432797 (Why is no real title available?)
• A characterization of tridiagonal matrices
• 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\)
• Signed graphs
• The graphs for which the maximum multiplicity of an eigenvalue is two
• The inertia set of a signed graph

Cited in

(7)

• Graphs whose positive semi-definite matrices have nullity at most two
• Signed graphs with maximum nullity 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\)
• On mesh geometries of root Coxeter orbits and mesh algorithms for corank two edge-bipartite signed graphs
• Signed graphs with stable maximum nullity at most two
• Signed graphs whose signed Colin de Verdière parameter is 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)