2012/04/10 by Cong X. Kang, Kang, Cong X., Eunjeong Yi +1
Computer Science · Mathematics · #05C38 #05C50 #05D99 #Artificial Intelligence in Games #Combinatorics (math.CO) #Computability, Logic, AI Algorithms #FOS: Mathematics #Mathematical Dynamics and Fractals
paper · pdf · doi:10.48550/arxiv.1204.2238
openalex publication_date 2012/04/10 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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) ∖ S 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 G1 and G2 be disjoint copies of a graph G and let f: V(G1) → V(G2) be a function. Then a functigraph C(G, f)=(V, E) has the vertex set V=V(G1) ∪ V(G2) and the edge set E=E(G1) ∪ E(G2) ∪ \uv | v=f(u)\. For a connected graph G of order n ≥ 3, it is readily seen that 1+δ(G) ≤ Z(C(G, σ)) ≤ n for any permutation σ; we show that 1+ δ(G) ≤ Z(C(G, f)) ≤ 2n-2 for any function f, where δ(G) is the minimum degree of G. We give examples showing that there does not exist a function g such that, for every pair (G,f), Z(G)Z(C(G,f)). We further investigate the zero forcing number of functigraphs on complete graphs, on cycles, and on paths.