## Abstract

Let G be a connected graph. Given a set S={v_{1},…,v_{k}}⊆V(G), the metric S-representation of a vertex v in G is the vector (d_{G}(v,v_{1}),…,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.

Original language | English |
---|---|

Article number | 112763 |

Journal | Discrete Mathematics |

Volume | 345 |

Issue number | 4 |

DOIs | |

Publication status | Published - Apr 2022 |

## Keywords

- Clique
- Domination
- Fullerene
- Local metric dimension
- Matching
- Triangle-free

## ASJC Scopus subject areas

- Theoretical Computer Science
- Discrete Mathematics and Combinatorics