2025/07/18 by Ghalavand, Ali, Li, Xueliang · 1 citation
#Combinatorics (math.CO) #FOS: Mathematics
paper · doi:10.48550/arxiv.2507.13752
Let \( G \) be a graph with order \( n(G) ≥ 5 \), local metric dimension \( diml(G) \), and clique number \( ω(G) \). In this paper, we investigate the local metric dimension of \( K5 \)-free graphs and prove that \( diml(G) ≤ \lfloor(2)/(3)n(G)\rfloor \) when \( ω(G) = 4 \). As a consequence of this finding, along with previous publications, we establish that if \( G \) is a \( K5 \)-free graph, then \( diml(G) ≤ \lfloor(2)/(5)n(G)\rfloor \) when \( ω(G) = 2 \), \( diml(G) ≤ \lfloor(1)/(2)n(G)\rfloor \) when \( ω(G) = 3 \), and \( diml(G) ≤ \lfloor(2)/(3)n(G)\rfloor \) when \( ω(G) = 4 \). Notably, these bounds are sharp for planar graphs. These results for graphs with a clique number less than or equal to 4 provide a positive answer to the conjecture stating that if \( n(G) ≥ ω(G) + 1 ≥ 4 \), then \( diml(G) ≤ ( (ω(G) - 2)/(ω(G) - 1) )n(G) \).