Complexity and computation of connected zero forcing
From MaRDI portal
Publication:2012050
Abstract: Zero forcing is an iterative graph coloring process whereby a colored vertex with a single uncolored neighbor forces that neighbor to be colored. It is NP-hard to find a minimum zero forcing set - a smallest set of initially colored vertices which forces the entire graph to be colored. We show that the problem remains NP-hard when the initially colored set induces a connected subgraph. We also give structural results about the connected zero forcing sets of a graph related to the graph's density, separating sets, and certain induced subgraphs, and we characterize the cardinality of the minimum connected zero forcing sets of unicyclic graphs and variants of cactus and block graphs. Finally, we identify several families of graphs whose connected zero forcing sets define greedoids and matroids.
Recommendations
Cites work
- scientific article; zbMATH DE number 3702724 (Why is no real title available?)
- scientific article; zbMATH DE number 3465355 (Why is no real title available?)
- scientific article; zbMATH DE number 3467157 (Why is no real title available?)
- scientific article; zbMATH DE number 3639144 (Why is no real title available?)
- A note on finding the bridges of a graph
- A technique for computing the zero forcing number of a graph with a cut-vertex
- Bounds for the Zero Forcing Number of Graphs with Large Girth
- Bounds on the connected domination number of a graph
- Bounds on the connected forcing number of a graph
- Complexity and algorithms for the connected vertex cover problem in 4-regular graphs
- Computation of minimal rank and path cover number for certain graphs
- Computational approaches for zero forcing and related problems
- Connected Domination and Spanning Trees with Many Leaves
- Domination in Graphs Applied to Electric Power Networks
- Dynamic approach to k-forcing
- Extremal values and bounds for the zero forcing number
- Fast-mixed searching and related problems on graphs
- Fractional zero forcing via three-color forcing games
- Graph theory
- Irreversible \(k\)-threshold processes: Graph-theoretical threshold models of the spread of disease and of opinion
- Logic circuits from zero forcing
- Metric Dimension and Zero Forcing Number of Two Families of Line Graphs
- Minimum rank of skew-symmetric matrices described by a graph
- Minimum-rank matrices with prescribed graph
- On Zero Forcing Number of Permutation Graphs
- On minimum rank and zero forcing sets of a graph
- On the difference between the maximum multiplicity and path cover number for tree-like graphs
- Parameters related to tree-width, zero forcing, and maximum nullity of a graph
- Positive semidefinite propagation time
- Positive semidefinite zero forcing
- Power domination in block graphs
- Power domination in graphs
- Proof of a conjecture on the zero forcing number of a graph
- Propagation time for zero forcing on a graph
- Solving connected dominating set faster than \(2^n\)
- Solving the connected dominating set problem and power dominating set problem by integer programming
- Spanning trees and the complexity of flood-filling games
- 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 price of connectivity for vertex cover
- Upper bounds on the \(k\)-forcing number of a graph
- Using variants of zero forcing to bound the inertia set of a graph
- Vertex and edge spread of zero forcing number, maximum nullity, and minimum rank of a graph
- Zero forcing and power domination for graph products
- Zero forcing for sign patterns
- Zero forcing number, constrained matchings and strong structural controllability
- Zero forcing number, path cover number, and maximum nullity of cacti
- Zero forcing parameters and minimum rank problems
- Zero forcing sets and bipartite circulants
- Zero forcing sets and the minimum rank of graphs
Cited in
(29)- Probabilistic zero forcing on random graphs
- A computational comparison of compact MILP formulations for the zero forcing number
- Blocking zero forcing processes in Cartesian products of graphs
- The zero forcing polynomial of a graph
- On the zero forcing number of a graph involving some classical parameters
- Connected power domination in graphs
- Total forcing versus total domination in cubic graphs
- STACS 2005
- On the semitotal forcing number of a graph
- Zero forcing versus domination in cubic graphs
- Logic circuits from zero forcing
- Total forcing sets and zero forcing sets in trees
- Zero forcing in claw-free cubic graphs
- On trees and unicyclic graphs with equal forcing-type numbers
- On the Computational Complexity of the Forcing Chromatic Number
- Bounding the total forcing number of graphs
- Graphs with total forcing number two, revisited
- On the complexity of failed zero forcing
- Computational approaches for zero forcing and related problems
- On the complexity of the positive semidefinite zero forcing number
- On the zero blocking number of rectangular, cylindrical, and Möbius grids
- The zero forcing number of claw-free cubic graphs
- Tight bounds on probabilistic zero forcing on hypercubes and grids
- On extremal graphs for zero forcing number
- Power domination throttling
- On the total forcing number of a graph
- Matching, path covers, and total forcing sets
- On the diameter and zero forcing number of some graph classes in the Johnson, Grassmann and Hamming association scheme
- Edge forcing in butterfly networks
This page was built for publication: Complexity and computation of connected zero forcing
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2012050)
