Let G be a connected graph. Given a set S = {v1,..., vk} ⊆ V (G), the metric Srepresentation of a vertex v in G is the vector (dG(v, v1),...,dG(v, vk)) where dG(a,b) is the distance between vertices a and b in G. If every two adjacent vertices of G have different metric S-representations, then the set S is a local metric generator for G. The local metric dimension of G, denoted by dim(G), is the minimum cardinality among all local metric generators of G. The local metric dimension of graphs with large clique numbers is known. Our contribution in this paper is to present upper bounds on the local metric dimension of connected graphs with small clique numbers. We show that there exists a constant C such that if G is a fullerene graph of order n, then dim(G) ≤ min{C, 12 5 n+1}. As a consequence of this result, we show that determining the local metric dimension of fullerene graphs can be done in polynomial time. If G is a connected triangle-free graph of order n, then we show that dim(G) ≤ γ (G), where γ (G) is the domination number of G. As an application of this result, we prove that dim(G) ≤ 25n. If G is a connected graph of order n with clique number 3, then we show that dim(G) ≤ n − α(G), where α(G) is the matching number of G. As an application of this result, we show that for such graphs G we have dim(G) ≤ 23n.

Keywords