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

Colin de Verdière type parametermaximum nullityminimum rankSAP zero forcingstrong Arnold propertyvertex cover

Mathematics Subject Classification ID

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

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

• 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 (G) 2
• Graph theory
• scientific article; zbMATH DE number 475583 (Why is no real title available?)
• 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)

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

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)