The Equidistant Dimension of Graphs

Bull. Malays. Math. Sci. Soc. (2022) 45:1757–1775 https://doi.org/10.1007/s40840-022-01295-z The Equidistant Dimension of Graphs A. González1 ·C. Hernando2 ·M. Mora2 Received: 23 July 2021 / Revised: 22 March 2022 / Accepted: 13 April 2022 / Published online: 6 May 2022 © The Author(s) 2022 Abstract A subset Sof vertices of a connected graph Gis a distance-equalizer set if for every two distinct vertices x,y∈V(G)\Sthere is a vertex w∈Ssuch that the distances from x and yto ware the same. The equidistant dimension of Gis the minimum cardinality of a distance-equalizer set of G. This paper is devoted to introduce this parameter and explore its properties and applications to other mathematical problems, not necessarily in the context of graph theory. Concretely, we first establish some bounds concerning the order, the maximum degree, the clique number, and the independence number, and characterize all graphs attaining some extremal values. We then study the equidistant dimension of several families of graphs (complete and complete multipartite graphs, bistars, paths, cycles, and Johnson graphs), proving that, in the case of paths and cycles, this parameter is related to 3-AP-free sets. Subsequently, we show the usefulness of distance-equalizer sets for constructing doubly resolving sets. Keywords Distance-equalizer set ·Equidistant dimension ·Resolving set ·Doubly resolving set ·Metric dimension Mathematics Subject Classification 05C12 ·05C69 Communicated by Rosihan M. Ali. This project has received funding from the European Union’s Horizon 2020 research and innovation programme under the Marie Skłodowska-Curie Grant Agreement No. 734922. BA. González [email protected] C. Hernando [email protected] M. Mora [email protected] 1Department of Didactics of Mathematics, Universidad de Sevilla, Seville, Spain 2Departament de Matemàtiques, Universitat Politècnica de Catalunya, Barcelona, Spain 123 1758 A. González et al. 1 Introduction The notion of resolving set, also known as locating set, was introduced by Slater [40] and, independently, by Harary and Melter [28]. This concept arises in diverse areas, including location problems in networks of different nature (see [11]). For example, in order to locate a failure in a computer network modeled as a graph, we are interested in a subset of vertices Ssuch that every vertex of the underlying graph might be uniquely determined by its vector of distances to the vertices of S. Such a set is called a resolving set of the graph, and the metric dimension of that graph is the minimum cardinality of a resolving set. Resolving sets and several related sets, such as identifying codes, locatingdominating sets or watching systems, have been widely studied during the last decades (see [3,10,18,35]), as well as doubly resolving sets, a type of subset of vertices more restrictive than resolving sets with multiple applications in different areas [11,12,15, 26,31–33]. However, many recent papers [13,16,17,24,41,43,44] have turned their attention precisely in the opposite direction to resolvability, thus trying to study anonymization problems in networks instead of location aspects. For instance, the need to ensure privacy and anonymity in social networks makes necessary to develop graph tools such as the concepts of antiresolving set and metric antidimension, introduced by Trujillo-Rasua and Yero [41]. Indeed, a subset of vertices Ais a 2-antiresolving set if, for every vertex v/∈A, there exists another different vertex w/∈Asuch that v and whave the same vector of distances to the vertices of A.The2-metric antidimension of a graph is the minimum cardinality among all its 2-antiresolving sets. With the same spirit, this paper introduces new graph concepts that can also be applied to anonymization problems in networks: distance-equalizer set and equidistant dimension. Furthermore, we shall see that these concepts have concrete applications in mathematical problems, such as obtaining new bounds on the size of doubly resolving sets of graphs, as well as a new formulation in terms of graphs of a classical problem of number theory. The paper is organized as follows. In Sect. 2, we define distance-equalizer sets and the equidistant dimension and show bounds in terms of other graph parameters: order, diameter, maximum degree, independence number, and clique number. Section 3is devoted to characterize all graphs attaining some extremal values of the equidistant dimension. In Sect. 4we study this parameter for some families of graphs: complete and complete multipartite graphs, bistars, paths, cycles, and Johnson graphs. For the particular cases of paths and cycles, we show that this parameter is related to 3-AP- free sets. In Sect. 5, we obtain bounds for general graphs and trees on the minimum cardinality of doubly resolving sets in terms of the equidistant dimension. Finally, we present some conclusions and open problems in Sect. 6. All graphs considered in this paper are connected, undirected, simple, and finite. The vertex set and the edge set of a graph Gare denoted by V(G)and E(G), respectively. The order of Gis |V(G)|. For any vertex v∈V(G), its open neighborhood is the set N(v) ={w∈V(G):vw ∈E(G)}and its closed neighborhood is N[v]=N(v) ∪{v}. 123 The Equidistant Dimension of Graphs 1759 Fig. 1 Black vertices form a distance-equalizer set of minimum size for P8 The degree of a vertex v, denoted by deg(v), is defined as the cardinality of N(v). If deg(v) =1, then we say that vis a leaf, in which case the only vertex adjacent to vis called its support vertex. When deg(v) =|V(G)|−1, we say that vis universal.Themaximum degree of Gis Δ(G)=max {deg(v) :v∈V(G)}and its minimum degree is δ(G)=min {deg(v) : v∈V(G)}.Thedistance between two vertices v,w ∈V(G)is denoted by d(v, w), and the diameter of Gis D(G)=max{d(v, w) :v,w ∈V(G)}.Aclique is a subset of pairwise adjacent vertices and the clique number of G, denoted by ω(G),isthe maximum cardinality of a clique of G.Anindependent set of Gis a subset of pairwise non-adjacent vertices and the independence number of G, denoted by α(G),isthe maximum cardinality of an independent set of G. For undefined terms we refer the reader to [42]. For every integer n≥1, let [n]={1,2,...,n}. We denote by Pnthe path of order nwith vertex set [n]and edges ijwith j=i+1 and i∈[n−1], and by Cnthe cycle of order n,n≥3, with vertex set [n]and the same edge set as Pntogether with the edge 1n. Also, for every r,s≥3, we denote by K1,rthe star on r+1 vertices with vertex set {v}∪[r],vertexvbeing called the center of the star, and edge set {vi:i∈[r]}. Abistar, denoted by K2(r,s), is a graph obtained by joining the centers of two stars K1,r−1and K1,s−1. 2 Distance-Equalizer Sets and Equidistant Dimension Let x,y,w be vertices of a graph G. We say that wis equidistant from xand y if d(x,w) =d(y,w). A subset Sof vertices is called a distance-equalizer set for Gif for every two distinct vertices x,y∈V(G)\Sthere exists a vertex w∈S equidistant from xand y.Theequidistant dimension of G, denoted by eqdim(G), is the minimum cardinality of a distance-equalizer set of G. For example, if vis a universal vertex of a graph G, then S={v}is a minimum distance-equalizer set of G, and so eqdim(G)=1. Also, a distance-equalizer set of P8is shown in Fig. 1, and it can be easily checked that P8has no distance-equalizer set of size at most 4, so eqdim(P8)=5. The following results are immediate but make it easier to prove subsequent results. Lemma 1 Let G be a graph. If S is a distance-equalizer set of G and vis a support vertex of G, then S contains vor all leaves adjacent to v. Consequently, eqdim(G)≥| {v∈V(G):vis a support vertex}|. Proof No vertex is equidistant from a leaf and its support vertex, since every path from a leaf to any other vertex goes through its support vertex. Hence, if vis not in S, then all leaves hanging from vmust be in S. 123 1760 A. González et al. Recall that a graph Gis bipartite whenever V(G)can be partitioned into two independent sets, say A,B, which are called its partite sets. Proposition 1 Let G be a bipartite graph with partite sets A and B. If S is a distanceequalizer set of G, then A ⊆SorB⊆S. Consequently, eqdim(G)≥min{|A|,|B|}. Proof The distance between two vertices in the same partite set is even, while the distance between vertices of different partite sets is odd. Hence, there is no vertex equidistant from two vertices belonging to different partite sets. Therefore, A⊆Sor B⊆S. If Gis a graph of order n, with n≥2, then any set of vertices of cardinality n−1 is obviously a distance-equalizer set. Hence, n−1 is an immediate upper bound on the equidistant dimension of nontrivial graphs. We next prove some upper bounds involving classical graph parameters. Proposition 2 For every graph G of order n ≥2, the following statements hold. (i) eqdim(G)≤n−Δ(G)and the bound is tight if Δ(G)≥n/2; (ii) eqdim(G)≤n−ω(G),ifGKn, and the bound is tight if ω(G)≤n/2; (iii) eqdim(G)≤n(D(G)−1)+1 D(G), and the bound is tight if D(G)=2; (iv) eqdim(G)≤n−α(G), whenever D(G)=2, and the bound is tight if α(G)≥ n/2. Proof (i) Let vbeavertexofdegreeΔ(G). It is easy to see that the set S=V(G)\N(v) is a distance-equalizer set of cardinality n−Δ(G), and so eqdim(G)≤n−Δ(G). To prove tightness, let Ha,bwith a≥1 and 0 ≤b<abe the graph with vertex set {v,v1,...,v a,u1,...,ub}and edge set {vvi:i∈[a]} ∪ {viui:i∈[b]}. This graph has order a+b+1 and maximum degree a,soeqdim(Ha,b)≤ b+1 as we have just seen. Moreover, this graph is bipartite with partite sets A={v, u1,...,ub}and B={v1,...,v a}, and so by Proposition 1we have that eqdim(Ha,b)≥min{|A|,|B|} = b+1 since b<a. Hence, Ha,bis a graph of order a+b+1 and maximum degree a, with a≥a+b+1 2and eqdim(Ha,b)=b+1, showing that the given the bound is tight. (ii) Suppose that Gis a non complete graph of order n.LetWbe a clique of maximum size ω(G). Thus, |W|=ω(G)<n. Since Gis connected, there is at least one vertex u/∈Wadjacent to a vertex w∈W. Hence, Δ(G)≥deg(w) ≥|W|= ω(G)and, by item (i), eqdim(G)≤n−Δ(G)≤n−ω(G). To prove that the bound is tight for ω(G)≤n/2, consider for example the graph Gr,sof order n=r+s, for every r≥2 and 1 ≤s≤r, obtained by attaching a leaf to svertices of a complete graph of order r. Then, by Lemma 1,eqdim(Gr,s)≥s. Since the set formed by all except one leaves together with the support vertex of the remaining leaf is a distance-equalizer set, we have eqdim(Gr,s)=s=n−r= n−ω(Gr,s). (iii) Let vbe a vertex of Gfor which there exists another vertex at distance D(G).For every i∈[D(G)],letVibe the set of vertices at distance ifrom v, and observe that all vertices in Viare equidistant from v. Also, there must exist a set Vi0, with 123 The Equidistant Dimension of Graphs 1761 1≤i0≤D, having at least n−1 D(G)vertices. Therefore, V(G)\Vi0is a distanceequalizer set, and consequently eqdim(G)≤n−n−1 D(G)=n(D(G)−1)+1 D(G). To prove that the bound is tight, consider the complete bipartite graph Kr,r, for every r≥2. These graphs have diameter 2 and, as we will see later, eqdim(Kr,r)=r. Hence, eqdim(Kr,r)=r=2r(2−1)+1 2. (iv) Let Wbe an independent set of cardinality α(G). Then, the set S=V\Wis a distance-equalizer set. Indeed, note that the vertices not in Sare the vertices in W.Ifv,w ∈W, then d(v, w) =2, because v,ware not adjacent and D(G)=2. Hence, there is a vertex u/∈Wsuch that d(u,v) =d(u,w) =1. Thus, Sis a distance-equalizer set and we obtain eqdim(G)≤|S|=n−α(G). Finally, consider any complete bipartite graph Kr,s, with s≥r. Then, Kr,shas order n=r+s, the independence number is α(Kr,s)=sand, as we will see later, eqdim(Kr,s)=r. Hence, eqdim(Kr,s)=n−α(Kr,s).  The bound given in Proposition 2(i) is not tight for all values of Δ(G)and n,for example when Δ(G)=2 and n≥7. Indeed, the only graphs satisfying Δ(G)=2 are paths and cycles and, as it will be seen below, the equidistant dimension of paths and cycles of order n≥7isatmostn−3. 3 Extremal Values In this section we characterize all nontrivial graphs achieving extremal values for the equidistant dimension, concretely, graphs Gof order n≥2 such that eqdim(G)∈ {1,2,n−2,n−1}. We also derive a Nordhaus–Gaddum type bound for the equidistant dimension. Theorem 1 For every graph G of order n ≥2, the following statements hold. (i) eqdim(G)=1if and only if Δ(G)=n−1; (ii) eqdim(G)=2if and only if Δ(G)=n−2. Proof (i) If Δ(G)=n−1, then eqdim(G)≤n−(n−1)=1 by Proposition 2(i), and so eqdim(G)=1. Conversely, if eqdim(G)=1, then there exists a vertex v such that S={v}is a distance-equalizer set of G. We claim that vhas degree n−1. Indeed, suppose on the contrary that there is a vertex unot adjacent to v. Then, since there is at least one vertex wadjacent to v,wehaved(v, w) =1= d(v, u). Hence, {v}is not a distance-equalizer set of G, a contradiction. Therefore, Ghas maximum degree n−1. (ii) If Ghas maximum degree n−2, then eqdim(G)≤n−(n−2)=2 by Proposition 2(i), and eqdim(G)= 1 by item (i). Hence, eqdim(G)=2. Conversely, suppose that eqdim(G)=2 and let S={u,v}be a distance-equalizer set of G. We first prove that N(u)\{v}⊆N(v)\{u}or N(v)\{u}⊆N(u)\{v}. Suppose on the contrary that N(u)\{v}N(v)\{u}and N(v)\{u}N(u)\{v}. Then, there exist vertices x,ysuch that x∈N(u)\{v}and x/∈N(v)\{u},y∈N(v)\{u} and y/∈N(u)\{v}. Thus, vertices x,yverify that d(x,u)=1= d(y,u)and 123 1762 A. González et al. d(y,v) =1= d(x,v), contradicting that Sis a distance-equalizer set. Without loss of generality, we assume N(v)\{u}⊆N(u)\{v}. Next, we prove that V(G)=N[u]∪{v}. Suppose on the contrary that there is avertexz/∈N[u]∪{v}. Thus, d(z,u)≥2 and d(z,v) ≥2. If N(v)\{u}is nonempty, then for any vertex x∈N(v)\{u}we have d(x,u)=1= d(z,u)≥2 and d(x,v)=1= d(z,v)≥2, contradicting that Sis a distance-equalizer set. Otherwise N(v)\{u}is empty, and so vis a leaf with uas its support vertex. Thus, for any y∈N(u)\{v},wehaved(y,u)=1= d(z,u)≥2 and d(y,v) =2= d(z,v) =d(z,u)+1≥3, contradicting again that Sis distanceequalizer. Finally, we have that Δ(G)= n−1 by the preceding item. Hence, v/∈N(u)and eqdim(G)=deg(u)=n−2.  Theorem 2 For any graph G of order n, the following statements hold. (i) If n ≥2, then eqdim(G)=n−1if and only if G is a path of order 2. (ii) If n ≥3, then eqdim(G)=n−2if and only if G ∈{P3,P4,P5,P6,C3,C4,C5}. Proof (i) It is obvious that eqdim(P2)=1. Conversely, if Gis a graph with eqdim(G)=n−1, then Δ(G)=1 by Proposition 2(i), and the only connected graph with maximum degree equal to 1 is the path of order 2. (ii) A straightforward computation shows that the graphs P3,P4,P5,P6,C3,C4, and C5have equidistant dimension equal to the order minus 2. Conversely, if Gis a graph with eqdim(G)=n−2, then Δ(G)≤2 by Proposition 2(i). As we have seen above, the path of order 2 is the only connected graph with maximum degree 1. Hence, Δ(G)=2, that is, Gis a path or a cycle of order at least 3. It is easy to see that in both cases the set [n]\{1,3,7}is a distance-equalizer set whenever n≥7, and so eqdim(G)≤n−3buteqdim(G)=n−2. Therefore, 3 ≤ n≤6 and consequently G∈{P3,P4,P5,P6,C3,C4,C5}since eqdim(C6)= 3= 6−2.  Corollary 1 If G is a graph of order n ≥7, then 1≤eqdim(G)≤n−3. Now, we provide a Nordhaus–Gaddum type bound on the equidistant dimension. Nordhaus–Gaddum type inequalities establish bounds on the sum of a parameter for a graph and its complement. Recall that the complement of a graph G, denoted by G, is the graph on the same vertices as Gand two vertices are adjacent in Gif and only if they are not adjacent in G. Also, a graph Gis doubly connected if both Gand G are connected. Note that nontrivial doubly connected graphs have order at least 4. The following result is a direct consequence of Proposition 2(i). Proposition 3 If G is a doubly connected graph, then eqdim(G)≤δ(G)+1. Theorem 3 If G is a doubly connected graph of order n ≥4, then 4≤eqdim(G)+ eqdim(G)≤n+1.Moreover, these bounds are tight. 123 The Equidistant Dimension of Graphs 1763 Proof First observe that a graph Gsatisfying eqdim(G)=1 is not doubly connected. Indeed, in such a case, by Theorem 1(i), it contains a universal vertex vthat is an isolated vertex in G. Hence, eqdim(G)≥2 and eqdim(G)≥2, whenever Gis doubly connected, and the lower bound follows. The family of bistars G=K2(2,n−2), n≥4, provides examples of graphs attaining the lower bound for every n≥4. As we will see in Theorem 4(iii) below, these graphs satisfy eqdim(G)=2, and it is easy to check that eqdim(G)=2. The upper bound is a direct consequence of Propositions 2(i) and 3, because eqdim(G)+eqdim(G)≤n−Δ(G)+δ(G)+1≤n+1. The cycle C5attains the upper bound, since C5=C5and, by Theorem 2(ii), eqdim(C5)=3.  4 Equidistant Dimension of Some Families of Graphs In this section we study the equidistant dimension of some families of graphs, concretely of complete, complete bipartite and complete multipartite graphs, bistars, paths, cycles, and Johnson graphs. 4.1 Complete Graphs, Complete Multipartite Graphs, and Bistars Recall that, for every positive integer n,thecomplete graph Knis the graph of order nin which every pair of vertices is connected by an edge. Also, the complete bipartite graph Kr,s, with r,spositive integers, is the bipartite graph with partite sets A,B such that |A|=rand |B|=s, and edge set given by all pairs vuwith v∈Aand u∈B. More generally, a complete p-partite graph, denoted by Kn1,...,np, is a graph with set of vertices A1∪···∪Apsuch that A1,...,Ap, which are called its partite sets, are pairwise disjoint, verify |Ai|=ni≥1, and two vertices are adjacent if and only if they belong to Aiand Aj, respectively, with i= j. Note that complete bipartite graphs are thus 2-partite graphs. Theorem 4 Let n,r,s,p,n1,...,npbe positive integers such that n ≥2,s ≥r, p≥3and np≥···≥n1≥1. Then, the following statements hold. (i) eqdim(Kn)=1; (ii) eqdim(Kr,s)=r; (iii) eqdim(K2(r,s)) =r; (iv) eqdim(Kn1,...,np)=min{n1,3}. Proof (i) It is a direct consequence of Theorem 1(i). (ii) By Proposition 1,eqdim(Kr,s)≥r. Since both partite sets of Kr,sare distanceequalizer sets, we have eqdim(Kr,s)=r. (iii) Note that K2(r,s)is a bipartite graph with partite sets of cardinality rand s. Hence, by Proposition 1,eqdim(K2(r,s)) ≥r. Moreover, if Ais the partite set 123 1764 A. González et al. of cardinality r, then Ais a distance-equalizer set because it contains a vertex at distance 1 from every vertex not in A. (iv) If n1=1, then Kn1,...,nphas a universal vertex and eqdim(Kn1,...,np)=1, by Theorem 1(i). If n1=2, then Kn1,...,nphas maximum degree equal to the order minus 2 and eqdim(Kn1,...,np)=2, by Theorem 1(ii). Otherwise n1≥3, and so the maximum degree of Kn1,...,npis at most the order minus 3 and eqdim(Kn1,...,np)≥3, by Theorem 1. Moreover, it is very easy to verify that any set consisting of 3 vertices from different partite sets is distance-equalizer. Thus, we conclude that eqdim(Kn1,...,np)=3.  4.2 Paths We next show that distance-equalizer sets and the equidistant dimension of paths are related to 3-AP-free sets and the function r(n)introduced by Erdös and Turán [23]. A subset S⊆[n]is 3-AP-free if a+c= 2b, for every distinct terms a,b,c∈S.The largest cardinality of a 3-AP-free subset of [n]is denoted by r(n). We begin by introducing some preliminary results. A subset of [n]is called evensum if all its elements have the same parity. Proposition 4 Let S ⊆[n]for some integer n. Then, S is a distance-equalizer set of Pnif and only if [n]\S is a 3-AP-free even-sum set. Proof Let us denote by Athe set of vertices of Pnlabeled with even numbers and by Bthe set of vertices labeled with odd numbers. (Note that Pnis a bipartite graph and A,Bare its partite sets). Also, let Sbe a distance-equalizer set of Pnwith |S|=r. By Proposition 1, either A⊆Sor B⊆S. Thus, if T=[n]\S={t1,...,tn−r}, then t1,...,tn−rhave the same parity, that is, Tis an even-sum set. Moreover, (ti+tj)/2 is the only vertex of Pnequidistant from tiand tj. Hence (ti+tj)/2∈S, that is, (ti+tj)/2/∈T. Then, Tis a 3-AP-free set. Conversely, suppose that T={t1,...,tn−r} is a 3-AP-free even-sum set. Then, for all pair of vertices ti,tjof T,wehave(ti+tj)/2∈ [n]\T. Hence, S=[n]\Tis a distance-equalizer set of Pn. Corollary 2 For every positive integer n, it holds that eqdim(Pn)=n−max{|T|:T is a 3-AP-free even-sum subset of [n]}. Proposition 5 [19]Let k1,...,kr,n be different positive integers. Then, one of the sets {2k1−1,2k2−1,...,2kr−1}or {2k1,2k2,...,2kr}is a 3-AP-free even-sum set of [n]if and only if {k1,...,kr}is a 3-AP-free subset of n/2. The equidistant dimension of a path is derived from the results above. Theorem 5 For every positive integer n, it holds that eqdim(Pn)=n−rn 2. 123 The Equidistant Dimension of Graphs 1765 Hence, obtaining the equidistant dimension of paths amounts to computing the function r(n), which has been widely studied [5,7–9,22,25,27,29,37–39]. In fact, many papers are devoted to obtain the values of r(n)in some specific cases (n≤23 and n=41 [23]; n≤27 and 41 ≤n≤43 [39]; n≤123 [21]), which allows us to compute eqdim(Pn)in all those cases (see Table 1for n≤20 and n=50). Also, other works [5,21,37] provide bounds on r(n)that are useful to approach eqdim(Pn), such as n1−c/√log n<r(n)< cn log log n. Besides its relationship with the function r(n), the equidistant dimension of paths is also related to a problem concerning covering squares of a chessboard by queens proposed by Cockayne and Hedetniemi [19]. Indeed, the authors are interested in determining the minimum number of queens needed to be placed on the major diagonal of a chessboard in order to reach all the remaining squares with a single chess movement. More formally, a subset K⊆[n]is a diagonal dominating set if its |K|queens placed in position {(k,k)|k∈K}on the black major diagonal of an n×nchessboard cover the entire board. The minimum cardinality of a diagonal dominating set is denoted by diag(n).Itisprovedin[19] that diagonal dominating sets are precisely the complements of 3-AP-free even-sum sets, which combined with Proposition 4leads us to see that the distance-equalizer sets of Pnare the diagonal dominating sets in [n], and consequently eqdim(Pn)=diag(n). Finally, we do not know the exact value of the equidistant dimension of trees. However, in this family of graphs, it looks that paths are those graphs needing more vertices to construct a distance-equalizer set. Indeed, it is easily seen that, for every pair of vertices of a path, there is at most one equidistant vertex. Hence, we believe that the following conjecture holds true. Conjecture 1 If T is a tree of order n,then eqdim(T)≤eqdim(Pn). 4.3 Cycles In this section, the equidistant dimension of cycles of even order is completely determined, while for cycles of odd order, lower and upper bounds in terms of r(n)are given. Theorem 6 For every positive integer n ≥3, the following statements hold. (i) eqdim(Cn)=⎧ ⎨ ⎩ n 2,for n even, n ≡ 0mod 4; 3n 4−1,for n even, n ≡0mod 4. (ii) n−1 2≤eqdim(Cn)≤n−rn+1 4,for n odd. Proof Throughout this proof, for every i,j∈[n], we use the expression i+j+n 2to represent the only integer in [n]modulo nwhenever i+j+n 2is an integer. Thus, for 123 1772 A. González et al. Fig. 4 The graph G3 σ(n):= min{dim(G)+eqdim(G):|V(G)|=n}. Proposition 8 For every integer n ≥4, the following statements hold. (i) Σ(n)≥3n 2−3; (ii) σ(n)≤log2(n)+2. Proof (i) Consider the complete bipartite graph G=Kn/2,n/2,forwhich dim(G)=n−2(see[14]), and eqdim(G)=n/2, by Theorem 4(ii). Hence, dim(G)+eqdim(G)=n−2+n/2≥3n/2−3. (ii) For every k≥1, consider the graph Gk, with V(Gk)=A∪B∪C, where A={v},B={1,...,k},C={w:wis a binary word of length k}and two different vertices xand yare adjacent in Gkif and only if one of the following conditions hold (see an example in Fig. 4): •one of the vertices is v; •one of the vertices belongs to C,sayx=w∈C, and the other one belongs to B, say y=j∈B, and whas the digit 1 in the jth position. Then, Gkis a graph of order n=2k+k+1. Moreover, Ais a distance-equalizer set since vis a universal vertex, and it is easy to check that A∪Bis a resolving set. Hence, dim(Gk)+eqdim(Gk)≤k+2≤log2(n)+2.  6 Conclusions and Open Problems In this paper, the notion of equidistant dimension as a parameter to evaluate sameness in graphs is introduced. The value of this invariant in several families of graphs and relations with other parameters has been provided. In Table 2, the equidistant dimension, metric dimension and minimum cardinality of doubly resolving sets of some families of graphs are given. Also, all graphs reaching some extremal values of the equidistant dimension have been characterized. As future work, besides solving Conjecture 1about the equidistant dimension of trees, and Conjecture 2about the relation of the equidistant dimension with doubly 123 The Equidistant Dimension of Graphs 1773 Table 2 Equidistant dimension and related parameters of some families of graphs G Constraints eqdim(G)dim(G)ψ(G) Pnn≥2n−rn 2 12 n=4k≥43n 4−123 Cnn=4k+2≥6n 223 n=2k+1≥5≤n−rn+1 4 22 Knn≥31n−1n−1 Kr,s2≤r≤s=n−rrn−2n−2 K1,n−1n≥41n−2n−1 K2(r,s)3≤r≤s=n−rrn−4n−2 Kn1,...,npp≥3, n1+···+np=nmin{3,n1,...,np}n−pn−p resolving sets, it would be interesting to relate distance-equalizer sets to other types of sets of vertices such as dominating sets, cut sets or determining sets, for example. Also, it could be of interest to find other graph families whose equidistant dimension connects with other problems, thus producing similar results as the relationship between the computation of this parameter in paths and AP-3-free sequences. Finally, we could perform new techniques that allow us to compute exact values for the equidistant dimension of Johnson graphs. Acknowledgements A. González is supported by “VI Plan Propio de Investigación y Transferencia” of the Universidad de Sevilla (Spain) and by the Research Group in Mathematics Education FQM-226 of the Junta de Andalucía (Spain). C. Hernando and M. Mora are supported by project PID2019-104129GB- I00/AEI/10.13039/501100011033 of the Spanish Ministry of Science and Innovation and by project Gen. Cat. DGR 2017SGR1336. M. Mora is also supported by project H2020-MSCA-RISE project 734922 - CONNECT. Funding Open Access funding provided thanks to the CRUE-CSIC agreement with Springer Nature. Open Access This article is licensed under a Creative Commons Attribution 4.0 International License, which permits use, sharing, adaptation, distribution and reproduction in any medium or format, as long as you give appropriate credit to the original author(s) and the source, provide a link to the Creative Commons licence, and indicate if changes were made. The images or other third party material in this article are included in the article’s Creative Commons licence, unless indicated otherwise in a credit line to the material. If material is not included in the article’s Creative Commons licence and your intended use is not permitted by statutory regulation or exceeds the permitted use, you will need to obtain permission directly from the copyright holder. To view a copy of this licence, visit http://creativecommons.org/licenses/by/4.0/. References 1. Alspach, B.: Johnson graphs are Hamilton-connected. Ars Math. Contemp. 6, 21–23 (2013) 2. Aslam, M., Ali, A.: Some results on induced subgraphs of Johnson graphs. Int. Math. Forum 7(9–12), 445–454 (2012) 3. Bailey, R.F., Cáceres, J., Garijo, D., González, A., Márquez, A., Meagher, K., Puertas, M.L.: Resolving sets for Johnson and Kneser graphs. Eur. J. Comb. 34(4), 736–751 (2013) 123 1774 A. González et al. 4. Bautista-Santiago, C., Cano, J., Fabila-Monroy, R., Flores-Peñaloza, D., González-Aguilar, H., Lara, D., Sarmiento, E., Urrutia, J.: On the connectedness and diameter of a geometric Johnson graph. Discrete Math. Theor. Comput. Sci. 15(3), 21–30 (2013) 5. Behrend, F.A.: On sets of integers which contain no three in arithmetic progression. Proc. Natl. Acad. Sci. 23, 331–332 (1946) 6. Bitan, S., Etzion, T.: On the chromatic number, colorings, and codes of the Johnson graph. Discrete Appl. Math. 70(2), 163–175 (1996) 7. Bloom, T.F.: A quantitative improvement for Roth’s theorem on arithmetic progressions. J. Lond. Math. Soc. Second Ser. 93(3), 643–663 (2016) 8. Bloom, T.F., Sisask, O.: Logarithmic bounds for Roths theorem via almost-periodicity. Discrete Anal. 4, 20 (2019) 9. Bourgain, J.: On triples in arithmetic progression. Geom. Funct. Anal. 9(5), 968–984 (1999) 10. Cáceres, J., Hernando, C., Mora, M., Pelayo, I.M., Puertas, M.L., Seara, C.: On the metric dimension of infinite graphs. Discrete Appl. Math. 160(18), 2618–2626 (2012) 11. Cáceres, J., Hernando, C., Mora, M., Pelayo, I.M., Puertas, M.L., Seara, C., Wood, D.R.: On the metric dimension of Cartesian products of graphs. SIAM J. Discrete Math. 21(2), 423–441 (2007) 12. ˇ Cangalovi´c, M., Kratica, J., Vujˇciˇc, V.K., Stojanoviˇc, M.: Minimal double resolving sets of prism graphs. Optimization 62(8), 1037–1043 (2013) 13. Casas-Roma, J., Herrera-Joancomartí, J., Torra, V.: A survey of graph-modification techniques for privacy-preserving on networks. Artif. Intell. Rev. 47(3), 341–366 (2017) 14. Chartrand, G., Eroh, L., Johnson, M.A., Oellermann, O.R.: Resolvability in graphs and the metric dimension of a graph. Discrete Appl. Math. 105, 99–113 (2000) 15. Chen, X., Wang, C.: Approximability of the minimum weighted doubly resolving set problem. Comput. Comb. LNCS 8591, 357–368 (2014) 16. Chester, S., Srivastava, G.: Social network privacy for attribute disclosure attacks. In: 2011 International Conference on Advances in Social Networks Analysis and Mining, pp. 445–449. IEEE (2011) 17. Chester, S., Kapron, B.M., Srivastava, G., Venkatesh, S.: Complexity of social network anonymization. Soc. Netw. Anal. Min. 3(2), 151–166 (2013) 18. Claverol, M., García, A., Hernández, G., Hernando, C., Maureso, M., Mora, M., Tejel, J.: Metric dimension of maximal outerplanar graphs. Bull. Malays. Math. Sci. Soc. 44(4), 2603–2630 (2021) 19. Cockayne, E.J., Hedetniemi, S.T.: On the diagonal queens domination problem. J. Comb. Theory Ser. A42(1), 137–139 (1986) 20. Dabrowski, A., Moss, L.S.: The Johnson graphs satisfy a distance extension property. Combinatorica 20(2), 295–300 (2000) 21. Dybizba´nski, J.: Sequences containing no 3-term arithmetic progressions. Electron. J. Comb. 19(2), P15 (2012) 22. Elkin, M.: An improved construction of progression-free sets. Isr. J. Math. 184, 93–128 (2011) 23. Erdös, P., Turán, P.: On some sequences of integers. J. Lond. Math. Soc. 11, 261–264 (1936) 24. Feder, T., Nabar, S., Terzi, E.: Anonymizing graphs (2008). CoRR arXiv:0810.5578 25. Gasarch, W., Glenn, J., Kruskal, C.: Finding large 3-free sets. I. The small n case. J. Comput. Syst. Sci. 74(4), 628–655 (2008) 26. González, A., Hernando, C., Mora, M.: Metric-locating-dominating sets of graphs for constructing related subsets of vertices. Appl. Math. Comput. 332, 449–456 (2018) 27. Gowers, W.: A new proof of Szeméredi’s theorem. Geom. Funct. Anal. 11, 465–588 (2001) 28. Harary, F., Melter, R.A.: On the metric dimension of a graph. Ars Comb. 2, 191–195 (1976) 29. Heath-Brown, D.R.: Integer sets containing no arithmetic progressions. J. Lond. Math. Soc. (2) 35, 385–394 (1987) 30. Hernando, C., Mora, M., Pelayo, I.M., Seara, C., Wood, D.R.: Extremal graph theory for metric dimension and diameter. Electron. J. Comb. 17, R30 (2010) 31. Jiang, J., Wen, S., Yu, S., Xiang, Y., Zhou, W.: Identifying propagation sources in networks: state-of- the-art and comparative studies. IEEE Commun. Surv. Tutor. 19(1), 465–481 (2017) 32. Kratica, J., ˇ Cangalovi´c, M., Kovaˇcevi´c-Vujˇci´c, V.: Computing minimal doubly resolving sets of graphs. Comput. Oper. Res. 36(7), 2149–2159 (2009) 33. Kratica, J., Kovaˇcevi´c-Vujˇci´c, V., ˇ Cangalovi´c, M., Stojanovi´c, M.: Minimal doubly resolving sets and the strong metric dimension of some convex polytopes. Appl. Math. Comput. 218(19), 9790–9801 (2012) 123 The Equidistant Dimension of Graphs 1775 34. Krebs, M., Shaheen, A.: On the spectra of Johnson graphs. Electron. J. Linear Algebra 17, 154–167 (2008) 35. Lobstein, A.: Watching systems, identifying, locating-dominating and discriminating codes in graphs. http://www.infres.enst.fr/lobstein/debutBIBidetlocdom.pdf 36. Ramras, M., Donovan, E.: The automorphism group of a Johnson graph. SIAM J. Discrete Math. 25, 267–270 (2011) 37. Roth, K.F.: On certain sets of integers. J. Lond. Math. Soc. 28(1), 104–109 (1953) 38. Sanders, T.: On Roth’s theorem on progressions. Ann. Math. (2) 174(1), 619–636 (2011) 39. Sharma, A.: Sequences of integers avoiding 3-term arithmetic progressions. Electron. J. Comb. 19, P27 (2012) 40. Slater, P.J.: Leaves of trees. Congr. Numer. 14, 549–559 (1975) 41. Trujillo-Rasua, R., Yero, I.G.: k-metric antidimension: a privacy measure for social graphs. Inf. Sci. 328, 403–417 (2016) 42. West, D.B.: Introduction to Graph Theory, Second Edition Prentice Hall, Upper Saddle River (2001) 43. Zheleva, E., Getoor, L.: Privacy in social networks: a survey. In: Aggarwal, C.C. (ed.) Social Network Data Analytics, 1st edn., pp. 277–306. Springer, Berlin (2011) 44. Zhou, B., Pei, J., Luk, W.S.: A brief survey on anonymization techniques for privacy preserving publishing of social network data. SIGKDD Explor. Newsl. 10(2), 12–22 (2008) Publisher’s Note Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations. 123