On the complexity of the positive semidefinite zero forcing number

DOI10.1016/j.laa.2015.03.011zbMath1330.05064OpenAlexW2963481734MaRDI QIDQ5962481

Karen Meagher, Shaun M. Fallat, Boting Yang

Publication date: 12 February 2016

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

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

zbMATH Keywords

computational complexitychordal graphsclique cover numberpositive zero forcing number

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35) Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50) Coloring of graphs and hypergraphs (05C15) Graph labelling (graceful graphs, bandwidth, etc.) (05C78) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items

On the zero forcing number and propagation time of oriented graphs, Positive Semidefinite Zero Forcing: Complexity and Lower Bounds, Failed skew zero forcing on a graph, Extremal values and bounds for the zero forcing number, Compressed cliques graphs, clique coverings and positive zero forcing, An integer program for positive semidefinite zero forcing in graphs, Some bounds on the zero forcing number of a graph, On the diameter and zero forcing number of some graph classes in the Johnson, Grassmann and Hamming association scheme, The \((d-2)\)-leaky forcing number of \(Q_d\) and \(\ell\)-leaky forcing number of \(GP(n,1)\), On graphs maximizing the zero forcing number, Zero forcing number, Grundy domination number, and their variants, Positive Zero Forcing and Edge Clique Coverings, A New Lower Bound for Positive Zero Forcing, Constructions of cospectral graphs with different zero forcing numbers, On leaky forcing and resilience, Lower bounds for positive semidefinite zero forcing and their applications, Brushing number and zero-forcing number of graphs and their line graphs, On the complexity of failed zero forcing, On the zero forcing number of a graph involving some classical parameters, Positive semidefinite zero forcing numbers of two classes of graphs, A computational comparison of compact MILP formulations for the zero forcing number, Power domination throttling, Edge Forcing in Butterfly Networks

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Fast-mixed searching and related problems on graphs
• Linearly independent vertices and minimum semidefinite rank
• On minimum rank and zero forcing sets of a graph
• Zero forcing parameters and minimum rank problems
• On the fractional intersection number of a graph
• Searching and pebbling
• Positive semidefinite zero forcing
• Zero forcing sets and the minimum rank of graphs
• Note on positive semidefinite maximum nullity and positive semidefinite zero forcing number of partial 2-trees
• On the Fast Searching Problem
• Nondiscriminatory propagation on trees
• On the Minimum Rank Among Positive Semidefinite Matrices with a Given Graph
• The complexity of searching a graph
• Monotonicity in graph searching
• Algorithmic Aspects of Vertex Elimination on Graphs
• Parameters Related to Tree‐Width, Zero Forcing, and Maximum Nullity of a Graph