Intertwining local (adjacency) metric dimension with the clique number of a graph

2025/07/18 by Ghalavand, Ali, Klavžar, Sandi, Li, Xueliang
#Combinatorics (math.CO) #FOS: Mathematics

paper · doi:10.48550/arxiv.2507.13777

Abstract

Let G be a simple connected graph with order n(G), local metric dimension \rm dim_l(G), local adjacency metric dimension \rm dim_A,l(G), and clique number ω(G), where G\not≅ K_n(G) and ω(G)≥3. It is proved that \rm dim_A,l(G) ≤ \lfloor ((ω(G) - 2)/(ω(G) - 1))n(G)\rfloor. Consequently, the conjecture asserting that the latter expression is an upper bound for \rm dim_l(G) is confirmed. It is important to note that there are infinitely many graphs that satisfy the equalities.

Citations

• On the local metric dimension of K₅-free graphs
• On the local metric dimension of K₄-free graphs
• Interplay between the local metric dimension and the clique number of a graph
• Nonlocal metric dimension of graphs
• Metric dimension related parameters in graphs: A survey on combinatorial, computational and applied results
• Getting the Lay of the Land in Discrete Space: A Survey of Metric Dimension and its Applications
• Local metric dimension of graphs: generalized hierarchical products and some applications
• The Fractional Local Metric Dimension of Graphs
• The local metric dimension of the lexicographic product of graphs
• The local metric dimension of strong product graphs
• On the adjacency dimension of graphs
• The k-metric dimension of a graph
• On the (adjacency) metric dimension of corona and strong product graphs\n and their local variants: combinatorial and computational results

Related

• Interplay between the local metric dimension and the clique number of a graph
• On the local metric dimension of K₄-free graphs
• On the local metric dimension of K₅-free graphs
• The local metric dimension of the lexicographic product of graphs
• On the (adjacency) metric dimension of corona and strong product graphs\n and their local variants: combinatorial and computational results