On the complexity of the positive semidefinite zero forcing number

DOI10.1016/J.LAA.2015.03.011MaRDI QIDQ5962481zbMATH OpenOpenAlexFDO

Authors Shaun M. Fallat, K. Meagher, 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

chordal graphsclique cover numbercomputational complexitypositive zero forcing number

Mathematics Subject Classification ID

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

Recommendations

• The complexity of the positive semidefinite zero forcing
• Positive semidefinite zero forcing: complexity and lower bounds
• Positive semidefinite zero forcing
• Lower bounds for positive semidefinite zero forcing and their applications
• Positive semidefinite maximum nullity and zero forcing number
• Positive semidefinite zero forcing numbers of two classes of graphs
• An integer program for positive semidefinite zero forcing in graphs
• A new lower bound for positive zero forcing
• Note on positive semidefinite maximum nullity and positive semidefinite zero forcing number of partial 2-trees
• Complexity and computation of connected zero forcing

Cites work

• Algorithmic Aspects of Vertex Elimination on Graphs
• Fast-mixed searching and related problems on graphs
• scientific article; zbMATH DE number 3859178 (Why is no real title available?)
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 554762 (Why is no real title available?)
• Linearly independent vertices and minimum semidefinite rank
• Monotonicity in graph searching
• Nondiscriminatory propagation on trees
• Note on positive semidefinite maximum nullity and positive semidefinite zero forcing number of partial 2-trees
• On minimum rank and zero forcing sets of a graph
• On the Fast Searching Problem
• On the fractional intersection number of a graph
• On the Minimum Rank Among Positive Semidefinite Matrices with a Given Graph
• Parameters related to tree-width, zero forcing, and maximum nullity of a graph
• Positive semidefinite zero forcing
• Searching and pebbling
• The complexity of searching a graph
• Zero forcing parameters and minimum rank problems
• Zero forcing sets and the minimum rank of graphs

Cited in

(27)

• Some bounds on the zero forcing number of a graph
• Zero forcing number, Grundy domination number, and their variants
• Brushing number and zero-forcing number of graphs and their line graphs
• On the zero forcing number and propagation time of oriented graphs
• On leaky forcing and resilience
• 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
• Positive semidefinite zero forcing
• Compressed cliques graphs, clique coverings and positive zero forcing
• The \((d-2)\)-leaky forcing number of \(Q_d\) and \(\ell\)-leaky forcing number of \(GP(n,1)\)
• The complexity of the positive semidefinite zero forcing
• Failed skew zero forcing on a graph
• Extremal values and bounds for the zero forcing number
• Positive semidefinite zero forcing: complexity and lower bounds
• Positive zero forcing and edge clique coverings
• A new lower bound for positive zero forcing
• Edge forcing in butterfly networks
• Constructions of cospectral graphs with different zero forcing numbers
• Lower bounds for positive semidefinite zero forcing and their applications
• An integer program for positive semidefinite zero forcing in 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 classification of graphs on eight vertices with coinciding zero forcing number and maximum nullity
• Zero forcing of generalized hierarchical products
• On the complexity of failed zero forcing

This page was built for publication: On the complexity of the positive semidefinite zero forcing number

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