The difference between the metric dimension and the determining number of a graph

The difference between the metric dimension and the determining number of a graph Delia Garijo, Antonio González ⇑ , Alberto Márquez Departamento de Matemática Aplicada I, Universidad de Sevilla, Spain Keywords: Resolving set Metric dimension Determining set Determining number Locating-dominating set Locating-domination number abstract We study the maximum value of the difference between the metric dimension and the determining number of a graph as a function of its order. We develop a technique that uses functions related to locating-dominating sets to obtain lower and upper bounds on that maximum, and exact computations when restricting to some specific families of graphs. Our approach requires very diverse tools and connections with well-known objects in graph theory; among them: a classical result in graph domination by Ore, a Ramsey-type result by Erd} os and Szekeres, a polynomial time algorithm to compute distinguishing sets and determining sets of twin-free graphs, k-dominating sets, and matchings. 1. Introduction and preliminaries Roughly speaking a resolving set is a subset of the vertices of a graph such that all other vertices are uniquely determined by their distances to those vertices. This concept was introduced in the 1970s by Harary and Melter [21], and independently by Slater [31]. Since one obtains a labeling process for all the vertices, resolving sets can be used to store the position of a mobile object in a scenario modeled by a graph, and design effective algorithms to robot navigation. This is not the only area where this type of sets can be used; we refer the reader to [6] and the survey of Bailey and Cameron [2] for more references on applications to coin weighing problems, strategies for Mastermind game, and pattern recognition, among others. Obviously, in order to design effective algorithms, resolving sets are required to have a cardinality as small as possible but it is also important to consider the following property related to symmetries: the only automorphism of the graph fixing a resolving set is the identity. In general, it is possible to find subsets of vertices with this property (of ‘‘destroying’’ all the automorphisms) and with smaller cardinality than all the resolving sets in the graph; these are cases of determining sets, which were introduced in the 1970s by Sims [30] in the context of computational group theory as specific types of bases. Much later, Boutin [4] and Erwin and Harary [17] used respectively the terms determining set and fixing set to refer to the same concept. In order to analyze how different resolving sets and determining sets can be, Boutin in [4] asked the following question on the parameters minimizing their cardinalities, which are formally defined below together with resolving sets and determining sets. Problem 1. Can the difference between the determining number and the metric dimension of a graph be arbitrarily large? ⇑ Corresponding author. E-mail addresses: [email protected] (D. Garijo), [email protected] (A. González), [email protected] (A. Márquez). Applied Mathematics and Computation One of the main contributions of this paper is the technique that we have developed to approach this problem, which has interest by its own, since it combines very diverse tools that go from a classical result by Ore and a Ramsey-type result of Erd} os and Szekeres to matchings and the design of a polynomial time algorithm to compute sets with some specific properties. To be more precise, we first provide some definitions and notations. Let G¼ðVðGÞ;EðGÞÞ be a finite, simple, undirected, and connected graph of order n¼jVðGÞj. As usual, Gdenotes the complement of G. We write N G ðuÞand N G ½u, respectively, for the open and the closed neighbourhood of a vertex u2VðGÞ. The degree of vertex uis denoted by d G ðuÞ, and dðGÞis the minimum degree of G. The subscript Gwill be dropped from these notations when no confusion may arise. An automorphism of Gis a bijective mapping of VðGÞonto itself such that fðuÞfð v Þ2EðGÞif and only if u v 2EðGÞ. The automorphism group of Gis denoted by AutðGÞ, and its identity element is id G . The stabilizer of a set S#VðGÞis StabðSÞ¼f/2AutðGÞj/ðuÞ¼u; 8 u2Sg, and Sis a determining set of Gif StabðSÞ¼fid G g. The minimum cardinality of a determining set is the determining number of G, written as DetðGÞ. The distance dðu; v Þbetween two vertices u; v 2VðGÞis the length of a shortest u-vpath. A vertex u2VðGÞresolves a pair fx;yg#VðGÞif dðu;xÞ–dðu;yÞ. When every pair of vertices of Gis resolved by some vertex in S, it is said that Sis a resolving set of G. The minimum cardinality of a resolving set is the metric dimension of G, denoted by dimðGÞ, and a resolving set of cardinality dimðGÞis called a metric basis of G. Problem 1 arises naturally since, as it was said before, every resolving set of a graph Gis also a determining set, and so DetðGÞ6dimðGÞ(see [4,17]). Further, the difference between both parameters is either zero or very small in many families of graphs; among them: paths, cycles, complete graphs, and 2-dimensional grids [17,27]. To approach the question we first define the function ðdim DetÞðnÞas the maximum value of dimðGÞDetðGÞover all graphs Gof order n(note that its computation would give the answer to the problem). Then, we develop a technique based mainly on the study of two functions (which are introduced below) related to locating-dominating sets: ðkDetÞðnÞand k j C ðnÞ. Besides its independent interest, this technique lets us improve significantly the best result known to date on Problem 1 which, in terms of our function ðdim DetÞðnÞ, is the following. Proposition 1.1 [5].For every n P8, 2 5n  26ðdim DetÞðnÞ6n2: A vertex u2VðGÞdistinguishes a pair fx;yg#VðGÞif either u2fx;ygor precisely one of x;yis adjacent to u, and a set D#VðGÞis a distinguishing set of Gif every pair of vertices of Gis distinguished by some vertex in D. When Dis also a dominating set (i.e., NðxÞ\D–;for every x2VðGÞnD) it is said that Dis a locating-dominating set. The minimum cardinality of a locating-dominating set is the locating-domination number of G, denoted by kðGÞ. Note that kðGÞ6n1 since every subset of n1 vertices is a locating-dominating set of G. Although distinguishing sets and locating-dominating sets were introduced in different contexts (see [1,32]) they are in essence the same concept: given a distinguishing set D#VðGÞ, by definition there is at most one vertex x2VðGÞnDso that NðxÞ\D¼;. Thus D[fxgis a locating-dominating set. This yields the following. Observation 1.2. Let Dbe a distinguishing set of a graph G. Then, kðGÞ6jDjþ1. Every locating-dominating set D#VðGÞis clearly a resolving set since each pair fx;yg#VðGÞnDis distinguished by some vertex u2Dand so either dðu;xÞ¼1<dðu;yÞor dðu;yÞ¼1<dðu;xÞ. Thus, DetðGÞ6dimðGÞ6kðGÞfor every graph G. Let ðkDetÞðnÞand kðnÞbe the maximum values of, respectively, kðGÞDetðGÞand kðGÞover all graphs Gof order n. Note that the function kðnÞequals n1 (attained by the complete graph K n ) but the non-trivial restriction of this function to the class C  of twin-free graphs (i.e., graphs that do not contain twin vertices, which are formally defined in SubSection 3.1), denoted by k j C ðnÞ, will play an important role throughout the paper. Thus, ðdim DetÞðnÞ6ðkDetÞðnÞ6kðnÞ¼n1:ð1Þ In Section 2, we find lower bounds on the functions ðdim DetÞðnÞand ðkDetÞðnÞby constructing appropriate families of graphs. In particular, we improve the lower bound of Proposition 1.1 and conjecture that these new bounds are precisely the exact expressions of those functions. Section 3develops a method to prove that k j C ðnÞis an upper bound on ðdim DetÞðnÞand ðkDetÞðnÞ, which is a key result in our study. Moreover, we conjecture a formula for the function k j C ðnÞ. Sections 4 and 5 contain two explicit upper bounds on k j C ðnÞ. Although the one in Section 5gives a better approach, we believe that the technique used to obtain the bound in Section 4has interest by its own and so it is worth to be included in this paper. This technique uses a variant of a classical theorem in domination theory due to Ore [28], which lets us relate, for twin-free graphs, the locating-domination number with a series of classical graph parameters (following the same spirit as the relationships existing among different domination parameters; see [23] for a number of examples). The desired bound is then obtained by using those relations and a Ramsey-type result of Erd} os and Szekeres [16]. 488 D. Garijo et al./ Applied Mathematics and Computation 249 (2014) 487–501 Our second upper bound on k j C ðnÞappears in Section 5and is, as far as we know, the best approach to the function ðdim DetÞðnÞ. It is obtained by a greedy algorithm which produces distinguishing sets and determining sets of bounded size. This algorithm also gives an upper bound on the determining number of a twin-free graph. In Section 6, we obtain exact expressions and bounds on the restrictions of the functions ðdim DetÞðnÞand ðkDetÞðnÞ to the family of graphs not containing the cycle C 4 as a subgraph, and the subfamily of trees. To do this, we design tools of independent interest related to k-dominating sets and matchings. Our results on trees close the study initiated by Cáceres et al. [5] on the difference between the metric dimension and the determining number in this class of graphs. We conclude the paper in Section 7with some remarks and open problems. 2. Lower bounds on ðdim DetÞðnÞand ðkDetÞðnÞ Let T m with mP6 be a tree that consists of a path ðu 1 ;...;u m Þand a pendant vertex u 0 adjacent to u 3 , and let G m be the corona product T m K 1 , i.e., the graph with vertex set VðG m Þ¼VðT m Þ[f v 0 ; v 1 ;...; v m gand edge set EðG m Þ¼ EðT m Þ[fu i v i j06i6mg. By adding another pendant vertex v 0 0to u 0 in G m we obtain the graph H m . Both graphs are shown in Fig. 1. By definition, VðH m Þ¼VðG m Þ[f v 0 0 gand EðH m Þ¼EðG m Þ[fu 0 v 0 0 g. The following lemma is the key tool to obtain lower bounds on the functions ðdim DetÞðnÞand ðkDetÞðnÞ. Lemma 2.1. For every m P6, the following statements hold. (i) DetðG m Þ¼0and DetðH m Þ¼1. (ii) dimðG m Þ¼m and dimðH m Þ¼mþ1. (iii) kðG m Þ¼mþ1and kðH m Þ¼mþ2. Proof. Since mP6;AutðG m Þis trivial and there is only one non-trivial automorphism of H m which maps v 0 onto v 0 0 . Thus, Statement (i) easily follows. Every resolving set Sof G m contains, for every 0 6i6mbut at most one, either vertex u i or vertex v i (note that, in G m ;dðu j ; v ‘ Þ¼dð v j ; v ‘ Þ¼1 for all j–‘and so the pair fu j ;u ‘ gis only distinguished by vertices u j ;u ‘ ; v j and v ‘ ). Hence dimðG m ÞPm, and the set S¼fu 0 ;u 1 ;...;u m2 ;u m gattains the bound. An analogous argument proves that S[f v 0 0 gis a metric basis of H m . Therefore, Statement (ii) holds. To prove Statement (iii), consider a locating-dominating set Dof G m . Clearly, for every 0 6i6m, either vertex u i or vertex v i belongs to D. Thus kðG m ÞPmþ1, and the set D¼fu 0 ;...;u m ggives the equality. By a similar argument one obtains kðH m Þ¼mþ1. h Observation 2.2. Since AutðGÞ¼AutðGÞthen DetðGÞ¼DetðGÞand so the preceding lemma gives DetðG m Þ¼0 and DetðH m Þ¼1. Cáceres et al. [5] used the wheel graph W 1;n to obtain the lower bound of Proposition 1.1. Our graphs G m and H m (for appropriate m) improve that bound, and moreover, we also obtain a lower bound on ðkDetÞðnÞby using the graphs G m and H m . Theorem 2.3. For every n P14, ðdim DetÞðnÞPn 2 jk1 and ðkDetÞðnÞPn 2 jk : Proof. For each function, it suffices to give a graph of order nP14 such that the difference between its corresponding parameters equals the bound of the statement. By Lemma 2.1, we can take the graphs G n 2 1 (neven) and H n1 2 1 (nodd) for the function ðdim DetÞðnÞ; the graphs G n 2 1 (neven) and H n1 2 1 (nodd) yield the bound for ðkDetÞðnÞ. Note that nP14 since the graphs G m ;H m ;G m and H m are defined for mP6. h Fig. 1. The graphs (a) G m and (b) H m . D. Garijo et al. / Applied Mathematics and Computation 249 (2014) 487–501 489 We shall exhibit large classes of graphs Csuch that the maximum values of, respectively, dimðGÞDetðGÞand kðGÞDetðGÞover all graphs G2Cof order ndo not exceed n 2 . Thus, we believe that the preceding bounds are in fact the exact expressions of our functions. Conjecture 1. There exists a positive integer n 0 such that, for every nPn 0 , ðdim DetÞðnÞ¼ n 2 jk1 and ðkDetÞðnÞ¼ n 2 jk : 3. An upper bound on ðdim DetÞðnÞand ðkDetÞðnÞ This section is devoted to the proof of one of our main results: the functions ðdim DetÞðnÞand ðkDetÞðnÞare bounded above by k j C ðnÞ. The main idea of this proof is that from every graph Gone can obtain an adequate twin-free graph e Gsuch that kðGÞis bounded above by kðe GÞplus some constant depending on the graphs. 3.1. The twin graph G  and the graph e G The construction of our twin-free graph e Gis based on the so called twin graph G  , which is obtained from a given graph G by identifying vertices with the same neighbourhood. This graph and its variations (depending on the choice of closed and/or open neighbourhoods) have been used to solve many problems in graph theory (see for instance [22,29]) since they completely characterize the original graph G. We begin by recalling its formal definition. Two different vertices u; v 2VðGÞare twins if NðuÞ¼Nð v Þor N½u¼N½ v , i.e., no vertex of VðGÞnfu; v gdistinguishes the pair fu; v g. This definition induces the following equivalence relation on VðGÞ:u v if and only if either u¼ v or uand v are twins; see [26]. Let u  ¼f v 2VðGÞju v gand consider the partition u  1 ;...;u  r of VðGÞinduced by the relation , where rP1 and every u i is a representative of u  i . The twin graph of G, denoted by G  , has vertex set VðG  Þ¼fu  1 ;...;u  r gand edge set EðG  Þ¼fu  i u  j ju i u j 2EðGÞg (which is well-defined as Statement (i) of Lemma 3.1 below shows). Note that, for every u2VðGÞ, we shall consider u  as a class in VðGÞas well as a vertex of G  (see the graphs Gand G  in Fig. 2 for an example). Lemma 3.1 [26].For every graph G, the following statements hold. (i) The graph G  is independent of the choice of the representatives u i , i.e., u  i u  j 2EðG  Þ()xy 2EðGÞ8x2u  i ;y2u  j : (ii) Every class u  i either induces a complete subgraph or is an independent set in G. A vertex u  i 2VðG  Þis said to be of type ð1Þif ju  i j¼1; otherwise, according to Statement (ii) of Lemma 3.1, vertex u  i is either of type ðKÞor of type ðNÞ, depending on whether u  i induces a complete subgraph or is an independent set in G. When u  i is of type ðKÞor ðNÞ, it is said to be of type ðKNÞ. Considering vertex u  i as a class in VðGÞand x;y2u  i , one has that N½x¼N½ywhenever u  i is of type ðKÞ, and NðxÞ¼NðyÞif u  i is of type ðNÞ(see the graph G  in Fig. 2). For more properties of G  we refer the reader to [26]. Let e Gbe the graph obtained from G  by adding a pendant vertex to every vertex u  i 2VðG  Þof type ðKNÞthat has a twin in G  (note that G  is not necessarily twin-free). Let Vðe GÞ¼VðG  Þ[Pwhere Pdenotes the set of pendant vertices adjacent to the u  i ’s. Fig. 2 shows an example of this construction. Observe that now the notation u  represents a class in VðGÞ, a vertex of G  , and a vertex of e G. Fig. 2. The dotted ellipses in Gindicate the different classes in VðGÞ. Informally, the vertices of G  are obtained by replacing each class in VðGÞby one vertex; the labels indicate the type of vertex. The squared vertices in e Gform the set P. 490 D. Garijo et al./ Applied Mathematics and Computation 249 (2014) 487–501 3.2. Using locating-dominating sets of twin-free graphs In this section, we obtain the desired upper bound on the functions ðdim DetÞðnÞand ðkDetÞðnÞby using the locatingdomination number of our graph e G, which is proved to be twin-free in Lemma 3.4 below. Twin-free graphs are important for their own sake and also for their multiple applications (see for example [7,22]); here, their properties are fundamental for reaching Theorem 3.7 which is one of our main results. We begin with an observation and a series of lemmas. Observation 3.2. For every graph G, no two different vertices u  i ;u  j 2VðG  Þof type ð1Þare twins in G  ; otherwise, by construction of G  ;u i and u j would be twins in Gbut u  i –u  j . Let X G ¼S 16i6r ðu  i nfu i gÞwhere r¼jVðG  Þj. This set consists of all but one vertex of every class of type ðKNÞsince u  i nfu i g is empty for classes u  i of type ð1Þ. Thus j X G j¼nrand moreover, by definition of equivalence classes, no two vertices of VðGÞn X G are twins in G. Lemma 3.3. Let G be a graph of order n such that G  has order r. Then, DetðGÞPnr: In particular, kðGÞDetðGÞ6r1. Proof. Given a class u  i of type ðKNÞin VðGÞand x;y2u  i , there is a non-trivial automorphism which maps xonto yand fixes the remaining vertices. Hence, every determining set Sof Gcontains either vertex xor vertex y. Thus, one can deduce that S contains all but one vertex of each class of type ðKNÞ, i.e., j X G j¼nrvertices. Therefore DetðGÞPnr, and combining this with kðGÞ6n1 yields kðGÞDetðGÞ6r1. h Lemma 3.4. Let G be a graph of order n such that G  is not isomorphic to K 2 . Then, the graph e G has order e n6n and is twin-free. Proof. When obtaining G  from G, we ‘‘lose’’ at least one vertex per each class of type ðKNÞ. Further, to construct e Gfrom G  we only have to add the set Pwhose cardinality is at most the number of vertices of type ðKNÞ. Hence, e n6n. Suppose now on the contrary that e Ghas a pair of twin vertices. Since by construction each vertex in Phas a single distinct neighbour in VðG  Þ, those twin vertices are not both contained in P. If both belong to VðG  Þ, one can easily check that they are also twins in G  and, by Observation 3.2, at least one of them is of type ðKNÞ. Thus, they are distinguished in e Gby the corresponding pendant vertex of P; a contradiction. Suppose now that just one of the twin vertices is in VðG  Þ; let u  i 2VðG  Þ (for some 1 6i6r) and v 2Pbe those twin vertices. Let Ne G ð v Þ¼fu  j gwhere u  j 2VðG  Þ.IfNe G ½u  i ¼Ne G ½ v ¼f v ;u  j gthen u  i ¼u  j and e GffiK 2 . Moreover, since v 2Pwe have G  ffiK 1 but then e Gwould also be isomorphic to K 1 ; a contradiction. Hence, Ne G ðu  i Þ¼Ne G ð v Þ¼fu  j gand u  i –u  j . Note that N G  ðu  i Þ¼Ne G ðu  i Þ¼fu  j g. Further, by construction of e G, vertex u  j has a twin u  ‘ in G  which cannot be vertex u  i (otherwise u  i and u  j would be twins in G  and so G  would be isomorphic to K 2 ). This implies that u  ‘ 2N G  ðu  i Þ¼fu  j g, which leads to a contradiction. h We now relate the locating-domination numbers of the graph Gand its associated twin-free graph e G. Lemma 3.5. Let G be a graph of order n such that G  has order r. Then, kðGÞ6kðe GÞþnr: In particular, kðGÞDetðGÞ6kðe GÞ. Proof. Let eSbe a minimum locating-dominating set of e G, and let e u2Vðe GÞ¼VðG  Þ[P.Ife u2VðG  Þthen there exists a unique vertex u  i 2VðG  Þsuch that e u¼u  i , and if e u2Pthen there is a unique vertex u  i 2VðG  Þso that Ne G ðe uÞ¼fu  i g. For each case, consider the representative u i 2VðGÞof that class u  i , and the mapping p :Vðe GÞ!VðGÞgiven by p ðe uÞ¼u i . Clearly, the set p ðeSÞ¼f p ðe uÞje u2eSgsatisfies that j p ðeSÞj 6jeSj¼kðe GÞ(it might be p ðe uÞ¼ p ðe v Þfor e u2Pand e v 2Ne G ðe uÞ). Thus, to obtain the desired bound it suffices to prove that S¼ p ðeSÞ[ X G is a locating-dominating set of G(recall that X G ¼S 16i6r ðu  i nfu i gÞand so j X G j¼nr). We next show that Sis a distinguishing set of G; a similar analysis (omitted for the sake of brevity) proves that Sis also a dominating set. Observe first that ð p ðe uÞÞ  #Sfor every e u2eS. Now, let x;y2VðGÞnS. Since x;yR X G then x  –y  and thus x  ;y  2VðG  Þ#Vðe GÞ. Hence, there is a vertex e u2eSdistinguishing fx  ;y  gin e G, and such that e u–x  –y  (if, say, e u¼x  then x  ¼ð p ðe uÞÞ  #Sbut xRS). We have e u2VðG  Þsince if e u2P then one can assume, without loss of generality, that Ne G ðe uÞ¼fx  gand so ð p ðe uÞÞ  ¼x  #Swhich contradicts xRS. Therefore, e uis distinguishing fx  ;y  gin G  .Ifx  2N G  ðe uÞand y  RN G  ðe uÞthen, D. Garijo et al. / Applied Mathematics and Computation 249 (2014) 487–501 491 by Lemma 3.1,x2N G ð p ðe uÞÞ and yRN G ð p ðe uÞÞ (the opposite case is similar). This implies that Sis a distinguishing set of G. Finally, by Lemma 3.3, DetðGÞPnrand so kðGÞDetðGÞ6kðe GÞ.h Let ðdim DetÞ j C ðnÞ;ðkDetÞ j C ðnÞand k j C ðnÞdenote the restrictions of our functions to a class of graphs C. Recall that C  is the class of twin-free graphs, and note that for that class, the functions can be considered for nP4 since P 4 is the smallest twin-free graph. Lemma 3.6. k j C ðnÞ6k j C ðnþ1Þ. Proof. We first prove that kðGÞ6kðHÞfor every graph Hobtained by adding a pendant edge to a given graph G. Indeed, consider a minimum locating-dominating set Sof H, and let u v 2EðHÞdenote the pendant edge with u2VðHÞnVðGÞ.IfuRS then S#VðGÞis also a locating-dominating set of G, and so kðGÞ6kðHÞ. Otherwise u2S, and S 0 ¼ðSnfugÞ[f v gis a locatingdominating set of G. Therefore, kðGÞ6jS 0 j6jSj¼kðHÞ. Consider now a twin-free graph Gof order nsuch that kðGÞ¼k j C ðnÞ. Set Hto be the graph obtained from Gby adding a pendant vertex uto a vertex v 2VðGÞwhose neighbours in Ghave degree at least 2. Note that to find such a vertex is possible since Gis not the disjoint union of copies of K 1 or K 2 , which is neither connected nor twin-free. Hence, Hhas order nþ1 and is twin-free. Moreover, kðGÞ6kðHÞsince His obtained by adding a pendant edge to G. Therefore, k j C ðnÞ6k j C ðnþ1Þ.h We thus reach the main result of this section which, in particular, improves significantly Expression (1) in Section 1. Theorem 3.7. For every n P4, ðdim DetÞðnÞ6ðkDetÞðnÞ6k j C ðnÞ: Proof. Let Gbe a graph of order nsuch that kðGÞDetðGÞ¼ðkDetÞðnÞ. Observe first that G  ÀK 2 ; otherwise, by Lemma 3.3, ðkDetÞðnÞ¼kðGÞDetðGÞ61< n 2 which contradicts Theorem 2.3. Thus, by Lemma 3.4, the graph e Gis twin-free and e n¼jVðe GÞj 6n. Hence, kðe GÞ6k j C ðe nÞ6k j C ðnÞ;ð2Þ the last inequality being a consequence of Lemma 3.6. Further, Lemma 3.5 yields ðkDetÞðnÞ¼kðGÞDetðGÞ6kðe GÞ:ð3Þ The result follows combining Expressions (2) and (3).h Theorems 2.3 and 3.7 give k j C ðnÞP n 2 and, throughout this paper, we shall find numerous conditions for a twin-free graph to satisfy kðGÞ6 n 2 . Thus, we believe that the following conjecture, which implies most of Conjecture 1, is true. Conjecture 2. There exists a positive integer n 1 such that, for every nPn 1 , k j C ðnÞ¼ n 2 jk : Theorem 3.7 implies that bounding the function k j C ðnÞyields bounds on ðdim DetÞðnÞand ðkDetÞðnÞ. Thus, the following two sections are mainly concerned with the locating-domination number of twin-free graphs. 4. From minimal dominating sets to locating-dominating sets In this section we present a variant of one of the first results in the field of domination theory due to Ore [28] (see [23] for an extensive bibliography on this very active area of graph theory) which lets us relate the locating-domination number of a twin-free graph Gwith the upper domination numbers and chromatic numbers of Gand G, and the independence number and clique number of G. On the one hand, these relations produce sufficient conditions for Gto verify kðGÞP n 2 , giving thus support to Conjecture 2. On the other hand, by means of the last-mentioned relation and a classical result due to Erd} os and Szekeres [16], we reach our first upper bound on the function k j C ðnÞ. A set D#VðGÞis a minimal dominating set if no proper subset of Dis a dominating set of G;minimal locating-dominating sets are defined analogously. The domination number c ðGÞis the minimum cardinality of a dominating set of G. Theorem 4.1 [28].A set D #VðGÞis a minimal dominating set if and only if each vertex u 2D satisfies that either NðuÞ#VðGÞnD or NðxÞ\D¼fugfor some x 2VðGÞnD. 492 D. Garijo et al./ Applied Mathematics and Computation 249 (2014) 487–501 Theorem 4.2 [28].Let G be a graph without isolated vertices and let D #VðGÞbe a minimal dominating set of G. Then, VðGÞnDis a dominating set of G. Consequently, c ðGÞ6 n 2 . Observe that if one could prove that the complement of every minimal locating-dominating set of a twin-free graph is a locating-dominating set then k j C ðnÞ6 n 2 , and by Theorems 2.3 and 3.7,k j C ðnÞP n 2 . Thus, Conjecture 2 would be proved in the affirmative. Unfortunately, Fig. 3 shows that this property is not true in general for minimal locating-dominating sets of twin-free graphs. However, we can establish a similar relation between minimal dominating sets and locating-dominating sets. Theorem 4.3. Let G be a twin-free graph and let D #VðGÞbe a minimal dominating set of G. Then, VðGÞnD is a locatingdominating set of G. Proof. Let Dbe a minimal dominating set of G. Since Gis connected, by Theorem 4.2, it suffices to prove that VðGÞnDis a distinguishing set of G. To do this, we show that every pair of vertices x;y2Dis distinguished by some vertex in VðGÞnD.If NðxÞ;NðyÞ#VðGÞnDthen the result easily follows since Gis twin-free. Otherwise, say that NðxÞ\D–;.ByTheorem 4.1, there is a vertex u2VðGÞnDsuch that NðuÞ\D¼fxg. Hence, vertex udistinguishes the pair fx;yg.h One of the most studied invariants in domination theory is the upper domination number CðGÞwhich is the maximum cardinality of a minimal dominating set of G. We refer the reader to [23] for a number of results involving this parameter. Corollary 4.4. Let G be a twin-free graph. Then, kðGÞ6nmaxf C ðGÞ; C ðGÞ1g: In particular, kðGÞ6 n 2 when either CðGÞP n 2 or CðGÞP n 2 þ1. Proof. By Theorem 4.3,kðGÞ6nCðGÞfor every twin-free graph G. Further, Theorem 7 of [25] gives jkðGÞkðGÞj 61 and so kðGÞ6kðGÞþ16nCðGÞþ1 since Gis also twin-free. Therefore, kðGÞ6minfnCðGÞ;nCðGÞþ1g.h Recall that the independence number a ðGÞand the clique number x ðGÞare the maximum cardinality of an independent set and the maximum order of a complete subgraph of G, respectively. Corollary 4.5. Let G be a twin-free graph. Then, kðGÞ6nmaxf a ðGÞ; x ðGÞ1g: In particular, kðGÞ6 n 2 when either a ðGÞP n 2 or x ðGÞP n 2 þ1. Proof. Every vertex in an independent set Iof maximum cardinality a ðGÞhas a neighbour in VðGÞnIand so Iis a dominating set of G. Moreover, by Theorem 4.1, the dominating set Iis minimal since NðuÞ#VðGÞnIfor every u2I. Hence a ðGÞ6CðGÞ, and analogously CðGÞP a ðGÞ¼ x ðGÞ. Combining these inequalities with Corollary 4.4, one obtains the desired bound since G is twin-free and so is G.h The chromatic number of G, denoted by v ðGÞ, is the smallest number of classes needed to partition VðGÞsuch that no two adjacent vertices belong to the same class. A classical result in graph theory establishes that x ðGÞP2 v ðGÞnfor every graph G(see for instance [9]). Thus, a ðGÞ¼ x ðGÞP2 v ðGÞnand we can deduce the following result from Corollary 4.5. Corollary 4.6. Let G be a twin-free graph. Then, kðGÞ62nmaxf2 v ðGÞ;2 v ðGÞ1g: Consequently, kðGÞ6 n 2 when either v ðGÞP 3 4 nor v ðGÞP 3 4 nþ 1 2 . Fig. 3. A twin-free graph of order 5kthat consists of kpaths of length 4, each hanging from a vertex of a path on kP1 vertices. This graph has a minimal locating-dominating set (depicted as squared vertices) of cardinality 3k, whose complement is not a locating-dominating set. D. Garijo et al. / Applied Mathematics and Computation 249 (2014) 487–501 493 Erd} os and Szekeres [16] proved that every graph of order ncontains either an independent set or a complete subgraph with at least d log 2 n 2 evertices. This and Corollary 4.5 give our first upper bound on k j C ðnÞwhich, by Theorem 3.7, is also a bound on the functions ðdim DetÞðnÞand ðkDetÞðnÞ. Corollary 4.7. For every n P4, ðdim DetÞðnÞ6ðkDetÞðnÞ6k j C ðnÞ6nlog 2 n 2  þ1: Observe that the preceding bound improves significantly the upper bound of Proposition 1.1, due to Cáceres et al. [5]. 5. A greedy algorithm to compute distinguishing sets and determining sets of twin-free graphs Babai [1] introduced distinguishing sets to study the graph isomorphism problem; he proved that deciding whether a graph Gof order nis isomorphic to any other graph can be done in oðn dþ3 Þtime whenever Ghas a distinguishing set of size d. As a consequence of one of his results, concretely the following lemma, we obtain Observation 5.2 below, which also supports Conjecture 2. Lemma 5.1 [1].Let G be a graph of order n and let M be such that jNðxÞ D NðyÞj PM for any x;y2VðGÞ. Then, G has a distinguishing set of cardinality at most 2nlog n Mþ2 lm provided that M >4 log n. Note that the condition of Lemma 5.1 on the symmetric difference NðxÞ D NðyÞimplies, in particular, that the graph Gis twin-free (as those of Conjecture 2). Further, when nP32 and M>4 log n,Lemma 5.1 and Observation 1.2 give kðGÞ6 2nlog n Mþ2 lm þ16 n 2 . Observation 5.2. A graph Gof order nP32 satisfies that kðGÞ6 n 2 whenever jNðxÞ D NðyÞj >4 log nfor every x;y2VðGÞ. By Procedure G REEDY -P ARTITION below, we can also obtain distinguishing sets of bounded size but (unlike in Lemma 5.1) imposing no restriction on the twin-free graph G. This is a polynomial time algorithm that, in addition, produces determining sets of bounded size. Its restriction to a specific family of graphs (concretely twin-free graphs) is natural since Colbourn et al. [13] showed that computing the locating-domination number of an arbitrary graph is NP-hard. We first require some notation. Given D#VðGÞ, there is an equivalence relation on VðGÞgiven by u D v if and only if either u¼ v or fu; v gis distinguished by no vertex of D. Denote by ½u D the set of vertices v 2VðGÞsuch that u D v . Note that a set Dis a distinguishing set of Gif the partition of VðGÞinduced by  D consists of unitary classes. Let D 1 be the set of vertices of VðGÞnDwhose class is unitary, and let D >1 ¼VðGÞnðD[D 1 Þ. Observe that D;D 1 ;D >1 form a partition of VðGÞ, where any of these sets may be empty. Procedure: G REEDY -P ARTITION Input: A twin-free graph G. Output: A partition of VðGÞinto three subsets A;B;C. 1. Take a vertex u 0 2VðGÞ. Let A¼fu 0 g;B¼A 1 , and C¼A >1 ; 2. While there exist u;x;y2Csuch that ½x A ¼½y A and ½x A[fug –½y A[fug do (a) Add vertex uto A, and rename A:¼A[fug; (b) Take B:¼A 1 and C:¼A >1 ; The following lemma says that combining the sets A;B;Cproperly, one obtains, as it was mentioned before, distinguishing sets and determining sets of bounded size. Lemma 5.3. Let A;B;C be the sets obtained by application of Procedure G REEDY -P ARTITION to a twin-free graph G. Then, the following statements hold. (i) A[B;A[C and B [C are distinguishing sets of G. (ii) A and B [C are determining sets of G. Proof. To prove Statement (i), observe first that Procedure G REEDY -P ARTITION returns a partition of VðGÞinto three subsets A;B;Csuch that B¼A 1 ;C¼A >1 and no pair fx;yg#Cwith ½x A ¼½y A is distinguished by any u2Cnfx;yg(if it exists). Since ½x A[C #½x A and the class ½x A is unitary for every x2ðVðGÞnðA[CÞÞ ¼ B¼A 1 , then the partition of VðGÞinduced by  A[C consists of unitary classes. Hence, A[Cis a distinguishing set of G. 494 D. Garijo et al./ Applied Mathematics and Computation 249 (2014) 487–501 That A[Bis a distinguishing set follows from the fact that Gis twin-free and so, in particular, every pair fx;yg#ðVðGÞnðA[BÞÞ ¼ Cis distinguished by some vertex u2VðGÞnfx;yg. Further, vertex ueither belongs to A(if ½x A –½y A ) or belongs to B(if ½x A ¼½y A ). It remains to prove that B[Cis a distinguishing set. To do this, let A¼fx 1 ;...;x jAj gwhose elements are ordered as they appear in Procedure G REEDY -P ARTITION ; we next show that every pair fx i ;x j gwith i<jis distinguished by some vertex in B[C. Vertex x j comes from a vertex u2Cthat is added to A(at Step 2(a) of Procedure G REEDY -P ARTITION ) when a class ½x fx 1 ;...;x j1 g ¼½y fx 1 ;...;x j1 g (for some x;y2C) can be split into two distinct classes ½x fx 1 ;...;x j1 ;x j g and ½y fx 1 ;...;x j1 ;x j g . Hence, every pair fz;tgwith z2½x fx 1 ;...;x j g and t2½y fx 1 ;...;x j g is distinguished by x j and not by x 1 ;...;x j1 . Thus, fz;tgis not contained in fx 1 ;...;x j g, and moreover the pair fx i ;x j gwith i<jis distinguished by either zor t. In the following steps of the procedure, it might happen that z¼x ‘ with ‘>j(analogous for vertex t) and so, at the end of the process, vertex zwould not belong to B[Cbut to A. In this case, zcan be replaced by another vertex z 0 2B[Cthat plays the same role than z. This comes from the fact that when a vertex in Cgoes to A(at Step 2(a) of the process), the remaining vertices of its class (which has cardinality at least 2) either go to the corresponding set Bor stay in the corresponding set C; one of those vertices can be taken as z 0 . Therefore, at the end of the process, we obtain two sets B;Csuch that B[Cis a distinguishing set of G, and so Statement (i) follows. Observe now that every distinguishing set is a resolving set and so also a determining set. Thus, Statement (i) implies Statement (ii) for B[C. To prove that Ais a determining set of G, it suffices to show that StabðAÞ¼StabðA[BÞsince one can deduce from Statement (i) that A[Bis a determining set, i.e., StabðA[BÞ¼fid G g. By definition, StabðA[BÞ#StabðAÞ. Further, given x2B¼A 1 there does not exist y2B[Csuch that NðyÞ\A¼NðxÞ\A. Hence, an automorphism of Gthat fixes every vertex in Ahas to fix vertex x. Therefore, StabðAÞ#StabðA[fxgÞ. Extending this argument to every vertex in Bit follows that StabðAÞ#StabðA[BÞ.h 5.1. The best approach to ðdim DetÞðnÞand an upper bound on DetðGÞfor twin-free graphs G The pigeonhole principle ensures that one set among the A;B;Cof Procedure G REEDY -P ARTITION has cardinality at least d n 3 e and so one of A[B;A[C;B[Chas cardinality at most b 2 3 nc. Thus, by Statement (i) of Lemma 5.3 and Observation 1.2,we reach our second upper bound on the function k j C ðnÞ. Theorem 5.4. Let G be a twin-free graph of order n P4. Then, there exists a locating-dominating set of G of cardinality at most b 2 3 ncþ1, which can be computed in polynomial time. In particular, k j C ðnÞ62 3n  þ1: The following corollary combines Theorems 2.3, 3.7 and 5.4 providing, as far as we know, the best approach to Problem 1. Corollary 5.5. For every n P14, n 2 jk16ðdim DetÞðnÞ6ðkDetÞðnÞ6k j C ðnÞ62 3n  þ1: Again, by the pigeonhole principle, it follows that either Aor B[Chas cardinality at most n 2 . Hence, by Statement (ii) of Lemma 5.3, we obtain the following. Theorem 5.6. Let G be a twin-free graph of order n P4. Then, there exists a determining set of G of cardinality at most n 2 , which can be computed in polynomial time. In particular, DetðGÞ6n 2 jk : We conclude this section with two remarks on the bound of Theorem 5.6. On the one hand, we do not know if that bound is tight although we have already found a tree that has determining number n 2 1 (see Fig. 4). On the other hand, the bound is explicit; this is important since Gibbons and Laison [20] gave an algorithm that for an arbitrary graph Gof order n, returns a determining set of cardinality OðDetðGÞlog log nÞ. Fig. 4. A tree of order nthat consists of n 2 paths of length 2 with a common endpoint. Its determining number is n 2 1 since the squared vertices form a minimum determining set. D. Garijo et al. / Applied Mathematics and Computation 249 (2014) 487–501 495