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
| CREATOR | Ali Ghalavand, Sandi Klavžar, Xueliang Li |
|---|---|
| YEAR | 2024 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 31 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2412-17074