Parameters related to tree-width, zero forcing, and maximum nullity of a graph

DOI10.1002/JGT.21637MaRDI QIDQ4908829zbMATH OpenOpenAlexFDO

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

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

Colin de Verdière type parametermaximum nullityminimum rankminor monotone ceilingminor monotone floorpath-widthtree-widthzero forcing number

Mathematics Subject Classification ID

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

Recommendations

• Zero forcing parameters and minimum rank problems
• A technique for computing the zero forcing number of a graph with a cut-vertex
• On minimum rank and zero forcing sets of a graph
• Zero forcing number, path cover number, and maximum nullity of cacti
• Positive semidefinite zero forcing

Cites work

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

Cited in

(93)

• Computational approaches for zero forcing and related problems
• Some bounds on the zero forcing number of a graph
• Infection in hypergraphs
• Zero forcing number, Grundy domination number, and their variants
• On the total forcing number of a graph
• The zero forcing polynomial of a graph
• 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
• Effects of vertex degrees on the zero-forcing number and propagation time of a graph
• A lower bound on the zero forcing number
• A zero forcing technique for bounding sums of eigenvalue multiplicities
• The Colin de Verdière parameter, excluded minors, and the spectral radius
• Rigid linkages and partial zero forcing
• Total forcing versus total domination in cubic graphs
• Complexity and computation of connected zero forcing
• On the relationships between zero forcing numbers and certain graph coverings
• On the zero forcing number and spectral radius of graphs
• On trees and unicyclic graphs with equal forcing-type numbers
• Total forcing sets and zero forcing sets in trees
• On Grundy total domination number in product graphs
• Grundy domination and zero forcing in regular graphs
• A short proof for a lower bound on the zero forcing number
• Zero forcing in claw-free cubic graphs
• Positive semidefinite zero forcing numbers of two classes of graphs
• A computational comparison of compact MILP formulations for the zero forcing number
• Generalizations of the strong Arnold property and the minimum number of distinct eigenvalues of a graph
• On the Wiener index, distance cospectrality and transmission-regular graphs
• Orthogonal representations of Steiner triple system incidence graphs
• The minimum rank of a sign pattern matrix with a 1-separation
• Zero forcing for sign patterns
• Compressed cliques graphs, clique coverings and positive zero forcing
• Various characterizations of throttling numbers
• Multi-color forcing in graphs
• Some properties of the closed global shadow graphs and their zero forcing number
• Odd cycle zero forcing parameters and the minimum rank of graph blowups
• The complexity of the positive semidefinite zero forcing
• Using a new zero forcing process to guarantee the strong Arnold property
• Fractional zero forcing via three-color forcing games
• Positive semidefinite zero forcing: complexity and lower bounds
• Positive zero forcing and edge clique coverings
• A new lower bound for positive zero forcing
• The forcing number of graphs with given girth
• Graphs with total forcing number two, revisited
• Techniques for determining equality of the maximum nullity and the zero forcing number of a graph
• Computational and Theoretical Challenges for Computing the Minimum Rank of a Graph
• Improved Computational Approaches and Heuristics for Zero Forcing
• How to count k-paths
• Lower bounds for positive semidefinite zero forcing and their applications
• Connected zero forcing sets and connected propagation time of graphs
• Throttling for zero forcing and variants
• Matching, path covers, and total forcing sets
• A note on variants of zero forcing
• Grundy domination and zero forcing in Kneser graphs
• On zero forcing number of graphs and their complements
• On the graph complement conjecture for minimum semidefinite rank
• Finding low-rank solutions of sparse linear matrix inequalities using convex optimization
• Computing the zero forcing number for generalized Petersen graphs
• On the complexity of the positive semidefinite zero forcing number
• 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
• scientific article; zbMATH DE number 7731182 (Why is no real title available?)
• 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
• Uniformly sparse graphs and matrices
• Loop zero forcing and Grundy domination in planar graphs and claw-free cubic graphs
• Bounds on zero forcing using (upper) total domination and minimum degree
• The zero (total) forcing number and covering number of trees
• Spectral arbitrariness for trees fails spectacularly
• The zero forcing number of claw-free cubic graphs
• On the zero forcing number of the complement of graphs with forbidden subgraphs
• Minimal zero forcing sets
• Zero forcing number and propagation time discrepancy of some graphs
• Relationships between minimum rank problem parameters for cobipartite graphs
• The classification of graphs on eight vertices with coinciding zero forcing number and maximum nullity
• The weak version of the graph complement conjecture and partial results for the delta conjecture
• Zero forcing number and maximum nullity of general power graphs
• Probabilistic zero forcing with vertex reversion
• A combinatorial bound on the number of distinct eigenvalues of a graph
• Hopping forcing number in random d-regular graphs
• The extremal results for forcing problem of trees
• New structures and their applications to variants of zero forcing and propagation time
• Exploring the influence of graph operations on zero forcing sets
• Compatible forts and maximum nullity of a graph
• Some results on the total (zero) forcing number of a graph
• Two tree-width-like graph invariants
• On the zero forcing number of trees
• Breadth-first search trees with many or few leaves
• Maximum nullity and zero forcing number on graphs with maximum degree at most three
• Positive semidefinite propagation time

This page was built for publication: Parameters related to tree-width, zero forcing, and maximum nullity of a graph

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