Loading...
Loading...

Go to the content (press return)

Locating-dominating sets and identifying codes in Graphs of Girth at least 5

Author
Balbuena, C.; Foucaud, F.; Hansberg, A.
Type of activity
Journal article
Journal
Electronic journal of combinatorics
Date of publication
2015-04-29
Volume
22
Number
2
First page
1
Last page
22
Project funding
Control de invariantes en grafos sujetos a propiedades estructurales
Repository
http://hdl.handle.net/2117/78501 Open in new window
URL
http://www.combinatorics.org/ojs/index.php/eljc/article/view/v22i2p15/pdf Open in new window
Rewarded activity
Yes
Abstract
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 mi...
Citation
Balbuena, C., Foucaud, F., Hansberg, A. Locating-dominating sets and identifying codes in Graphs of Girth at least 5. "Electronic journal of combinatorics", 29 Abril 2015, vol. 22, núm. 2, p. 1-22.
Keywords
BOUNDS, COMPLEXITY, Identifying codes, NUMBER, SYSTEMS, dominating sets, girth, locating-dominating sets, minimum degree, path covers
Group of research
COMBGRAPH - Combinatorics, Graph Theory and Applications

Participants

Attachments