Presentation
Breaking symmetries of graphs with resolving sets
Author/s | Garijo Royo, Delia
![]() ![]() ![]() ![]() ![]() ![]() ![]() González Herrera, Antonio ![]() ![]() ![]() ![]() ![]() ![]() Márquez Pérez, Alberto ![]() ![]() ![]() ![]() ![]() ![]() ![]() |
Department | Universidad de Sevilla. Departamento de Matemática Aplicada I (ETSII) |
Publication Date | 2014 |
Deposit Date | 2024-05-02 |
Published in |
|
Abstract | 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. |
Funding agencies | Junta de Andalucía Ministerio de Ciencia, Innovación y Universidades (MICINN). España |
Project ID. | 2010/FQM-164
![]() 2011/FQM-164 ![]() EUI- EURC-2011-4306 ![]() |
Citation | 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). |
Files | Size | Format | View | Description |
---|---|---|---|---|
Actas-345-352.pdf | 451.9Kb | ![]() | View/ | |