Resumen de Destrucción de simetrías y resolubilidad en grafos
This work is devoted to the study of the main methods in symmetry breaking and resolvability in graphs, namely the determining sets and the resolving sets, with a special interest in the extremal values of the sizes of those sets, the determining number and the metric dimension. However, in order to fulfill our task we study some other parameters related to those sets.
First, we consider the problem of computing the determining number and the metric dimension of specific families of graphs, namely Johnson graphs and Kneser graphs. The reason for considering these families is due to the fact that they produce surprising connections between areas in mathematics which are apparently disconnected. Indeed, we construct determining sets and resolving sets of these graphs from various algebraic, combinatorial and geometric objects; among them: regular hypergraphs, Hadamard designs, Steiner systems, partial geometries and toroidal grids.
From all these connections we obtain a variety of results on the determining number and the metric dimension of Johnson graphs and Kneser graphs that extend the studies started by Boutin [2] and Bailey and Cameron [1]. For the determining number, we design a technique based on hypergraphs for computing this parameter in a wide range of Johnson graphs and Kneser graphs. Also, this technique allows us to characterize some subfamilies of these graphs, one of them answering an open question posed by Boutin in [2]. On the other hand, our constructions of resolving sets of Johnson graphs and Kneser graphs lead us to a number of upper bounds on the metric dimension of these graphs. Note that this is a significant extension of the results obtained by Bailey and Cameron [1] since they study only a very particular subfamily of these graphs.
The next part of this work is concerned with the number of resolving sets of a graph, which implies a different point of view since, so far, we have just considered the problem of minimize the size of these sets. To do this, we deal with two resolving parameters, the upper dimension and the resolving number, that combined with the metric dimension give an insight of how large the set of resolving sets of a graph is. Thus, we study together these three parameters obtaining significant results such as the resolution of a conjecture posed by Chartrand et al. [5] which claims that every pair of integers a, b with 1ab+1 is realizable as the metric dimension and the upper dimension of some graph. Also, we solve the problem, proposed by Chartrand and Zhang [6], of characterizing the graphs with equal metric dimension and resolving number.
In order to extend the results obtained in [5] and [6], we develop a study on the resolving number that begins with a formula to compute this parameter that is based on the distance distribution of a graph. As a first consequence of that formula, we show an important difference between resolving number and metric dimension: while the resolving number of an arbitrary graph can be computed in polynomial time, the metric dimension is an NP-hard problem [8]. Also, our formula leads to some upper bounds on various graph parameters in terms of the resolving number, characterizing some extremal cases; for example, the graphs with equal resolving number and clique number.
As an application of all those relations we prove another fundamental difference between metric dimension and resolving number: the set of graphs with fixed resolving number c3 is finite, contrary to the fact that every a>0 is realizable as the metric dimension of infinitely many graphs. On the other hand, we also utilize those relations to determine all graphs with resolving number 1, 2 and 3, thereby initiating a study which has been already considered for the metric dimension [4, 7].
In the last part of this work, we study together determining sets and resolving sets since to combine symmetries with distances may provide much information on the graph. Concretely, we deal with the problem proposed by Boutin [2] about the maximum value of the difference between these two parameters. Thus, we regard this maximum as a function of the order, as well as we require the use of similar functions for which we develop independent studies. It is worth mentioning that our results about these functions are obtained by means of very interesting connections that we establish between combinatorial objects which are apparently unrelated; among them: dominating sets, cliques and independent sets of vertices.
Our results on those functions contain bounds that improve the results provided by Cáceres et al. [3] on the problem posed by Boutin [2]. Thus, we first provide some constructions of graphs which lead to a lower bound on the maximum value of the difference between the determining number and the metric dimension. Subsequently, we develop a complex machinery of technical lemmas which enable us to obtain upper bounds for this maximum by means of very diverse methods; among them: the design of a polinomial time algorithm, and relationships between certain domination parameters and classical graph invariants such as the clique number and the chromatic number.
Cáceres et al. [3] study the maximum value of the difference between the determining number and the metric dimension of a tree (which is a restriction of the problem proposed by Boutin [2]). To solve this problem, we utilize a technique which uses two interesting combinatorial estructures: k-dominating sets and matchings. Furthermore, we consider not only trees but more general families of graphs for which we compute the exact value of the difference between the determining number and the metric dimension.
References:
[1] R. F. Bailey and P. J. Cameron. Base size, metric dimension and other invariants of groups and graphs. Bull. Lond. Math. Soc., 43(2):209¿242, 2011.
[2] D. L. Boutin. Identifying graph automorphisms using determining sets. Electron. J. Combin., 13(1):Research Paper 78, 12, 2006.
[3] J. Cáceres, D. Garijo, M. L. Puertas, and C. Seara. On the determining number and the metric dimension of graphs. Electron. J. Combin., 17(1):Research Paper 63, 20, 2010.
[4] G. Chartrand, L. Eroh, M. A. Johnson, and O. R. Oellermann. Resolvability in graphs and the metric dimension of a graph. Discrete Appl. Math., 105(1-3):99¿113, 2000.
[5] G. Chartrand, C. Poisson, and P. Zhang. Resolvability and the upper dimension of graphs. Comput. Math. Appl., 39(12):19¿28, 2000.
[6] G. Chartrand and P. Zhang. On the chromatic dimension of a graph. In Proceedings of the Thirty-first Southeastern International Conference on Combinatorics, Graph Theory and Computing (Boca Raton, FL, 2000), volume 145, pages 97¿108, 2000.
[7] M. Jannesari and B. Omoomi. Characterization of n-vertex graphs with metric dimension n ¿ 3. 2011. arXiv:1103.3588v1.
[8] S. Khuller, B. Raghavachari, and A. Rosenfeld. Landmarks in graphs. Discrete Appl. Math., 70(3):217¿229, 1996.
