{
  "id": "2405.18162",
  "version": "v1",
  "published": "2024-05-28T13:24:07.000Z",
  "updated": "2024-05-28T13:24:07.000Z",
  "title": "A note on locating sets in twin-free graphs",
  "authors": [
    "Nicolas Bousquet",
    "Quentin Chuet",
    "Victor Falgas-Ravry",
    "Amaury Jacques",
    "Laure Morelle"
  ],
  "comment": "5 pages, 1 figure",
  "categories": [
    "math.CO"
  ],
  "abstract": "In this short note, we prove that every twin-free graph on $n$ vertices contains a locating-dominating set of size at most $\\lceil\\frac{5}{8}n\\rceil$. This improves the earlier bound of $\\lfloor\\frac{2}{3}n\\rfloor$ due to Foucaud, Henning, L\\\"owenstein and Sasse from 2016, and makes some progress towards the well-studied locating-dominating conjecture of Garijo, Gonz\\'alez and M\\'arquez.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2024-05-28T13:24:07.000Z"
    }
  ],
  "analyses": {
    "subjects": [
      "05C69",
      "G.2.2",
      "F.2.2"
    ],
    "keywords": [
      "twin-free graph",
      "locating sets",
      "short note",
      "vertices contains",
      "earlier bound"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 5,
      "language": "en",
      "license": "arXiv",
      "status": "editable"
    }
  }
}