The Equidistant Dimension of Graphs

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 S such 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, locating-dominating 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,32,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 A is a 2-antiresolving set if, for every vertex \(v\notin A\), there exists another different vertex \(w\notin A\) such that v and w have the same vector of distances to the vertices of A. The 2-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 3 is devoted to characterize all graphs attaining some extremal values of the equidistant dimension. In Sect. 4 we 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 G are denoted by V(G) and E(G), respectively.

The order of G is |V(G)|. For any vertex \(v\in V(G)\), its open neighborhood is the set \(N(v) = \{w \in V(G) : vw \in E(G)\}\) and its closed neighborhood is \( N[v] = N(v)\cup \{v\}\).

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 v is a leaf, in which case the only vertex adjacent to v is called its support vertex.

When \(\deg (v)=|V(G)|-1\), we say that v is universal. The maximum degree of G is \(\varDelta (G) = \text {max} \ \{\text {deg}(v) : v \in V(G)\}\) and its minimum degree is \(\delta (G) = \text {min} \ \{\text {deg}(v) : v \in V(G)\}\). The distance between two vertices \(v,w \in V(G)\) is denoted by d(v, w), and the diameter of G is \(D(G) =\text { max} \{d(v,w) : v,w \in V(G)\}\). A clique is a subset of pairwise adjacent vertices and the clique number of G, denoted by \(\omega (G)\), is the maximum cardinality of a clique of G. An independent set of G is a subset of pairwise non-adjacent vertices and the independence number of G, denoted by \(\alpha (G)\), is the maximum cardinality of an independent set of G. For undefined terms we refer the reader to [42].

For every integer \(n\ge 1\), let \([n]=\{1,2,\dots ,n\}\). We denote by \(P_n\) the path of order n with vertex set [n] and edges ij with \(j=i+1\) and \(i\in [n-1]\), and by \(C_n\) the cycle of order n, \(n\ge 3\), with vertex set [n] and the same edge set as \(P_n\) together with the edge 1n. Also, for every \(r,s\ge 3\), we denote by \(K_{1,r}\) the star on \(r+1\) vertices with vertex set \(\{v\} \cup [r]\), vertex v being called the center of the star, and edge set \(\{vi: i\in [r]\}\). A bistar, denoted by \(K_2(r,s)\), is a graph obtained by joining the centers of two stars \(K_{1,r-1}\) and \(K_{1,s-1}\).

Let x, y, w be vertices of a graph G. We say that w is equidistant from x and y if \(d(x,w)=d(y,w)\). A subset S of vertices is called a distance-equalizer set for G if for every two distinct vertices \(x,y\in V(G){\setminus } S\) there exists a vertex \(w \in S\) equidistant from x and y. The equidistant dimension of G, denoted by eqdim(G), is the minimum cardinality of a distance-equalizer set of G. For example, if v is 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 \(P_8\) is shown in Fig. 1, and it can be easily checked that \(P_8\) has no distance-equalizer set of size at most 4, so \(eqdim(P_8)=5\).

Black vertices form a distance-equalizer set of minimum size for \(P_8\)

Full size image

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 v is a support vertex of G, then S contains v or all leaves adjacent to v.

Consequently,

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 v is not in S, then all leaves hanging from v must be in S. \(\square \)

Recall that a graph G is 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 distance-equalizer set of G, then \(A\subseteq S\) or \(B\subseteq S\). Consequently, \(eqdim(G)\ge min\{\vert A \vert , \vert B \vert \}.\)

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\subseteq S\) or \(B\subseteq S\). \(\square \)

If G is a graph of order n, with \(n\ge 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\ge 2\), the following statements hold.

1. (i)

   \(eqdim(G)\le n-\varDelta (G)\) and the bound is tight if \(\varDelta (G) \ge n/2\);

2. (ii)

   \(eqdim(G)\le n- \omega (G)\), if \(G\not \cong K_n\), and the bound is tight if \(\omega (G) \le n/2\);

3. (iii)

   \(eqdim(G)\le \frac{n(D(G)-1) +1}{D(G)}\), and the bound is tight if \(D(G)=2\);

4. (iv)

   \(eqdim(G)\le n- \alpha (G)\), whenever \(D(G)=2\), and the bound is tight if \(\alpha (G) \ge n/2\).

Proof

1. (i)

   Let v be a vertex of degree \(\varDelta (G)\). It is easy to see that the set \(S=V(G){\setminus } N(v)\) is a distance-equalizer set of cardinality \(n-\varDelta (G)\), and so \(eqdim(G)\le n-\varDelta (G)\).

   To prove tightness, let \(H_{a,b}\) with \(a\ge 1\) and \(0\le b< a\) be the graph with vertex set \(\{v, v_1, \ldots , v_a,u_1,\ldots ,u_b\}\) and edge set \(\{vv_i: i\in [a]\}\cup \{v_iu_i: i\in [b]\}\). This graph has order \(a+b+1\) and maximum degree a, so \(eqdim (H_{a,b})\le b +1 \) as we have just seen. Moreover, this graph is bipartite with partite sets \(A=\{v,u_1,\ldots , u_b\}\) and \(B=\{v_1,\ldots ,v_a\}\), and so by Proposition 1 we have that \(eqdim (H_{a,b})\ge min\{\vert A \vert , \vert B \vert \} = b +1 \) since \(b<a\). Hence, \(H_{a,b}\) is a graph of order \(a+b+1\) and maximum degree a, with \(a\ge \frac{a+b+1}{2}\) and \(eqdim (H_{a,b})= b +1 \), showing that the given the bound is tight.

