Edge metric dimensions via hierarchical product and integer linear programming

If S = {v(1),..., v(k)} is an ordered subset of vertices of a connected graph G and e is an edge of G, then the vector r(G)(e vertical bar S) = (d(G)(v(1), e),..., d(G)(v(k), e)) is the edge metric S-representation of e. If the vertices of G have pairwise different edge metric S-representations, then S is an edge metric generator for G. The cardinality of a smallest edge metric generator is the edge metric dimension edim(G) of G. A general sharp upper bound on the edge metric dimension of hierarchical products G(U) Pi H is proved. Exact formula is derived for the case when vertical bar U vertical bar = 1. An integer linear programming model for computing the edge metric dimension is proposed. Several examples are provided which demonstrate how these two methods can be applied to obtain the edge metric dimensions of some applicable graphs.

Automated summary

The paper introduces concepts related to the edge metric generator, edge metric dimension, and edge metric of connected graphs. It analyzes the calculation methods of edge metrics through deriving formulas and proposing integer linear programming models.