Ponencia
Breaking symmetries of graphs with resolving sets
Autor/es | Garijo Royo, Delia
González Herrera, 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 | 2024-05-02 |
Publicado en |
|
Resumen | We undertake a study on the maximum value of the difference between the metric dimension and the determining number of a graph as a function of its order. Our results include lower and upper bounds on that maximum, and ... We undertake a study on the maximum value of the difference between the metric dimension and the determining number of a graph as a function of its order. Our results include lower and upper bounds on that maximum, and exact computations when restricting to some specific families of graphs. Although our technique is mainly based on locating-dominating sets, it also requires very diverse tools and relationships with well-known objects in graph theory; among them: a classical result in graph domination by Ore, a Ramsey-type result by ErdHos and Szekeres, a polynomial time algorithm to compute distinguishing sets and dominating sets of twin-free graphs, k-dominating sets, and matchings. |
Agencias financiadoras | Junta de Andalucía Ministerio de Ciencia, Innovación y Universidades (MICINN). España |
Identificador del proyecto | 2010/FQM-164
2011/FQM-164 EUI- EURC-2011-4306 |
Cita | Garijo Royo, D., González Herrera, A. y Márquez Pérez, A. (2014). Breaking symmetries of graphs with resolving sets. En IX Jornadas de Matemática Discreta y Algorítmica, Tarragona (España). |
Ficheros | Tamaño | Formato | Ver | Descripción |
---|---|---|---|---|
Actas-345-352.pdf | 451.9Kb | [PDF] | Ver/ | |