The edge metric dimension of the generalized Petersen graph $P(n,3)$ is 4

Abstract

It is known that the problem of computing the edge dimension of a graph is NP-hard, and that the edge dimension of any generalized Petersen graph $P(n,k)$ is at least 3. We prove that the graph $P(n,3)$ has edge dimension 4 for $n\ge 11$, by showing semi-combinatorially the nonexistence of an edge resolving set of order 3 and by constructing explicitly an edge resolving set of order 4.

28 pages, 1 figure, 21 tables