Locating-dominating sets and identifying codes in graphs of girth at least 5 (Q2344817)
From MaRDI portal
!
This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use the normal view instead:
scientific article; zbMATH DE number 6436277
| Language | Label | Description | Also known as |
|---|---|---|---|
| default for all languages | No label defined |
||
| English | Locating-dominating sets and identifying codes in graphs of girth at least 5 |
scientific article; zbMATH DE number 6436277 |
Statements
Locating-dominating sets and identifying codes in graphs of girth at least 5 (English)
0 references
18 May 2015
0 references
Summary: Locating-dominating sets and identifying codes are two closely related notions in the area of separating systems. Roughly speaking, they consist in a dominating set of a graph such that every vertex is uniquely identified by its neighbourhood within the dominating set. In this paper, we study the size of a smallest locating-dominating set or identifying code for graphs of girth at least 5 and of given minimum degree. We use the technique of vertex-disjoint paths to provide upper bounds on the minimum size of such sets, and construct graphs who come close to meeting these bounds.
0 references
identifying codes
0 references
locating-dominating sets
0 references
dominating sets
0 references
path covers
0 references
girth
0 references
minimum degree
0 references
0.8252144455909729
0 references
0.8206573128700256
0 references
0.8175173997879028
0 references
0.8161333799362183
0 references
0.8102250099182129
0 references
