Umeå University's logo

umu.sePublications
Change search
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • ieee
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf
A note on locating-dominating sets in twin-free graphs
LIRIS, Université Claude Bernard, CNRS, Lyon 1, France.
LISN, Université Paris-Saclay, France.
Umeå University, Faculty of Science and Technology, Department of Mathematics and Mathematical Statistics.ORCID iD: 0000-0001-8631-4745
LaBRI, Université de Bordeaux, France.
Show others and affiliations
2025 (English)In: Discrete Mathematics, ISSN 0012-365X, E-ISSN 1872-681X, Vol. 348, no 2, article id 114297Article in journal (Refereed) Published
Abstract [en]

In this short note, we prove that every twin-free graph on n vertices contains a locating-dominating set of size at most ⌈[Formula presented]n⌉. This improves the earlier bound of ⌊[Formula presented]n⌋ due to Foucaud, Henning, Löwenstein and Sasse from 2016, and makes some progress towards the well-studied locating-dominating conjecture of Garijo, González and Márquez.

Place, publisher, year, edition, pages
Elsevier, 2025. Vol. 348, no 2, article id 114297
Keywords [en]
Graph partitions, Locating sets, Locating-dominating sets, Twin-free graphs
National Category
Discrete Mathematics
Identifiers
URN: urn:nbn:se:umu:diva-231531DOI: 10.1016/j.disc.2024.114297ISI: 001348586300001Scopus ID: 2-s2.0-85207787370OAI: oai:DiVA.org:umu-231531DiVA, id: diva2:1915106
Available from: 2024-11-21 Created: 2024-11-21 Last updated: 2024-11-21Bibliographically approved

Open Access in DiVA

fulltext(239 kB)86 downloads
File information
File name FULLTEXT01.pdfFile size 239 kBChecksum SHA-512
56ac86825746f504b40017eb4bfca36599e3e33d8a889aecc542d6ae3a8255dc60a571d033ce3b79c7d3008f916c44e82ee18d548315363281d0dc1b8c92acdf
Type fulltextMimetype application/pdf

Other links

Publisher's full textScopus

Authority records

Falgas-Ravry, Victor

Search in DiVA

By author/editor
Falgas-Ravry, Victor
By organisation
Department of Mathematics and Mathematical Statistics
In the same journal
Discrete Mathematics
Discrete Mathematics

Search outside of DiVA

GoogleGoogle Scholar
Total: 87 downloads
The number of downloads is the sum of all downloads of full texts. It may include eg previous versions that are now no longer available

doi
urn-nbn

Altmetric score

doi
urn-nbn
Total: 517 hits
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • ieee
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf