Computation of minimal rank and path cover number for certain graphs

DOI10.1016/j.laa.2004.06.019zbMath1052.05045OpenAlexW1988353915MaRDI QIDQ1887507

Leslie Hogben, Francesco Barioli, Shaun M. Fallat

Publication date: 26 November 2004

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

Full work available at URL: https://doi.org/10.1016/j.laa.2004.06.019

zbMATH Keywords

GraphsSymmetric matricesMinimum rankEdge sumPath cover numberVertex sum

Mathematics Subject Classification ID

Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50) Eigenvalues, singular values, and eigenvectors (15A18)

Related Items (44)

Graph reduction techniques and the multiplicity of the Laplacian eigenvalues ⋮ The inverse inertia problem for graphs: Cut vertices, trees, and a counterexample ⋮ Minimum rank problems ⋮ Maximum nullity of outerplanar graphs and the path cover number ⋮ Computational and Theoretical Challenges for Computing the Minimum Rank of a Graph ⋮ Families of graphs with maximum nullity equal to zero forcing number ⋮ Minimum rank and maximum eigenvalue multiplicity of symmetric tree sign patterns ⋮ On the minimum rank of the join of graphs and decomposable graphs ⋮ On the maximum multiplicity of an eigenvalue in a matrix whose graph contains exactly one cycle ⋮ Improved Computational Approaches and Heuristics for Zero Forcing ⋮ Forbidden minors for the class of graphs \(G\) with \(\xi (G) \leqslant 2\) ⋮ Decompositions of minimum rank matrices ⋮ Connected power domination in graphs ⋮ Minimum rank of outerplanar graphs ⋮ Vertex and edge spread of zero forcing number, maximum nullity, and minimum rank of a graph ⋮ Computing inertia sets using atoms ⋮ On the minimum rank of the third power of a starlike tree ⋮ The minimum rank of a sign pattern matrix with a 1-separation ⋮ Orthogonal representations, minimum rank, and graph complements ⋮ The minimum rank of matrices and the equivalence class graph ⋮ On the minimum semidefinite rank of a simple graph ⋮ The inverse eigenvalue problem of a graph: multiplicities and minors ⋮ On acyclic and unicyclic graphs whose minimum rank equals the diameter ⋮ An upper bound for the minimum rank of a graph ⋮ Parameters Related to Tree‐Width, Zero Forcing, and Maximum Nullity of a Graph ⋮ The maximum corank of graphs with a 2-separation ⋮ Zero forcing sets and the minimum rank of graphs ⋮ Minimum rank of skew-symmetric matrices described by a graph ⋮ On minimum rank and zero forcing sets of a graph ⋮ Techniques for determining the minimum rank of a small graph ⋮ Complexity and computation of connected zero forcing ⋮ Zero forcing parameters and minimum rank problems ⋮ A note on universally optimal matrices and field independence of the minimum rank of a graph ⋮ Approximating the minimum rank of a graph via alternating projection ⋮ Odd Cycle Zero Forcing Parameters and the Minimum Rank of Graph Blowups ⋮ Minimum rank and path cover number for generalized and double generalized cycle star graphs ⋮ The minimum rank of symmetric matrices described by a graph: a survey ⋮ The minimum rank problem over the finite field of order 2: Minimum rank 3 ⋮ The graphs for which the maximum multiplicity of an eigenvalue is two ⋮ The maximum multiplicity of the largest \(k\)-th eigenvalue in a matrix whose graph is acyclic or unicyclic ⋮ On the difference between the maximum multiplicity and path cover number for tree-like graphs ⋮ On extremal graphs for zero forcing number ⋮ Fuzzification of Zero Forcing Process ⋮ On the rank spread of graphs

Cites Work

• Spectral multiplicity and splitting results for a class of qualitative matrices
• On the possible multiplicities of the eigenvalues of a Hermitian matrix whose graph is a tree
• A typical vertex of a tree
• On the relative position of multiple eigenvalues in the spectrum of an Hermitian matrix with a given graph
• A characterization of tridiagonal matrices
• Minimum-rank matrices with prescribed graph
• The maximum multiplicity of an eigenvalue in a matrix whose graph is a tree
• On two conjectures regarding an inverse eigenvalue problem for acyclic symmetric matrices
• Graphs whose minimal rank is two
• On the eigenvalues of generalized and double generalized stars
• On the Eigenvalues and Eigenvectors of a Class of Matrices

This page was built for publication: Computation of minimal rank and path cover number for certain graphs