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

threshold graphunimodalityzero forcing polynomialzero forcing set

Mathematics Subject Classification ID

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

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

• 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
• 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?)
• 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 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
• Zero Forcing, Linear and Quantum Controllability for Systems Evolving on Networks

Cited in

(31)

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

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)