Complexity and computation of connected zero forcing
From MaRDI portal
Publication:2012050
DOI10.1016/J.DAM.2017.05.016zbMATH Open1367.05115arXiv1607.00658OpenAlexW2964164538MaRDI QIDQ2012050FDOQ2012050
Authors: Boris Brimkov, Illya V. Hicks 
Publication date: 27 July 2017
Published in: Discrete Applied Mathematics (Search for Journal in Brave)
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.
Full work available at URL: https://arxiv.org/abs/1607.00658
Recommendations
Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms and problem complexity (68Q25) Coloring of graphs and hypergraphs (05C15) Paths and cycles (05C38) Connectivity (05C40) Graph designs and isomorphic decomposition (05C51)
Cites Work
- Graph theory
- Title not available (Why is that?)
- Zero forcing sets and the minimum rank of graphs
- A note on finding the bridges of a graph
- Connected Domination and Spanning Trees with Many Leaves
- Irreversible \(k\)-threshold processes: Graph-theoretical threshold models of the spread of disease and of opinion
- Computation of minimal rank and path cover number for certain graphs
- Title not available (Why is that?)
- Domination in Graphs Applied to Electric Power Networks
- Vertex and edge spread of zero forcing number, maximum nullity, and minimum rank of a graph
- Parameters related to tree-width, zero forcing, and maximum nullity of a graph
- On minimum rank and zero forcing sets of a graph
- Zero forcing parameters and minimum rank problems
- Positive semidefinite zero forcing
- Power domination in graphs
- Metric Dimension and Zero Forcing Number of Two Families of Line Graphs
- Fractional zero forcing via three-color forcing games
- Proof of a conjecture on the zero forcing number of a graph
- Extremal values and bounds for the zero forcing number
- A technique for computing the zero forcing number of a graph with a cut-vertex
- Propagation time for zero forcing on a graph
- Upper bounds on the \(k\)-forcing number of a graph
- Zero forcing number, constrained matchings and strong structural controllability
- Bounds for the Zero Forcing Number of Graphs with Large Girth
- Dynamic approach to k-forcing
- Zero forcing sets and bipartite circulants
- Positive semidefinite propagation time
- Minimum rank of skew-symmetric matrices described by a graph
- The minimum rank of symmetric matrices described by a graph: a survey
- 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
- Solving connected dominating set faster than \(2^n\)
- Minimum-rank matrices with prescribed graph
- Fast-mixed searching and related problems on graphs
- The price of connectivity for vertex cover
- On the difference between the maximum multiplicity and path cover number for tree-like graphs
- Title not available (Why is that?)
- Power domination in block graphs
- Zero forcing number, path cover number, and maximum nullity of cacti
- On Zero Forcing Number of Permutation Graphs
- Bounds on the connected domination number of a graph
- Title not available (Why is that?)
- Computational approaches for zero forcing and related problems
- Bounds on the connected forcing number of a graph
- Zero forcing and power domination for graph products
- Complexity and algorithms for the connected vertex cover problem in 4-regular graphs
- Logic circuits from zero forcing
- Zero forcing for sign patterns
- Using variants of zero forcing to bound the inertia set of a graph
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
- STACS 2005
- Total forcing versus total domination in cubic graphs
- 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 the Computational Complexity of the Forcing Chromatic Number
- On trees and unicyclic graphs with equal forcing-type numbers
- 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
- The zero forcing number of claw-free cubic graphs
- On the zero blocking number of rectangular, cylindrical, and Möbius grids
- 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)
