On Zero Forcing Number of Permutation Graphs Conference Paper uri icon

abstract

  • Zero forcing number, Z(G), of a graph G is the minimum cardinality of a set S of black vertices (whereas vertices in 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 : V(G 1) V(G 2) be a permutation. Then a permutation graph G = (V, E) has the vertex set V = V(G 1) V(G 2) and the edge set E = E(G 1) E(G 2) {uv |v = (u)}. It is readily seen that 1 + (G) Z(G ) n, if G is a graph of order n 2; here (G) is the minimum degree of G. We give examples showing that |Z(G) - Z(G )| can be arbitrarily large. Further, we characterize permutation graphs G satisfying Z(G ) = n for a graph G that is a nearly complete graph, a complete k-partite graph, a cycle, and a path, respectively, on n vertices. 2012 Springer-Verlag.

published proceedings

  • Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

author list (cited authors)

  • Yi, E.

citation count

  • 4

complete list of authors

  • Yi, Eunjeong

publication date

  • August 2012