Local metric dimension for graphs with small clique numbers

Gholamreza Abrishami, Michael A. Henning, Mostafa Tavakoli

Research output: Contribution to journalArticlepeer-review

7 Citations (Scopus)

Abstract

Let G be a connected graph. Given a set S={v1,…,vk}⊆V(G), the metric S-representation 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 [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 languageEnglish
Article number112763
JournalDiscrete Mathematics
Volume345
Issue number4
DOIs
Publication statusPublished - Apr 2022

Keywords

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

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Discrete Mathematics and Combinatorics

Fingerprint

Dive into the research topics of 'Local metric dimension for graphs with small clique numbers'. Together they form a unique fingerprint.

Cite this