A comparison between the Metric Dimension and Zero Forcing Number of Line Graphs
Linda Eroh, Cong X. Kang, Eunjeong Yi · 2012
The metric dimension dim(G) of a graph G is the minimum number of vertices such that every vertex of G is uniquely determined by its vector of distances to the chosen vertices. The 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 converted entirely to 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”. We investigate the metric dimension and the zero forcing number of line graphs. First, we determine the metric dimension of the line graphs of wheel graphs and bouquet of circles. Second, we determine the zero forcing number of the line graphs of complete graphs, wheel graphs, and bouquet of circles. We prove that Z(G) ≤ 2Z(L(G)) for a simple and connected graph G. Further, we show that Z(G) ≤ Z(L(G)) when G is a tree or when G contains a Hamiltonian path and has a certain number of edges. Finally, we compare the metric dimension with the zero forcing number of a line graph by demonstrating a couple of inequalities between the two parameters. We conclude with some open problems.