zbMATH — the first resource for mathematics

Metric dimension and zero forcing number of two families of line graphs. (English) Zbl 1340.05057
The relationships between the metric dimension and the zero forcing number of graphs have been studied by many authors. There are examples of graphs whose metric dimension is more than the zero forcing number and vice versa. In this context studying the relationships between these two parameters is an interesting problem. In this paper, the authors investigate the metric dimension and the zero forcing number of some line graphs. They also determine the metric dimension and the zero forcing number of the line graphs of wheel graphs and the bouquet of circles. They prove that $$Z(G) \leq 2Z(L(G))$$ for a simple and connected graph $$G$$. Further, the authors prove that $$Z(G) \leq Z(L(G))$$ when $$G$$ is a tree or when $$G$$ contains a Hamiltonian path and has a certain number of edges. They compare the metric dimension with the zero forcing number of a line graph by demonstrating a couple of inequalities between the two parameters. Finally, the authors pose a conjecture that $$\dim(L(G))\leq Z(L(G))$$ for any $$G$$.

MSC:
 05C12 Distance in graphs 05C50 Graphs and linear algebra (matrices, eigenvalues, etc.) 05C38 Paths and cycles 05C05 Trees 05C76 Graph operations (line graphs, products, etc.) 05C45 Eulerian and Hamiltonian graphs
Full Text: