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

(28)

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