Interplay between the local metric dimension and the clique number of a graph

Ali Ghalavand, Sandi Klavžar, Xueliang Li · 2024

Read Interplay between the local metric dimension and the clique number of a graph by Ali Ghalavand, Sandi Klavžar, Xueliang Li (2024) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2412-17074.txt.

Description

Ali Ghalavand, Sandi Klavžar, and Xueliang Li study how two graph measures constrain each other, in a paper published in two thousand twenty-four. One measure is the local metric dimension, the smallest set of landmarks that lets nearby vertices be told apart by their distances. The other is the clique number, the size of the largest fully linked group.

The authors prove that when the clique number falls short of the vertex count by at least three, the local metric dimension is also capped. They classify the graphs that reach that cap exactly. For graphs whose clique number sits just two below the vertex count, they pin the dimension to one of two values and sort all such graphs by which one applies. A broad conjectured bound is proved for the largest clique cases. One question about flat, planar graphs gets a negative answer.

Catalog record

CREATORAli Ghalavand, Sandi Klavžar, Xueliang Li
YEAR2024
COLLECTIONPAPERS
FORMATTXT
FILE SIZE31 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2412-17074

Browse the full library · About the Tower of Babel