For an ordered non-empty subset S = {v1, . . . , vk} of vertices in a connected graph G and an l-clique V of G, the l-clique metric S-representation of V is the vector rl G(V |S) = (dG(V , v1), . . . , dG(V , vk)) where dG(V , vi) = min{dG(v, vi) : v ∈ V }. A non-empty subset S of V (G) is an l-clique metric generator for G if all lcliques of G have pairwise different l-clique metric S-representations. An l-clique metric generator of smallest order is an l-clique metric basis for G, its order being the l-clique metric dimension (l-CMD for short) cdiml(G) of G. In this paper, we propose this concept as an extension of the 1-clique metric dimension which is known as the metric dimension, and also study some its properties. Moreover, l-CMD for (Zn) and the corona product of two graphs is investigated. Furthermore, we prove that computing the l-CMD of connected graphs is NP-hard and present an integer linear programming model for finding this parameter.

Keywords