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

nullitysigned graphsymmetric

Mathematics Subject Classification ID

Signed and weighted graphs (05C22) Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50) 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$.

Review text

\textit{T. Zaslavsky} [Discrete Appl. Math. 4, 47--74 (1982; Zbl 0476.05080)] introduced signed graphs. Contracting an edge \(e\) with ends \(u\) and \(v\) in a graph \(G\) means deleting \(e\) and identifying the vertices \(u\) and \(v\). 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,\dots,n\}\) and \(\Sigma\subseteq E\). The edges in \(\Sigma\) are called odd and the other edges of \(E\) even. By \(S(G,\Sigma)\) denote the set of all symmetric \(n\times n\) 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}\in R\) if \(i\) and \(j\) are connected by both even and odd edges, \(a_{i,j} = 0\) if \(i = j\) and \(i\) and \(j\) are non-adjacent, and \(a_{i,i}\in R\) 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 \(A\in S(G,\Sigma)\) and the largest nullity of any matrix \(A\in S(G,\Sigma)\) that has the strong Arnold property, respectively. In an earlier paper, the authors [ibid. 439, No. 5, 1506--1529 (2013; Zbl 1282.05058)] gave a characterization of signed graphs \((G,\Sigma)\) with \(M(G,\Sigma)\leq 1\) and of signed graphs with \(\xi(G,\Sigma)\leq 1\). Here, they characterize the 2-connected signed graphs \((G,\Sigma)\) with \(M(G,\Sigma)\leq 2\) and the 2-connected signed graphs \((G,\Sigma)\) with \(\xi(G,\Sigma)\leq 2\). The concept of wide separation is the main frame of the article. This article is useful to researchers working on signed graphs and allied areas.

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 as an A_()-eigenvalue of signed graphs with pendant vertices
• The nullity of bicyclic signed graphs
• Rank decompositions and signed bigraphs

Cites work

• 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 (G) 2
• scientific article; zbMATH DE number 1432797 (Why is no real title available?)
• 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 stable maximum nullity at most two
• On mesh geometries of root Coxeter orbits and mesh algorithms for corank two edge-bipartite signed graphs
• No signed graph with the nullity \(\eta(G,\sigma)=|V(G)|-2m(G)+2c(G)-1\)
• The maximum corank of graphs with a 2-separation
• Signed graphs with maximum nullity 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)