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 graph unimodality zero forcing polynomial zero 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

m a t h c a l Z (G; x) = s u 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

m a t h c a l Z (G; x)

, derive closed form expressions for the zero forcing polynomials of several families of graphs, and explore various structural properties of

m a t h c a l Z (G; x)

, including multiplicativity, unimodality, and uniqueness.

Review text

Let $G$ be a graph. If $S \subseteq V(G)$ is a set of initially colored vertices, then the zero forcing color change rule demands that at each timestep, a colored vertex $u$ with a single uncolored neighbor $v$ forces that neighbor to become colored. The closure of $S$ is the set of colored vertices obtained after the color change rule is applied in timesteps until no new vertex can be forced in a timestep. A zero forcing set is a set whose closure is all $V$. In the present paper, the authors introduce the zero forcing polynomial of a graph. \par Definition. Let $G$ be a graph on $n$ vertices and $z(G;i)$ be the number of zero forcing sets of $G$ with cardinality $i$. The zero forcing polynomial of $G$ is defined as \[ \mathcal{Z}(G;x) = \sum_{i=1}^n z(G;i)x^i. \] Obviously, the defined polynomial is related to the zero forcing number of $G$, denoted by $Z(G)$, which is defined as the minimum cardinality of a zero forcing set. \par In the paper, the extremal coefficients of the zero forcing polynomial are firstly studied in Section 3. In the following section, the polynomial is investigated for some specific families of graphs, for example complete graphs, paths, cycles, wheels, and threshold graphs. Finally, in Section 5, various structural properties of the zero forcing polynomial are examined (such as multiplicativity, unimodality, uniqueness). In addition, several families of graphs which can be recognized by their zero forcing polynomials are identified. However, it does not hold in general that if $\mathcal{Z}(G;x) = \mathcal{Z}(H;x)$, then $G \backsimeq H$. In the conclusion, some interesting open problems are also presented. Among them, the following question is included: for any graph $G$ on $n$ vertices, is it true that $z(G;i) \leq z(P_n;i)$, for $1 \leq i \leq n$?

Recommendations

Cites work

Cited in

(31)

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)