Parameters Related to Tree‐Width, Zero Forcing, and Maximum Nullity of a Graph

DOI10.1002/jgt.21637zbMath1259.05112OpenAlexW2101880654MaRDI QIDQ4908829

Francesco Barioli, H. Tracy Hall, Hein van der Holst, Shaun M. Fallat, Pauline van den Driessche, Bryan L. Shader, Leslie Hogben, Wayne W. Barrett

Publication date: 7 March 2013

Published in: Journal of Graph Theory (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1002/jgt.21637

zbMATH Keywords

tree-widthpath-widthminimum rankColin de Verdière type parametermaximum nullityzero forcing numberminor monotone floorminor monotone ceiling

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50) Eigenvalues, singular values, and eigenvectors (15A18) Structural characterization of families of graphs (05C75) Graph minors (05C83) Graph algorithms (graph-theoretic aspects) (05C85) Connectivity (05C40) Vector spaces, linear dependence, rank, lineability (15A03)

Related Items

Throttling for Zero Forcing and Variants ⋮ On the zero forcing number and spectral radius of graphs ⋮ GRAPHS WITH TOTAL FORCING NUMBER TWO, REVISITED ⋮ Generalizations of the strong Arnold property and the minimum number of distinct eigenvalues of a graph ⋮ Computational approaches for zero forcing and related problems ⋮ Positive Semidefinite Zero Forcing: Complexity and Lower Bounds ⋮ Using a new zero forcing process to guarantee the strong Arnold property ⋮ Fractional zero forcing via three-color forcing games ⋮ Compressed cliques graphs, clique coverings and positive zero forcing ⋮ Computational and Theoretical Challenges for Computing the Minimum Rank of a Graph ⋮ On trees and unicyclic graphs with equal forcing-type numbers ⋮ Techniques for determining equality of the maximum nullity and the zero forcing number of a graph ⋮ On the Wiener index, distance cospectrality and transmission-regular graphs ⋮ Various characterizations of throttling numbers ⋮ Multi-color forcing in graphs ⋮ Orthogonal representations of Steiner triple system incidence graphs ⋮ Improved Computational Approaches and Heuristics for Zero Forcing ⋮ Total forcing sets and zero forcing sets in trees ⋮ The Complexity of the Positive Semidefinite Zero Forcing ⋮ Unnamed Item ⋮ Some properties of the closed global shadow graphs and their zero forcing number ⋮ Positive semidefinite propagation time ⋮ Some bounds on the zero forcing number of a graph ⋮ The \(q\)-analogue of zero forcing for certain families of graphs ⋮ On the diameter and zero forcing number of some graph classes in the Johnson, Grassmann and Hamming association scheme ⋮ On graphs maximizing the zero forcing number ⋮ The zero forcing number of graphs with the matching number and the cyclomatic number ⋮ Bounding the total forcing number of graphs ⋮ Sparks of symmetric matrices and their graphs ⋮ Infection in hypergraphs ⋮ Zero forcing number, Grundy domination number, and their variants ⋮ The minimum rank of a sign pattern matrix with a 1-separation ⋮ On Grundy total domination number in product graphs ⋮ Unnamed Item ⋮ Zero forcing for sign patterns ⋮ On the total forcing number of a graph ⋮ Positive Zero Forcing and Edge Clique Coverings ⋮ A New Lower Bound for Positive Zero Forcing ⋮ The zero forcing polynomial of a graph ⋮ A zero forcing technique for bounding sums of eigenvalue multiplicities ⋮ The forcing number of graphs with given girth ⋮ Grundy domination and zero forcing in regular graphs ⋮ Lower bounds for positive semidefinite zero forcing and their applications ⋮ The extremal function and Colin de Verdière graph parameter ⋮ Bounds on the connected forcing number of a graph ⋮ Brushing number and zero-forcing number of graphs and their line graphs ⋮ Total forcing and zero forcing in claw-free cubic graphs ⋮ The Colin de Verdière parameter, excluded minors, and the spectral radius ⋮ Rigid linkages and partial zero forcing ⋮ Finding Low-rank Solutions of Sparse Linear Matrix Inequalities using Convex Optimization ⋮ Total forcing versus total domination in cubic graphs ⋮ On the graph complement conjecture for minimum semidefinite rank ⋮ Complexity and computation of connected zero forcing ⋮ On the relationships between zero forcing numbers and certain graph coverings ⋮ Unnamed Item ⋮ Odd Cycle Zero Forcing Parameters and the Minimum Rank of Graph Blowups ⋮ A short proof for a lower bound on the zero forcing number ⋮ On the complexity of the positive semidefinite zero forcing number ⋮ Effects of vertex degrees on the zero-forcing number and propagation time of a graph ⋮ A lower bound on the zero forcing number ⋮ Connected zero forcing sets and connected propagation time of graphs ⋮ Matching, path covers, and total forcing sets ⋮ Grundy domination and zero forcing in Kneser graphs ⋮ Zero forcing in claw-free cubic graphs ⋮ Positive semidefinite zero forcing numbers of two classes of graphs ⋮ Maximum nullity and zero forcing number on graphs with maximum degree at most three ⋮ A computational comparison of compact MILP formulations for the zero forcing number ⋮ On zero forcing number of graphs and their complements

Cites Work

• Mixed searching and proper-path-width
• Linearly independent vertices and minimum semidefinite rank
• Forbidden minors for the class of graphs \(G\) with \(\xi (G) \leqslant 2\)
• Three-connected graphs whose maximum nullity is at most three
• An upper bound for the minimum rank of a graph
• Zero forcing parameters and minimum rank problems
• The minimum rank of symmetric matrices described by a graph: a survey
• A partial k-arboretum of graphs with bounded treewidth
• Minimal acyclic forbidden minors for the family of graphs with bounded path-width
• Graph searching and a min-max theorem for tree-width
• Graphs whose positive semi-definite matrices have nullity at most two
• Multiplicities of eigenvalues and tree-width of graphs
• A correction: Orthogonal representations and connectivity of graphs
• Orthogonal representations and connectivity of graphs
• Computation of minimal rank and path cover number for certain graphs
• Homomorphiesätze für Graphen
• Minimum-rank matrices with prescribed graph
• On the ?largeur d'arborescence?
• On the minimum rank of not necessarily symmetric matrices: A preliminary study
• The graphs for which the maximum multiplicity of an eigenvalue is two
• The Minor Crossing Number
• Nondiscriminatory propagation on trees
• On the Minimum Rank Among Positive Semidefinite Matrices with a Given Graph
• The maximum multiplicity of an eigenvalue in a matrix whose graph is a tree
• Recontamination does not help to search a graph
• Minimum Degree and Graph Minors
• A variant on the graph parameters of Colin de Verdiere: Implications to the minimum rank of graphs
• Spectral characterization of tree-width-two graphs