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

DOI10.1016/J.LAA.2016.06.017zbMATH Open1343.05094arXiv1601.01341OpenAlexW2962964022MaRDI QIDQ306447FDOQ306447

Authors: Jephian Chin-Hung Lin 

Publication date: 31 August 2016

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

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.

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

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

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)

Cites Work

• Graph theory
• Zero forcing sets and the minimum rank of graphs
• The Colin de Verdière number and sphere representations of a graph
• Multiplicities of eigenvalues and tree-width of graphs
• A short proof of the planarity characterization of Colin de Verdière
• The inertia set of a signed graph
• Odd cycle zero forcing parameters and the minimum rank of graph blowups
• The graphs for which the maximum multiplicity of an eigenvalue is two
• Vertex and edge spread of zero forcing number, maximum nullity, and minimum rank of a graph
• Title not available (Why is that?)
• Parameters related to tree-width, zero forcing, and maximum nullity of a graph
• The strong Arnold property for 4-connected flat graphs
• A variant on the graph parameters of Colin de Verdiere: Implications to the minimum rank of graphs
• The inverse inertia problem for graphs: Cut vertices, trees, and a counterexample
• Minimum rank problems
• Forbidden minors for the class of graphs \(G\) with \(\xi (G) \leqslant 2\)
• On minimum rank and zero forcing sets of a graph
• Techniques for determining the minimum rank of a small graph
• Zero forcing parameters and minimum rank problems

Cited In (5)

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

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)