The zero forcing polynomial of a graph

DOI10.1016/J.DAM.2018.11.033MaRDI QIDQ1732095zbMATH OpenOpenAlexWikidataFDO

Authors Xianqiang Yang

Publication date 22 March 2019

Published in Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1801.08910

zbMATH Keywords

unimodalitythreshold graphzero forcing setzero forcing polynomial

Mathematics Subject Classification ID

Graph polynomials (05C31) Coloring of graphs and hypergraphs (05C15)

Abstract: Zero forcing is an iterative graph coloring process, where given a set of initially colored vertices, a colored vertex with a single uncolored neighbor causes that neighbor to become colored. A zero forcing set is a set of initially colored vertices which causes the entire graph to eventually become colored. In this paper, we study the counting problem associated with zero forcing. We introduce the zero forcing polynomial of a graph $G$ of order $n$ as the polynomial $mathcalZ(G;x)=su{m}_{i=1}^{n}z(G;i)x^i$, where $z(G;i)$ is the number of zero forcing sets of $G$ of size $i$. We characterize the extremal coefficients of $mathcalZ(G;x)$, derive closed form expressions for the zero forcing polynomials of several families of graphs, and explore various structural properties of $mathcalZ(G;x)$, including multiplicativity, unimodality, and uniqueness.

Recommendations

• Computing the zero forcing number for generalized Petersen graphs
• Zero forcing in claw-free cubic graphs
• The Zero Forcing Number of Graphs
• On trees and unicyclic graphs with equal forcing-type numbers
• Probalistic zero forcing in graphs

Cites work

• scientific article; zbMATH DE number 3598234 (Why is no real title available?)
• scientific article; zbMATH DE number 1229629 (Why is no real title available?)
• scientific article; zbMATH DE number 1295362 (Why is no real title available?)
• A Decomposition for Combinatorial Geometries
• A polynomial invariant for knots via von Neumann algebras
• A technique for computing the zero forcing number of a graph with a cut-vertex
• Characterization of graphs using domination polynomials
• Clique polynomials and independent set polynomials of graphs
• Complexity and computation of connected zero forcing
• Domination in Graphs Applied to Electric Power Networks
• Domination polynomials of \(k\)-tree related graphs
• Dynamic approach to k-forcing
• Fast-mixed searching and related problems on graphs
• Fractional zero forcing via three-color forcing games
• Graph polynomials and their applications. I: The Tutte polynomial
• Graph polynomials and their applications. II: Interrelations and interpretations
• Graph theory with applications
• Introduction to domination polynomial of a graph.
• Irreversible \(k\)-threshold processes: Graph-theoretical threshold models of the spread of disease and of opinion
• Logic circuits from zero forcing
• On dichromatic polynomials
• On the edge cover polynomial of a graph
• On the roots of domination polynomials
• Parameters related to tree-width, zero forcing, and maximum nullity of a graph
• Positive semidefinite propagation time
• Positive semidefinite zero forcing
• Power domination in graphs
• Propagation time for zero forcing on a graph
• Recurrence relations and splitting formulas for the domination polynomial
• The graphs for which the maximum multiplicity of an eigenvalue is two
• The vertex-cover polynomial of a graph
• Throttling positive semidefinite zero forcing propagation time on graphs
• Throttling zero forcing propagation speed on graphs
• Using variants of zero forcing to bound the inertia set of a graph
• Zero Forcing, Linear and Quantum Controllability for Systems Evolving on Networks
• Zero forcing for sign patterns
• Zero forcing parameters and minimum rank problems
• Zero forcing propagation time on oriented graphs
• Zero forcing sets and the minimum rank of graphs

Cited in

(31)

• On the zero forcing number of some Cayley graphs
• Iteration index of a zero forcing set in a graph
• A computational comparison of compact MILP formulations for the zero forcing number
• Blocking zero forcing processes in Cartesian products of graphs
• Almost unimodal and real-rooted graph polynomials
• Zero forcing number of some families of graphs
• Exploring the influence of graph operations on zero forcing sets
• On the error of \textit{a priori} sampling: zero forcing sets and propagation time
• Properties of a \(q\)-analogue of zero forcing
• Beta invariant and chromatic uniqueness of wheels
• Improved Computational Approaches and Heuristics for Zero Forcing
• Computing the zero forcing number for generalized Petersen graphs
• Isomorphisms and properties of TAR graphs for zero forcing and other \(X\)-set parameters
• The Zero Forcing Number of Graphs
• An approximation algorithm for zero forcing
• Zero forcing in claw-free cubic graphs
• On trees and unicyclic graphs with equal forcing-type numbers
• The zero forcing span of a graph
• Multi-color forcing in graphs
• Computational approaches for zero forcing and related problems
• On the zero blocking number of rectangular, cylindrical, and Möbius grids
• Zero forcing with random sets
• Complexity and computation of connected zero forcing
• Some properties of the closed global shadow graphs and their zero forcing number
• Well-forced graphs
• Minimal zero forcing sets
• Zero forcing number of degree splitting graphs and complete degree splitting graphs
• Zero forcing in benzenoid network
• Probalistic zero forcing in graphs
• Reconfiguration graphs of zero forcing sets
• The \(q\)-analogue of zero forcing for certain families of graphs

This page was built for publication: The zero forcing polynomial of a graph

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