Using a new zero forcing process to guarantee the strong Arnold property

DOI10.1016/J.LAA.2016.06.017MaRDI QIDQ306447zbMATH OpenOpenAlexFDO

Authors Jephian Chin-Hung Lin

Publication date 31 August 2016

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

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

zbMATH Keywords

vertex covermaximum nullityminimum rankSAP zero forcingstrong Arnold propertyColin de Verdière type parameter

Mathematics Subject Classification ID

Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50) Eigenvalues, singular values, and eigenvectors (15A18) Combinatorial aspects of matrices (incidence, Hadamard, etc.) (05B20) Graph minors (05C83) Inverse problems in linear algebra (15A29) Vector spaces, linear dependence, rank, lineability (15A03)

Abstract: The maximum nullity $M(G)$ and the Colin de Verdi`ere type parameter $xi(G)$ both consider the largest possible nullity over matrices in $mathcalS(G)$, which is the family of real symmetric matrices whose $i,j$-entry, $ieqj$, is nonzero if $i$ is adjacent to $j$, and zero otherwise; however, $xi(G)$ restricts to those matrices $A$ in $mathcalS(G)$ with the Strong Arnold Property, which means $X=O$ is the only symmetric matrix that satisfies $AcircX=O$, $IcircX=O$, and $AX=O$. This paper introduces zero forcing parameters $Z_{mathrmSAP}(G)$ and $Z_{mathrmvc}(G)$, and proves that $Z_{mathrmSAP}(G)=0$ implies every matrix $AinmathcalS(G)$ has the Strong Arnold Property and that the inequality $M(G)-Z_{mathrmvc}(G)leqxi(G)$ holds for every graph $G$. Finally, the values of $xi(G)$ are computed for all graphs up to $7$ vertices, establishing $xi(G)=lfloorZfloor(G)$ for these graphs.

Recommendations

• Zero forcing parameters and minimum rank problems
• Techniques for determining equality of the maximum nullity and the zero forcing number of a graph
• On minimum rank and zero forcing sets of a graph
• Positive semidefinite maximum nullity and zero forcing number
• Signed graphs with stable maximum nullity at most two

Cites work

• scientific article; zbMATH DE number 475583 (Why is no real title available?)
• A short proof of the planarity characterization of Colin de Verdière
• 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\)
• Graph theory
• Minimum rank problems
• Multiplicities of eigenvalues and tree-width of graphs
• Odd cycle zero forcing parameters and the minimum rank of graph blowups
• On minimum rank and zero forcing sets of a graph
• Parameters related to tree-width, zero forcing, and maximum nullity of a graph
• Techniques for determining the minimum rank of a small graph
• The Colin de Verdière number and sphere representations of a graph
• The graphs for which the maximum multiplicity of an eigenvalue is two
• The inertia set of a signed graph
• The inverse inertia problem for graphs: Cut vertices, trees, and a counterexample
• The strong Arnold property for 4-connected flat graphs
• Vertex and edge spread of zero forcing number, maximum nullity, and minimum rank of a graph
• Zero forcing parameters and minimum rank problems
• Zero forcing sets and the minimum rank of graphs

Cited in

(5)

• On the strong Arnol'd hypothesis and the connectivity of graphs
• Zero forcing number, Grundy domination number, and their variants
• The strong spectral property for graphs
• The inverse nullity pair problem and the strong nullity interlacing property
• The liberation set in the inverse eigenvalue problem of a graph

This page was built for publication: Using a new zero forcing process to guarantee the strong Arnold property

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