Artículo
Resolving sets for breaking symmetries of graphs
Autor/es | Garijo Royo, Delia
González, Antonio Márquez Pérez, Alberto |
Departamento | Universidad de Sevilla. Departamento de Matemática Aplicada I (ETSII) |
Fecha de publicación | 2014 |
Fecha de depósito | 2021-06-16 |
Publicado en |
|
Resumen | This paper deals with the maximum value of the difference between the determining
number and the metric dimension of a graph as a function of its order. Our technique
requires to use locating-dominating sets, and perform ... This paper deals with the maximum value of the difference between the determining number and the metric dimension of a graph as a function of its order. Our technique requires to use locating-dominating sets, and perform an independent study on other functions related to these sets. Thus, we obtain lower and upper bounds on all these functions by means of very diverse tools. Among them are some adequate constructions of graphs, a variant of a classical result in graph domination and a polynomial time algorithm that produces both distinguishing sets and determining sets. Further, we consider specific families of graphs where the restrictions of these functions can be computed. To this end, we utilize two well-known objects in graph theory: k-dominating sets and matchings. |
Cita | Garijo Royo, D., González, A. y Márquez Pérez, A. (2014). Resolving sets for breaking symmetries of graphs. ArXiv.org, arXiv:1401.3686 |
Ficheros | Tamaño | Formato | Ver | Descripción |
---|---|---|---|---|
Resolving sets for breaking ... | 344.8Kb | [PDF] | Ver/ | |