Mathematics – Combinatorics
Scientific paper
2012-04-10
Mathematics
Combinatorics
15 pages, 11 figures
Scientific paper
\emph{Zero forcing number}, $Z(G)$, of a graph $G$ is the minimum cardinality of a set $S$ of black vertices (whereas vertices in $V(G)\setminusS$ are colored white) such that $V(G)$ is turned black after finitely many applications of "the color-change rule": a white vertex is converted black if it is the only white neighbor of a black vertex. Zero forcing number was introduced and used to bound the minimum rank of graphs by the "AIM Minimum Rank - Special Graphs Work Group". Let $G_1$ and $G_2$ be disjoint copies of a graph $G$ and let $f: V(G_1) \rightarrow V(G_2)$ be a function. Then a \emph{functigraph} $C(G, f)=(V, E)$ has the vertex set $V=V(G_1) \cup V(G_2)$ and the edge set $E=E(G_1) \cup E(G_2) \cup \{uv \mid v=f(u)\}$. For a graph $G$ of order $n \ge 3$, it is readily seen that $1+\delta(G) \le Z(C(G, \sigma)) \le n$ for any one-to-one function $\sigma$; we show that $1+ \delta(G) \le Z(C(G, f)) \le 2n-2$ for any function $f$, where $\delta(G)$ is the minimum degree of $G$. We give examples showing that $|Z(G)-Z(C(G,f))|$ can be arbitrarily large. We further investigate the zero forcing number of functigraphs on complete graphs, on cycles, and on paths. We also characterize permutation graphs $C(G, \sigma)$ for which the zero forcing number equals $1+ \delta(G)$ or $n$, respectively, when $G$ is a complete graph, a cycle, or a path on $n$ vertices.
No associations
LandOfFree
On Zero Forcing Number of Functigraphs does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with On Zero Forcing Number of Functigraphs, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and On Zero Forcing Number of Functigraphs will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-645945