2. (ii)

   Suppose that G is a non complete graph of order n. Let W be a clique of maximum size \(\omega (G)\). Thus, \(|W|=\omega (G)<n\). Since G is connected, there is at least one vertex \(u\notin W\) adjacent to a vertex \(w\in W\). Hence, \(\varDelta (G)\ge \deg (w)\ge |W|=\omega (G)\) and, by item (i), \(eqdim (G)\le n-\varDelta (G)\le n-\omega (G)\).

   To prove that the bound is tight for \(\omega (G)\le n/2\), consider for example the graph \(G_{r,s}\) of order \(n=r+s\), for every \(r\ge 2\) and \(1\le s\le r\), obtained by attaching a leaf to s vertices of a complete graph of order r. Then, by Lemma 1, \(eqdim(G_{r,s})\ge 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(G_{r,s})=s=n-r=n-\omega (G_{r,s})\).

3. (iii)

   Let v be a vertex of G for which there exists another vertex at distance D(G). For every \(i\in [D(G)]\), let \(V_i\) be the set of vertices at distance i from v, and observe that all vertices in \(V_i\) are equidistant from v. Also, there must exist a set \(V_{i_0}\), with \(1\le i_0\le D\), having at least \(\frac{n-1}{D(G)}\) vertices. Therefore, \(V(G){\setminus } V_{i_0}\) is a distance-equalizer set, and consequently \(eqdim(G)\le n-\frac{n-1}{D(G)}=\frac{n(D(G)-1)+1}{D(G)}\).

   To prove that the bound is tight, consider the complete bipartite graph \(K_{r,r}\), for every \(r\ge 2\). These graphs have diameter 2 and, as we will see later, \(eqdim(K_{r,r})=r\). Hence, \(eqdim(K_{r,r})=r=\lfloor \frac{2r(2-1) +1}{2} \rfloor \).

4. (iv)

   Let W be an independent set of cardinality \(\alpha (G)\). Then, the set \(S=V{\setminus } W\) is a distance-equalizer set. Indeed, note that the vertices not in S are the vertices in W. If \(v,w\in W\), then \(d(v,w)=2\), because v,w are not adjacent and \(D(G)=2\). Hence, there is a vertex \(u\notin W\) such that \(d(u,v)=d(u,w)=1\). Thus, S is a distance-equalizer set and we obtain \(eqdim(G)\le |S|=n- \alpha (G)\).

   Finally, consider any complete bipartite graph \(K_{r,s}\), with \(s\ge r\). Then, \(K_{r,s}\) has order \(n=r+s\), the independence number is \( \alpha (K_{r,s})=s\) and, as we will see later, \(eqdim(K_{r,s})=r\). Hence, \(eqdim(K_{r,s})=n-\alpha (K_{r,s})\).

\(\square \)

The bound given in Proposition 2(i) is not tight for all values of \(\varDelta (G) \) and n, for example when \(\varDelta (G)=2\) and \(n\ge 7\). Indeed, the only graphs satisfying \(\varDelta (G) = 2\) are paths and cycles and, as it will be seen below, the equidistant dimension of paths and cycles of order \(n\ge 7\) is at most \(n-3\).

