Local metric dimension for graphs with small clique numbers

Let G be a connected graph. Given a set S={v₁,…,v_k}⊆V(G), the metric S-representation of a vertex v in G is the vector (d_G(v,v₁),…,d_G(v,v_k)) where d_G(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 [Formula presented]. 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 [Formula presented]. 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.