In this section we characterize all nontrivial graphs achieving extremal values for the equidistant dimension, concretely, graphs G of order \(n\ge 2\) such that \(eqdim (G)\in \{ 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\ge 2\), the following statements hold.

1. (i)

   \(eqdim(G)=1\) if and only if \(\varDelta (G)=n-1\);

2. (ii)

   \(eqdim(G)=2\) if and only if \(\varDelta (G)=n-2\).

Proof

1. (i)

   If \(\varDelta (G)=n-1\), then \(eqdim(G)\le 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 v has degree \(n-1\). Indeed, suppose on the contrary that there is a vertex u not adjacent to v. Then, since there is at least one vertex w adjacent to v, we have \(d(v,w)=1\not =d(v,u)\). Hence, \(\{ v\}\) is not a distance-equalizer set of G, a contradiction. Therefore, G has maximum degree \(n-1\).

2. (ii)

   If G has maximum degree \(n-2\), then \(eqdim(G)\le n-(n-2)=2\) by Proposition 2(i), and \(eqdim(G)\not =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){\setminus } \{ v\}\subseteq N(v){\setminus } \{u\}\) or \(N(v){\setminus } \{ u\}\subseteq N(u){\setminus } \{v\}\). Suppose on the contrary that \(N(u){\setminus } \{ v\}\nsubseteq N(v){\setminus } \{u\}\) and \(N(v){\setminus } \{ u\}\nsubseteq N(u){\setminus } \{v\}\). Then, there exist vertices x, y such that \(x\in N(u){\setminus } \{ v\}\) and \(x\notin N(v){\setminus } \{u\}\), \(y\in N(v){\setminus } \{ u\}\) and \(y\notin N(u){\setminus } \{v\}\). Thus, vertices x, y verify that \(d(x,u)=1\ne d(y,u)\) and \(d(y,v)=1\ne d(x,v)\), contradicting that S is a distance-equalizer set. Without loss of generality, we assume \(N(v){\setminus } \{ u\}\subseteq N(u){\setminus } \{v\}\).

   Next, we prove that \(V(G)=N[u]\cup \{v\}\). Suppose on the contrary that there is a vertex \(z\notin N[u]\cup \{v\}\). Thus, \(d(z,u)\ge 2\) and \(d(z,v)\ge 2\). If \(N(v){\setminus } \{u\}\) is nonempty, then for any vertex \(x\in N(v){\setminus } \{u\}\) we have \(d(x,u)=1\ne d(z,u)\ge 2\) and \(d(x,v)=1\ne d(z,v)\ge 2\), contradicting that S is a distance-equalizer set.

   Otherwise \(N(v){\setminus } \{u\}\) is empty, and so v is a leaf with u as its support vertex. Thus, for any \(y\in N(u){\setminus } \{v\}\), we have \(d(y,u)=1\ne d(z,u)\ge 2\) and \(d(y,v)=2\not = d(z,v)=d(z,u)+1\ge 3\), contradicting again that S is distance-equalizer.

   Finally, we have that \(\varDelta (G) \not = n-1\) by the preceding item. Hence, \(v\notin N(u)\) and \(eqdim (G)=deg(u)=n-2\).

\(\square \)

Theorem 2

For any graph G of order n, the following statements hold.

1. (i)

   If \(n\ge 2\), then \(eqdim(G)=n-1\) if and only if G is a path of order 2.

2. (ii)

   If \(n\ge 3\), then \(eqdim(G)=n-2\) if and only if \(G \in \{P_3,P_4,P_5, P_6, C_3, C_4, C_5\}\).

Proof

1. (i)

   It is obvious that \(eqdim(P_2)=1\). Conversely, if G is a graph with \(eqdim(G)=n-1\), then \(\varDelta (G)=1\) by Proposition 2(i), and the only connected graph with maximum degree equal to 1 is the path of order 2.

2. (ii)

   A straightforward computation shows that the graphs \(P_3\), \(P_4\), \(P_5\), \(P_6\), \(C_3\), \(C_4\), and \(C_5\) have equidistant dimension equal to the order minus 2. Conversely, if G is a graph with \(eqdim(G)=n-2\), then \(\varDelta (G)\le 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, \(\varDelta (G)=2\), that is, G is a path or a cycle of order at least 3.

   It is easy to see that in both cases the set \([n]{\setminus } \{ 1,3,7\}\) is a distance-equalizer set whenever \(n\ge 7\), and so \(eqdim (G)\le n -3\) but \(eqdim(G)=n-2\). Therefore, \(3\le n\le 6\) and consequently \(G\in \{ P_3,P_4,P_5, P_6, C_3,C_4, C_5\}\) since \(eqdim (C_6)=3\not = 6-2\).

\(\square \)

Corollary 1

If G is a graph of order \(n\ge 7\), then \(1\le eqdim(G) \le 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 \(\overline{G}\), is the graph on the same vertices as G and two vertices are adjacent in \(\overline{G}\) if and only if they are not adjacent in G. Also, a graph G is doubly connected if both G and \(\overline{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 ( \overline{G} )\le \delta (G)+1\).

Theorem 3

If G is a doubly connected graph of order \(n\ge 4\), then \(4\le eqdim(G)+eqdim(\overline{G})\le n+1.\) Moreover, these bounds are tight.

Proof

First observe that a graph G satisfying \(eqdim(G)=1\) is not doubly connected. Indeed, in such a case, by Theorem 1(i), it contains a universal vertex v that is an isolated vertex in \(\overline{G}\). Hence, \(eqdim (G)\ge 2\) and \(eqdim (\overline{G})\ge 2\), whenever G is doubly connected, and the lower bound follows. The family of bistars \(G=K_2(2,n-2)\), \(n\ge 4\), provides examples of graphs attaining the lower bound for every \(n\ge 4\). As we will see in Theorem 4(iii) below, these graphs satisfy \(eqdim(G)=2\), and it is easy to check that \(eqdim(\overline{G})=2\).

The upper bound is a direct consequence of Propositions 2(i) and 3, because

The cycle \(C_5\) attains the upper bound, since \(\overline{C_5}=C_5\) and, by Theorem  2(ii), \(eqdim(C_5)=3\). \(\square \)

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, the complete graph \(K_n\) is the graph of order n in which every pair of vertices is connected by an edge. Also, the complete bipartite graph \(K_{r,s}\), with r, s positive integers, is the bipartite graph with partite sets A, B such that \(|A|=r\) and \(|B|=s\), and edge set given by all pairs vu with \(v\in A\) and \(u\in B\). More generally, a complete p-partite graph, denoted by \(K_{n_1,\dots , n_p}\), is a graph with set of vertices \(A_1\cup \dots \cup A_p\) such that \(A_1, \dots ,A_p\), which are called its partite sets, are pairwise disjoint, verify \(|A_i|=n_i\ge 1\), and two vertices are adjacent if and only if they belong to \(A_i\) and \(A_j\), respectively, with \(i\not = j\). Note that complete bipartite graphs are thus 2-partite graphs.

Theorem 4

Let \(n,r,s,p,n_1,\dots , n_p\) be positive integers such that \(n\ge 2\), \(s\ge r\), \(p\ge 3\) and \(n_p\ge \dots \ge n_1\ge 1\). Then, the following statements hold.

1. (i)

   \( eqdim(K_{n})=1\);

2. (ii)

   \( eqdim(K_{r,s})=r\);

3. (iii)

   \( eqdim(K_2 (r,s))=r\);

4. (iv)

   \( eqdim(K_{n_1,\dots , n_p})=\min \{n_1,3\}.\)

Proof

1. (i)

   It is a direct consequence of Theorem 1(i).

2. (ii)

   By Proposition 1, \(eqdim(K_{r,s})\ge r\). Since both partite sets of \(K_{r,s}\) are distance-equalizer sets, we have \(eqdim(K_{r,s})=r\).

3. (iii)

   Note that \(K_2 (r,s)\) is a bipartite graph with partite sets of cardinality r and s. Hence, by Proposition 1, \(eqdim(K_2{(r,s)})\ge r\). Moreover, if A is the partite set of cardinality r, then A is a distance-equalizer set because it contains a vertex at distance 1 from every vertex not in A.

4. (iv)

   If \(n_1=1\), then \(K_{n_1,\dots , n_p}\) has a universal vertex and \(eqdim(K_{n_1,\dots , n_p})=1\), by Theorem 1(i).

   If \(n_1=2\), then \(K_{n_1,\dots , n_p}\) has maximum degree equal to the order minus 2 and \(eqdim(K_{n_1,\dots , n_p})=2\), by Theorem 1(ii).

   Otherwise \(n_1\ge 3\), and so the maximum degree of \(K_{n_1,\dots , n_p}\) is at most the order minus 3 and \(eqdim(K_{n_1,\dots , n_p})\ge 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(K_{n_1,\dots , n_p})=3.\)

\(\square \)

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\subseteq [n]\) is 3-AP-free if \(a+c \ne 2b\), for every distinct terms \(a,b,c \in 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 even-sum if all its elements have the same parity.

Proposition 4

Let \(S\subseteq [n]\) for some integer n. Then, S is a distance-equalizer set of \(P_n\) if and only if \([n] {\setminus } S\) is a 3-AP-free even-sum set.

Proof

Let us denote by A the set of vertices of \(P_n\) labeled with even numbers and by B the set of vertices labeled with odd numbers. (Note that \(P_n\) is a bipartite graph and A, B are its partite sets). Also, let S be a distance-equalizer set of \(P_n\) with \(|S|=r\). By Proposition 1, either \(A \subseteq S\) or \(B \subseteq S\). Thus, if \(T= [n] {\setminus } S=\{t_1, \dots , t_{n-r}\}\), then \(t_1,\dots ,t_{n-r}\) have the same parity, that is, T is an even-sum set. Moreover, \((t_i+t_j)/2\) is the only vertex of \(P_n\) equidistant from \(t_i\) and \(t_j\). Hence \((t_i+t_j)/2 \in S\), that is, \((t_i+ t_j)/2 \notin T\). Then, T is a 3-AP-free set. Conversely, suppose that \(T=\{t_1, \dots , t_{n-r}\}\) is a 3-AP-free even-sum set. Then, for all pair of vertices \(t_i\), \(t_j\) of T, we have \((t_i+t_j)/2 \in [n] {\setminus } T\). Hence, \(S=[n] {\setminus } T\) is a distance-equalizer set of \(P_n\). \(\square \)

Corollary 2

For every positive integer n, it holds that

Proposition 5

[19] Let \( k_1,\ldots , k_r, n\) be different positive integers. Then, one of the sets \(\{2k_1-1,2k_2 -1,\ldots , 2k_r -1\}\) or \(\{2k_1,2k_2,\ldots , 2k_r\}\) is a 3-AP-free even-sum set of [n] if and only if \( \{k_1,\ldots , k_r\}\) is a 3-AP-free subset of \(\Big [ \, \lceil n/2 \rceil \, \Big ]\).

The equidistant dimension of a path is derived from the results above.

Theorem 5

For every positive integer n, it holds that

Hence, obtaining the equidistant dimension of paths amounts to computing the function r(n), which has been widely studied [5, 7,8,9, 22, 25, 27, 29, 37,38,39]. In fact, many papers are devoted to obtain the values of r(n) in some specific cases (\(n\le 23\) and \(n=41\) [23]; \(n\le 27\) and \(41\le n \le 43\) [39]; \(n\le 123\) [21]), which allows us to compute \(eqdim(P_n)\) in all those cases (see Table 1 for \(n\le 20\) and \(n=50\)). Also, other works [5, 21, 37] provide bounds on r(n) that are useful to approach \(eqdim(P_n)\), such as

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 \subseteq [n]\) is a diagonal dominating set if its |K| queens placed in position \(\{(k,k) \, | \, k \in K\}\) on the black major diagonal of an \(n\times n\) chessboard cover the entire board. The minimum cardinality of a diagonal dominating set is denoted by diag(n). It is proved in [19] that diagonal dominating sets are precisely the complements of 3-AP-free even-sum sets, which combined with Proposition 4 leads us to see that the distance-equalizer sets of \(P_n\) are the diagonal dominating sets in [n], and consequently \(eqdim(P_n)=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)\le eqdim(P_n)\).

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 \ge 3\), the following statements hold.

1. (i)

   \(eqdim(C_n)=\left\{ \begin{array}{lll} \frac{n}{2} , &{} \text {for n even,} \ \ n\not \equiv 0 \text { mod }4; \\ \\ \frac{3n}{4}-1, &{} \text {for n even,} \ \ n\equiv 0 \text { mod }4. \\ \end{array} \right. \)

2. (ii)

   \(\frac{n-1}{2}\le eqdim(C_n) \le n-r\left( \Big \lceil \frac{n+1}{4} \Big \rceil \right) , \, \, \text {for n odd.}\)

Proof

Throughout this proof, for every \(i,j\in [n]\), we use the expression \(\frac{i+j+n}{2}\) to represent the only integer in [n] modulo n whenever \(\frac{i+j+n}{2}\) is an integer. Thus, for every pair of vertices i, j of \(C_n\), the vertices equidistant from them are \(\frac{i+j}{2}\) and \(\frac{i+j+n}{2}\), whenever these values are integers. Hence, there is exactly one vertex equidistant from i and j, when n is odd; there is no equidistant vertex from i and j, whenever n is even and i, j have distinct parity; and there are exactly two vertices equidistant from i and j, if n even and i, j have the same parity. Moreover, in this last case, the vertices equidistant from i and j are antipodal.

1. (i)

   Let n be an even integer, and let us denote by A (resp., B) the set of vertices of \(C_n\) labeled with odd (resp., even) numbers. As n is even, \(C_n\) is a bipartite graph and, by Proposition 1, for every distance-equalizer set S, either \(A\subseteq S\) or \(B\subseteq S\). Hence, \(|S|\ge n/2\). We distinguish two subcases.

   1. (a)

      Case \(n\not \equiv 0 \text { mod }4\). We claim that A is a distance-equalizer set (see an example in Fig. 2a). Indeed, for every \(i,j\in [n]{\setminus } A\), the numbers \(\frac{i+j}{2}\) and \(\frac{i+j+n}{2}\) are integers of different parity, because n is even but \(n\not \equiv 0 \text { mod }4\). Thus, either \(\frac{i+j}{2}\) or \(\frac{i+j+n}{2}\) belongs to A. Hence, A is a distance-equalizer set and \(eqdim{(C_n)}=n/2\).

   2. (b)

      Case \(n\equiv 0 \text { mod }4\). Let S be a distance-equalizer set, and let us assume, relabeling the vertices if necessary, that \(A\subseteq S\). Thus, \([n]{\setminus } S\subseteq B\). First, we suppose that there is a pair of antipodal vertices in \([n]{\setminus } S\subseteq B\). We can assume without loss of generality that these vertices are n/2 and n. For every \(i\in \{2,4,\dots ,n/2-2\}\), the only vertices equidistant from i and \(n-i\) are n/2 and n. Since n/2 and n are not in S, we derive that at least one of the vertices i or \(n-i\) must be in S, for every \(i\in \{2,4,\dots ,n/2-2\}\). Therefore, besides the vertices from A, the set S contains at least \(\frac{n/2-2}{2}\) vertices from B. Therefore,

      $$\begin{aligned} eqdim(C_n)\ge \frac{n}{2}+\frac{n/2-2}{2}=\frac{3n}{4}-1. \end{aligned}$$

      It is straightforward that the same bound holds if we suppose that there is no pair of antipodal vertices in \([n]{\setminus } S\subseteq B\).

      Now, we consider the set \(S=[n]{\setminus } \{2,4,6,\dots ,n/2+2\}\) of size \(|S|=\frac{3n}{4}-1\). It is easy to check that every pair of vertices not in S has a vertex in \(\{n/2+3,n/2+4,\dots ,n,1\}\subseteq S\) equidistant from them. Thus, we conclude that S is a distance-equalizer set of minimum cardinality (see an example in Fig. 2b), and so \(eqdim(C_n)= \frac{3n}{4}-1\).

2. (ii)

   Let n be an odd integer, and let S be a distance-equalizer set of minimum size. Since any set of cardinality \(n-1\) is a distance-equalizer set, we can assume without loss of generality that \(n\notin S\). As n is an odd integer, n is the only vertex of \(C_n\) equidistant from each pair of vertices \(i,n-i\), with \(i\in \{1,\dots ,(n-1)/2\}\), and so at least one of them must be in S. Therefore, \(eqdim (C_n)\ge (n-1)/2\).

   To prove the upper bound, let \(S_1=\{ i : (n+1)/2 < i \le n\}\) and consider a distance-equalizer set \(S_2\) of \(P_{(n+1)/2}\). We claim that \(S=S_1 \cup S_2\) is a distance-equalizer set of \(C_n\) (see an example in Fig. 2c). Indeed, any two vertices i, j not in S belong to \([(n+1)/2] \), and there is a vertex in \(S_2\) equidistant from then, since \(S_2\) is a distance-equalizer set of \(P_{(n+1)/2}\). Hence,

   $$\begin{aligned} eqdim(C_n)\le |S_1|+|S_2|=\frac{n-1}{2}+eqdim(P_{\frac{n+1}{2}}) =n-r\left( \Big \lceil \frac{n+1}{4} \Big \rceil \right) . \end{aligned}$$

\(\square \)

The set of black vertices form a distance-equalizer set of the cycles a \(C_{10}\), b \(C_{12}\), and c, d \(C_{13}\). In cases (a, b, d), the given distance-equalizer set has minimum cardinality

Full size image

Note that the distance-equalizer set constructed in the proof of the preceding theorem for odd cycles is not necessarily of minimum cardinality. In Fig. 2c, d, the distance-equalizer set described in the proof of the theorem and a distance-equalizer set of minimum cardinality for \(C_{13}\) are shown.

In Table 1 the values of the equidistant dimension of \(C_n\) for \(n \le 20\) and \(n=50\) are given. Note that some of these values have been obtained with computer.

4.4 Johnson Graphs

Johnson graphs are important because of their connections with other combinatorial structures such as projective planes and symmetric designs [3]. Furthermore, there exist different studies about geometric versions of these graphs because of their multiple applications in network design (see for instance [4]). Due to these facts, among others, properties of Johnson graphs have been widely studied in the literature: spectra [34], induced subgraphs [2], connectivity [1], colorings [6], distances [20], automorphisms [36], and metric dimension [3]. In this subsection we study the equidistant dimension of Johnson graphs, obtaining an upper bound for several cases.

The Johnson graph J(n, k), with \(n>k\ge 1\), has as vertex set the k-subsets of a n-set and two vertices are adjacent if their intersection has size \(k-1\). Thus, it can be easily seen that the distance between any two vertices X, Y is given by

Consequently, a vertex \(U\in V(J(n,k))\) is equidistant from vertices X and Y if and only if \(|U\cap X| = |U\cap Y|.\)

Proposition 6

For any positive integer k, it holds that

whenever \(n\in \{2k-1,2k+1\}\) or \(n > 2k^2\).

Proof

Consider the vertices of J(n, k) as k-subsets of the n-set \(W=\{0,\ldots ,n-1\}\). For each positive integer i, let \(S_i = \{i, i+1, \ldots , i+k-1\}\in V(J(n,k))\) where sums are taken modulo n (thus \(S_{i+rn}=S_i\) for any integer r). We claim that the set \(\mathcal{S} = \{S_0,\ldots ,S_{n-1}\}\) is a distance-equalizer set of J(n, k). Suppose on the contrary the existence of two vertices \(X,Y\in V(J(n,k)){\setminus } \mathcal{S}\) such that \(|S_i\cap X| \ne |S_i\cap Y|\) for every \(i\in \{0,1,\dots ,n-1\}\).

First, we assume that \(n > 2k^2\). For j, r integers, let \(T(j,r)=\{j,j+1,\ldots ,j+r\}\subseteq W\), where the sums are also taken modulo n. Let \(\mathcal {T}=\{T_1,\dots ,T_s\}\) be the family of sets T(j, r) satisfying \(T(j,r) \cap (X\cup Y)=\emptyset \), \(j-1\in X\cup Y\) and \(j+r+1\in X\cup Y\). Note that \(\mathcal {T}\) is a partition of \(W{\setminus } (X\cup Y)\) with at most 2k parts, by construction. Moreover, \(|T_i|\le k-1\) for every \(i\in \{1,\dots ,s\}\), otherwise, if \(T_i=T(j,r)\), where \(r\ge k\), then \(|S_j\cap X|=|S_j\cap Y|=0\), which contradicts our hypothesis. Therefore,

contradicting our assumption on n.

Now, suppose \(n\in \{2k-1,2k+1\}\). Let \(u = (u_0,\ldots ,u_{n-1})\) be the vector of \(\{-1,1,0\}^n\) such that \(u_i=1\) if \(i\in X{\setminus } Y\); \(u_i=-1\) if \(i\in Y{\setminus } X\); and \(u_i=0\) otherwise. Observe that u has at most 2k nonzero components, and the same number of 1’s and \(-1\)’s. Hence, \(\sum _{i=0}^{n-1}u_i=0\). Let \(s_i = \sum _{j=i}^{i+k-1}u_j\). Observe that \(s_i = |S_i\cap X|-|S_i\cap Y|\), for every \(i\in \{0,1,\dots ,n-1\}\). Hence, \(s_i\not = 0\), for every \(i\in \{0,1,\dots ,n-1\}\), because no set \(S_i\) is equidistant from X and Y. Next, we prove that \(s_i s_{i+k}<0\) for every \(i\in \{0,\dots ,n-1\}\). Indeed, we have that

Therefore, for \(n=2k+1\),

and for \(n=2k-1\),

Hence, for every \(i\in \{0,\dots , n-1\}\), we have \(s_is_{i+k}<0\) since \(s_{i+k}\not = 0\), and it can be derived that \(s_is_{i+rk}<0\), for r odd, and \(s_is_{i+rk}>0\), for r even. Then, \(s_i s_{i+nk}<0\), since n is odd, which is a contradiction since \(s_{i+nk}=s_i\). \(\square \)

We now explore different relationships among distance-equalizer sets and doubly resolving sets. To do this, we first need to formally define resolving sets. Indeed, a subset S of vertices is a resolving set of a graph G if, for every pair of vertices \(x,y\in V(G)\), there exists a vertex \(v\in S\) such that \(d(v,x)\ne d(v,y)\). The metric dimension of G, denoted by dim(G), is the minimum cardinality of a resolving set of G. Observe that, on the one hand, a set of vertices can be at the same time resolving set and distance-equalizer set. For example, it is easy to check that any independent set S of cardinality three of a cycle of order 6 is both resolving and distance-equalizer. However, in this case S is a distance-equalizer set of minimum cardinality, but S is not a resolving set of minimum cardinality, since \(eqdim(C_6)=3\) and \(dim(C_6)=2\). On the other hand, there are graphs satisfying \(dim(G) = eqdim(G)\) with no minimum resolving set being a distance-equalizer set. For example, the cycle or order 4 satisfies \(eqdim(C_4)=dim(C_4)=2\), but there is no set of cardinality two that is both resolving and distance-equalizer because a resolving set on two vertices is formed by two adjacent vertices and distance-equalizer sets of cardinality two are formed by two non-adjacent vertices.

Doubly resolving sets were introduced in [11] as a tool for computing the metric dimension of Cartesian products of graphs. Furthermore, different authors have provided interesting applications of doubly resolving sets on source location [15, 31], algorithmic studies and relations with other graph parameters [12, 26, 32, 33].

We say that two vertices u, v doubly resolve a pair of vertices x, y of G (or that \(\{x, y\}\) is doubly resolved by u, v) if \(d(u, x) - d(u, y) \ne d(v, x) - d(v, y)\). A set \(S\subseteq V(G)\) is a doubly resolving set of G if every pair \(\{x, y\} \subseteq V(G)\) is doubly resolved by two vertices of S (it is said that S doubly resolves \(\{x, y\}\)), and the minimum cardinality of such a set is denoted by \(\psi (G)\). Observe that a doubly resolving set is also a resolving set, and so \(dim(G) \le \psi (G\)).

Proposition 7

For every graph G, it holds that

Proof

Let A be a resolving set, and let B be a distance-equalizer set. We next construct a set C of vertices satisfying \(0\le |C|\le eqdim(G)\) and such that for every pair of vertices \(x,y\in V(G)\), there exist \(u,v\in A\cup B\cup C\) doubly resolving x and y.

First, notice that if \(x, y \in B\) then x and y are doubly resolved by themselves, and if \(x, y \notin B\), then x and y are doubly resolved by vertices u and v, where \(u\in A\) is a vertex resolving x and y, and \(v\in B\) is equidistant from x and y. Hence, in both cases, x and y are doubly resolved by a pair of vertices in \(A\cup B\).

Now, suppose that \(x\in B\) and \(y\notin B\). We claim that, for every \(x\in B\) there is at most one vertex \(y_x\notin B\) such that \(x,y_x\) are not doubly resolved by \(A\cup B\) and besides, in such a case, \(d(u,x)+d(x,y_x)=d(u,y_x)\) for every \(u\in A\cup B\). Indeed, suppose that there exists \(y'\notin B\) such that the pair \(x, y'\) is not doubly resolved by \(A\cup B\). Then, for all \(u\in A\cup B\), the pair of vertices \(x,u\in A\cup B\) does not doubly resolve \(x,y'\). Hence, \(d(u,x)-d(u,y')=-d(x,y')\). In a similar way, if \(y''\) is a vertex such that \(y''\notin B\), \(y''\not = y'\) and the pair \(x, y''\) is not doubly resolved by \(A\cup B\), then for all \(u\in A\cup B\) we have \(d(u,x)-d(u,y'')=-d(x,y'')\). Therefore, \(d(x,y')-d(x,y'')=d(u,y')-d(u,y'')\). Thus, for every pair of vertices \(u,v\in A\cup B\) we obtain \(d(u,y')-d(u,y'')=d(x,y')-d(x,y'')=d(v,y')-d(v,y'')\), implying that \(y',y''\notin B\) are not doubly resolved by \(A\cup B\), which is not possible as we have seen in the former paragraph. Consider the (possibly empty) set

Then, \(0\le |C|\le |B|\) and, by construction, \(A\cup B\cup C\) doubly resolves x and y whenever \(x\in B\) and \(y\notin B\). Therefore, the set \(S=A\cup B \cup C\) is a doubly resolving set for G and, consequently, \(|S|\le dim(G) +2\,\, eqdim (G)\). \(\square \)

We think that the preceding bound can be improved as follows.

Conjecture 2

For every graph G, it holds that \(\psi (G)\le dim(G)+ eqdim(G)\).

A graph attaining the upper bound given in the preceding conjecture is shown in Fig. 3.

In this graph G, \(\psi (G)=dim(G)+eqdim(G)\). Black vertices, gray vertices and the set of leaves are a distance-equalizer set, a resolving set and a doubly resolving set of minimum cardinality, respectively

Full size image

Although we have no proof of Conjecture 2, we next prove that it holds true for trees.

Theorem 7

For every tree T, it holds that

Proof

Let S be the set of all support vertices of T. For every \(v \in S\), consider the sets of vertices \(L_v =\{z : \ z \ \text {is a leaf adjacent to} \ v\}\) and \( T_v =\{v\}\cup L_v\), and observe that the sets \(T_v \) are pairwise disjoint. First, note that it is well known that the set of leaves of a tree T is the unique minimum doubly resolving set of T (see [11]). Hence,

Also, note that if W is a resolving set of T, then \(| W \cap L_v|\ge |L_v|-1\) for every \(v\in S\) (see [30]).

Let \(W'\) be the union of a minimum resolving set and a minimum distance-equalizer set of T. We claim that \(|W' \cap T_v|\ge |L_v|\), for every \(v\in S\). Indeed, \(|W'\cap L_v|\ge |L_v|-1\), since \(W'\) is a resolving set, and \(v \in W'\) or \(L_v\subseteq W'\), by Lemma 1. In any case, \(|W' \cap T_v|\ge |L_v|\).

Then,

\(\square \)

We finish this section by analyzing lower and upper bounds on \(dim(G)+eqdim(G)\). Concretely, we are interested in the minimum and maximum value of \(dim(G)+eqdim(G)\) for graphs of order n. First, note that for any nontrivial graph G of order n,

The lower bound in (1) is attained only by the paths \(P_2\) and \(P_3\), by Theorem 1(i), and the upper bound, only by the path \(P_2\), by Theorem  2(i). Hence, for every graph G of order at least 4,

In order to study this question, we consider the following functions defined for integers \(n\ge 4\):

Proposition 8

For every integer \(n\ge 4\), the following statements hold.

1. (i)

   \(\varSigma (n)\ge \frac{3n}{2}-3\);

2. (ii)

   \(\sigma (n)\le \log _2(n)+2\).

Proof

1. (i)

   Consider the complete bipartite graph \(G=K_{\lfloor n/2\rfloor ,\lceil n/2\rceil }\), for which \(dim(G)=n-2\) (see [14]), and \(eqdim(G)=\lfloor n/2\rfloor \), by Theorem 4(ii). Hence, \(dim (G)+eqdim(G)= n-2 + \lfloor n/2\rfloor \ge 3n/2-3\).

2. (ii)

   For every \(k\ge 1\), consider the graph \(G_k\), with \(V(G_k)=A\cup B\cup C\), where \( \ A=\{v\}, \ B=\{1, \dots , k\}\), \( \ \ C=\{w : \ w \ \ \text {is a binary word of length k} \}\) and two different vertices x and y are adjacent in \(G_k\) if 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, say \(x=w\in C\), and the other one belongs to B, say \(y=j\in B\), and w has the digit 1 in the jth position.

Then, \(G_k\) is a graph of order \(n=2^k+k+1\). Moreover, A is a distance-equalizer set since v is a universal vertex, and it is easy to check that \(A\cup B\) is a resolving set. Hence, \(dim (G_k)+eqdim(G_k)\le k+2\le \log _2(n)+2\). \(\square \)

The graph \(G_3\)

Full size image

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 1 about the equidistant dimension of trees, and Conjecture 2 about the relation of the equidistant dimension with doubly 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.