Loading [MathJax]/jax/output/SVG/jax.js
Research article

The equidistant dimension of graphs: NP-completeness and the case of lexicographic product graphs

  • Received: 08 January 2024 Revised: 13 April 2024 Accepted: 19 April 2024 Published: 28 April 2024
  • MSC : 05C12, 05C69, 05C76, 68Q25

  • Let V(G) be the vertex set of a simple and connected graph G. A subset SV(G) is a distance-equalizer set of G if, for every pair of vertices u,vV(G)S, there exists a vertex in S that is equidistant to u and v. The minimum cardinality among the distance-equalizer sets of G is the equidistant dimension of G, denoted by ξ(G). In this paper, we studied the problem of finding ξ(GH), where GH denotes the lexicographic product of two graphs G and H. The aim was to express ξ(GH) in terms of parameters of G and H. In particular, we considered the cases in which G has a domination number equal to one, as well as the cases where G is a path or a cycle, among others. Furthermore, we showed that ξ(G)ξ(GH)ξ(G)|V(H)| for every connected graph G and every graph H and we discussed the extreme cases. We also showed that the general problem of finding the equidistant dimension of a graph is NP-hard.

    Citation: Adrià Gispert-Fernández, Juan Alberto Rodríguez-Velázquez. The equidistant dimension of graphs: NP-completeness and the case of lexicographic product graphs[J]. AIMS Mathematics, 2024, 9(6): 15325-15345. doi: 10.3934/math.2024744

    Related Papers:

    [1] S. Gajavalli, A. Berin Greeni . On strong geodeticity in the lexicographic product of graphs. AIMS Mathematics, 2024, 9(8): 20367-20389. doi: 10.3934/math.2024991
    [2] Shuangliang Tian, Ping Chen . Edge-coloring of generalized lexicographic product of graphs. AIMS Mathematics, 2024, 9(6): 15988-15995. doi: 10.3934/math.2024774
    [3] Rangel Hernández-Ortiz, Luis Pedro Montejano, Juan Alberto Rodríguez-Velázquez . Weak Roman domination in rooted product graphs. AIMS Mathematics, 2021, 6(4): 3641-3653. doi: 10.3934/math.2021217
    [4] Meiqin Jin, Ping Chen, Shuangliang Tian . Interval edge colorings of the generalized lexicographic product of some graphs. AIMS Mathematics, 2024, 9(11): 30597-30611. doi: 10.3934/math.20241477
    [5] Jin Cai, Shuangliang Tian, Lizhen Peng . On star and acyclic coloring of generalized lexicographic product of graphs. AIMS Mathematics, 2022, 7(8): 14270-14281. doi: 10.3934/math.2022786
    [6] Xia Hong, Wei Feng . Completely independent spanning trees in some Cartesian product graphs. AIMS Mathematics, 2023, 8(7): 16127-16136. doi: 10.3934/math.2023823
    [7] Sakander Hayat, Bagus Imanda, Asad Khan, Mohammed J. F. Alenazi . Three infinite families of Hamilton-connected convex polytopes and their detour index. AIMS Mathematics, 2025, 10(5): 12343-12387. doi: 10.3934/math.2025559
    [8] Syafrizal Sy, Rinovia Simanjuntak, Tamaro Nadeak, Kiki Ariyanti Sugeng, Tulus Tulus . Distance antimagic labeling of circulant graphs. AIMS Mathematics, 2024, 9(8): 21177-21188. doi: 10.3934/math.20241028
    [9] Milica Anđelić, Saleem Khan, S. Pirzada . On graphs with a few distinct reciprocal distance Laplacian eigenvalues. AIMS Mathematics, 2023, 8(12): 29008-29016. doi: 10.3934/math.20231485
    [10] M. Haris Mateen, Muhammad Khalid Mahmmod, Doha A. Kattan, Shahbaz Ali . A novel approach to find partitions of $ Z_{m} $ with equal sum subsets via complete graphs. AIMS Mathematics, 2021, 6(9): 9998-10024. doi: 10.3934/math.2021581
  • Let V(G) be the vertex set of a simple and connected graph G. A subset SV(G) is a distance-equalizer set of G if, for every pair of vertices u,vV(G)S, there exists a vertex in S that is equidistant to u and v. The minimum cardinality among the distance-equalizer sets of G is the equidistant dimension of G, denoted by ξ(G). In this paper, we studied the problem of finding ξ(GH), where GH denotes the lexicographic product of two graphs G and H. The aim was to express ξ(GH) in terms of parameters of G and H. In particular, we considered the cases in which G has a domination number equal to one, as well as the cases where G is a path or a cycle, among others. Furthermore, we showed that ξ(G)ξ(GH)ξ(G)|V(H)| for every connected graph G and every graph H and we discussed the extreme cases. We also showed that the general problem of finding the equidistant dimension of a graph is NP-hard.



    Let V(G) be the vertex set of a simple and connected graph G. As usual, the distance between two vertices u,vV(G), denoted by dG(u,v), is defined to be the length of a shortest path connecting u and v in G. A subset SV(G) is a distance-equalizer set of G if, for every pair of vertices u,vV(G)S, there exists a vertex sS that is equidistant to u and v, i.e., dG(u,s)=dG(v,s). The minimum cardinality among the distance-equalizers of G is the equidistant dimension of G, denoted by ξ(G). This novel parameter was introduced in [9], where the authors explored its properties and proposed some applications to other problems not necessarily in the context of graph theory. They obtained general bounds on ξ(G) and derived closed formulas for the case of several families of graphs. Furthermore, they have shown the usefulness of distance-equalizer sets for constructing doubly resolving sets.

    In this paper, we deal with the problem of finding the equidistant dimension of the lexicographic product GH of two graphs G and H. The aim is to express ξ(GH) in terms of parameters of G and H. Since it is not usual to expect the existence of a unified formula of a parameter on GH for every graph G and every graph H, we will impose certain restrictions on the connected graph G, while H will be an arbitrary graph. In particular, we consider the cases in which G has a domination number equal to one, as well as the cases where G is a path or a cycle, among others. We show that if G has a domination number equal to one, then ξ(GH) can be expressed in terms of domination parameters of H, while if G is a path of a cycle of order n, then ξ(GH) can be expressed in terms of n and the order of H. As we can expect, ξ(G)ξ(GH)ξ(G)n(H) for every connected graph G and every graph H. We discuss the extreme cases of these inequalities and, in particular, the analysis of the case ξ(GH)=ξ(G) leads to the challenge of investigating a new parameter that we call the total equidistant dimension of a graph. As a consequence of the study, we show that the general problem of finding the equidistant dimension of a graph is NP-hard.

    The plan of the paper is described as follows. First, in Section 2, we declare some additional notations, define some concepts, and state some tools needed to develop the remaining sections. In Section 3, we discuss the class of lexicographic product graphs GH where the domination number of G is equal to one. Section 4 is devoted to considering the general bounds ξ(G)ξ(GH)ξ(G)n(H) and discussing the extremal cases. The classes of lexicographic product graphs GH in which G is a path graph or a cycle graph are discussed in Sections 5 and 6, respectively. In Section 7, we show how the study of lexicographic product graphs provides us the tools to show that the general problem of finding the equidistant dimension of arbitrary graphs is NP-hard. Finally, Section 8 is devoted to describing some open problems and future works.

    To begin our study, we need to declare some notation, terminology and tools. The lexicographic product of two graphs G and H is the graph GH whose vertex set is V(GH)=V(G)×V(H) and (g,h) is adjacent with (g,h) in GH if and only if either g is adjacent with g in G or g=g and h is adjacent with h in H. Notice that, for any vertex gV(G), the subgraph of GH induced by {g}×V(H) is isomorphic to H. For simplicity, we will denote this subgraph by Hg. Given a set WV(G)×V(H), the restriction of W to V(Hg) is Wg=WV(Hg), while the projection of W on V(G) is given by

    WG={gV(G):Wg}.

    For instance, Figure 1 shows the graph P4P3, where V(P4)={a,b,c,d} and V(P3)={1,2,3}. In particular, V(Ha)={(a,1),(a,2),(a,3)}, and for W={(a,1),(a,2),(b,3),(c,2)} we have Wa={(a,1),(a,2)} and WP4={a,b,c}.

    Figure 1.  The graph P4P3.

    The following claim, which states the distance formula in the lexicographic product of two graphs, is one of our main tools.

    Remark 2.1. [10] For any connected graph G of order n(G)2 and any graph H, the following statements hold.

    (ⅰ) dGH((g,h),(g,h))=dG(g,g) for gg.

    (ⅱ) dGH((g,h),(g,h))=min{2,dH(h,h)}.

    For a basic introduction to the lexicographic product of two graphs, we suggest the books [10,14]. One of the main problems in the study of GH consists of finding exact values or tight bounds for specific parameters of these graphs and expressing them in terms of known invariants of G and H. In particular, we cite the following works on metric parameters in lexicographic product graphs: metric dimension [15,24,26], fractional metric dimension [7], simultaneous metric dimension [23], simultaneous strong metric dimension [4], k-metric dimension [5,6], strong metric dimension [21], local metric dimension [2], edge metric dimension [22], outer multiset dimension [18], general strong metric dimension [16], weak total resolvability [3], general position problem [20], general position achievement game [19], Steiner general position problem [17], universal lines and the Chen-Chvátal conjecture [25] and convex sets [1].

    Next, we proceed to introduce additional notation and terminology. Complete graphs, empty graphs, cycle graphs, and path graphs of order n will be denoted by Kn, Nn, Cn, and Pn, respectively. As usual, the neighborhood of a vertex gV(G) will be denoted by NG(g)={gV(G):g and g are adjacent}, while the closed neighborhood will be denoted by NG[g]={g}NG(g). Thus, the degree of a vertex gV(G) is given by |NG(g)|.

    For short, if (g,h)V(GH), then we will use the notation NGH(g,h), instead of NGH((g,h)).

    Now, the open neighborhood of a set SV(G) is defined to be NG(S)=gSNG(g), and the closed neighborhood as NG[S]=gSNG[g]=SNG(S). The minimum degree of G will be denoted by δ(G), i.e.,

    δ(G)=min{|NG(g)|:gV(G)}.

    Now, the maximum degree of G will be denoted by Δ(G), i.e.,

    Δ(G)=max{|NG(g)|:gV(G)}.

    Given two different vertices g,gV(G), we define the bisector of g and g as

    Bg|g={uV(G):dG(u,g)=dG(u,g)}.

    Hence, we can express the concept of distance-equalizer set in term of bisectors, i.e., a set XV(G) is a distance-equalizer set of G if XBg|g for every pair of different vertices g,gV(G)X.

    Notice that, for every pair of different vertices g,gV(G) and every h,hV(H), the bisectors in G and the bisectors in GH are related as follows:

    Bg|g×V(H)B(g,h)|(g,h).

    Furthermore,

    (V(G){g})×V(H)B(g,h)|(g,h).

    We define a ξ(G)-set as a distance-equalizer set X with |X|=ξ(G). The same agreement will be assumed for optimal parameters associated to other characteristic sets used in the paper.

    As described above, the aim of Section 3 is to provide a formula for the equidistant dimension of any lexicographic product graph GH whenever G has at least one universal vertex. To carry out the study, we can distinguish two cases depending on whether G has minimum degree one or not. In both cases, the result will depend on some domination parameters on H. Two of these parameters are the domination number and the total domination number, which are well known parameters. In contrast, the third parameter required for the study is completely new. We will call this new parameter the pairwise domination number.

    A subset SV(H) is said to be a dominating set of H if NH[S]=V(H), while S is said to be a total dominating set if NH(S)=V(H). The minimum cardinality among all dominating sets of H is the domination number of H, denoted by γ(H). The total domination number is defined by analogy, and is denoted by γt(H). Since every total dominating set is dominating set, γt(G)γ(G). As mentioned above, the domination number and the total domination number of a graph have been extensively studied. For instance, we cite the books [11,12,13]. We recall that if u is a vertex of a graph G, then the vertex-deletion subgraph Gu is the subgraph of G induced by V(G){u}.

    We shall show in Theorem 3.1 that if δ(G)=1, then either ξ(GH)=γ(H) or ξ(GH)=γ(H)+1, while if δ(G)2, then either ξ(GH)=min{γ(H),γt(Gu)+1} or ξ(GH)=1+min{γ(H),γt(Gu)}. In both cases, the problem of deciding the precise value of ξ(GH) will depend on the value of the pairwise domination number of H.

    We say that a dominating set XV(H) is a pairwise dominating set of H if, for any pair of vertices u,vV(H)X, there exists a vertex wX such that {u,v}NH(w) or {u,v}NH(w)=. The pairwise domination number of H, denoted by γP(H), is defined to be the minimum cardinality among all pairwise dominating sets of H. Since every pairwise dominating set is a dominating set, γP(H)γ(H) for every graph H. Figure 2 shows three connected graphs with γP(H)=γ(H)=3. The sets of black coloured vertices correspond to γP(H)-sets.

    Figure 2.  Three connected graphs with γP(H)=γ(H)=3.

    We assume that the reader is familiar with the basic concepts, notation and terminology on graph theory. For the remainder of the paper, definitions will be introduced whenever a concept is needed.

    We are now in a position to state the main result of this section.

    Theorem 3.1. Let G be a non-trivial graph with γ(G)=1 and let uV(G) be a vertex of degree Δ(G). The following statements hold for any graph H of order at least two.

    (ⅰ) If δ(G)=1, then ξ(GH)={γ(H),ifγP(H)=γ(H),γ(H)+1,otherwise.

    (ⅱ) If δ(G)2, then ξ(GH)={min{γ(H),γt(Gu)+1},ifγP(H)=γ(H),1+min{γ(H),γt(Gu)},otherwise.

    Proof. Let uV(G) be a vertex of degree n(G)1 and let SV(H) be a γ(H)-set. We proceed to show that W={u}×S{(u,v)} is a distance-equalizer set of GH for every uV(G){u} and vV(H). We differentiate the following cases for every pair of vertices (g,h),(g,h)V(GH)W.

    (a) If gu and gu, then (g,h) and (g,h) are adjacent to every vertex in {u}×SW.

    (b) If g=g=u, then (g,h) and (g,h) are adjacent to (u,v)W.

    (c) If g=u and gu, then (g,h) and (g,h) are adjacent to every vertex (u,s)W such that sSNH(h).

    According to the three cases above, W is a distance-equalizer set of GH, which implies that ξ(GH)|W|=γ(H)+1.

    In particular, if γP(H)=γ(H), then for any γP(H)-set X we have that {u}×X is also a distance-equalizer set of GH (we leave the details to the reader). Therefore, in this case, ξ(GH)|{u}×X|=γ(H). In summary, for any graph H,

    ξ(GH){γ(H), if γP(H)=γ(H),γ(H)+1, otherwise. (3.1)

    Let Z be a ξ(GH)-set where ZG has maximum cardinality among all ξ(GH)-sets. Without loss of generality, we can assume that uZG. We differentiate the following three cases for the set Z.

    Case 1. |ZG|=1. Since ZuNGH(u,v) for every uV(G){u} and every vV(H), we have that NGH(u,h)Zu for every (u,h){u}×V(H)Zu. Hence, Z=Zu is a dominating set of Hu. Moreover, if there exists a dominant set Y of H of cardinality less than |Zu|, then for any vertex (u,v)V(GH), where uu, we have that Z={u}×Y{(u,v)} is a ξ(GH)-set with |ZG|=2>1=|ZG|, which is a contradiction. Thus, Zu is a γ(Hu)-set. Notice that Zu is a pairwise dominating set of Hu, since for two vertices (u,y),(u,y)Zu are required to have either a common neighbor in Zu or a common non-neighbor in Zu. In summary, ξ(GH)=|Zu|=γ(H)=γP(H).

    Case 2. |ZG|=2. Let uV(G){u} such that Z=ZuZu. Now, if |Zu|<γ(H) and |Zu|<γ(H), then Zu is not a dominating set of Hu and Zu is not a dominating set of Hu, which implies that there exist two vertices (u,v)V(Hu)Z and (u,v)V(Hu)Z such that for every (u,h)Zu,

    dGH((u,v),(u,h))=21=dGH((u,v),(u,h)),

    and for every (u,h)Zu,

    dGH((u,v),(u,h))=12=dGH((u,v),(u,h)),

    which is a contradiction. Therefore, either |Zu|γ(H) or |Zu|γ(H), which implies that ξ(GH)=|Z|=|Zu|+|Zu|γ(H)+1, and by (3.1) we can conclude that ξ(GH)=γ(H)+1. Notice that, in this case, γ(H)<γP(H).

    Case 3. |ZG|3. If |Zg|γ(H) for some gZG, then ξ(GH)=|Z||Zg|+2γ(H)+2, which contradicts (3.1). Thus, |Zg|<γ(H) for every gZG. As a result, for any gV(G), either Zg= or there exists at least one vertex (g,hg)V(Hg)Z, which is not dominated by any vertex in Zg. Hence, for every pair of vertices of the form (g,hg)V(Hg)Z and (u,hu)V(Hu)Z with gu, there exists (g,h)Z(ZgZu), which is adjacent to (g,hg) and (u,hu). As a result, ZG{u} is a total dominating set of Gu, and so ξ(GH)=|Z||ZG{u}|+1γt(Gu)+1.

    Notice that Case 3 does not occur when δ(G)=1. Therefore, we deduce (ⅰ) from Cases 1 and 2.

    In order to conclude the proof of (ⅱ), from now on we assume that δ(G)2. Hence, Gu does not have isolated vertices. We claim that, by taking any γt(Gu)-set X and any vertex yV(H), it follows that W=({u}X)×{y} is a distance-equalizer set of GH. To prove this claim, we consider the following possibilities for two different vertices (g,h),(g,h)V(GH)W.

    (a') If gu and gu, then (g,h) and (g,h) are adjacent to (u,y)W.

    (b') If g=g=u, then (g,h) and (g,h) are adjacent to every vertex (x,y)X×{y}W.

    (c') If g=u and gu, then (g,h) and (g,h) are adjacent to every vertex (x,y)W such that xXNGu(g).

    Thus, W is a distance-equalizer set of GH, which implies that

    ξ(GH)γt(Gu)+1. (3.2)

    Therefore, in Case 3 we have ξ(GH)=γt(Gu)+1. In summary, to conclude the proof of (ⅱ) we only need to observe that if γP(H)=γ(H), then the only possibilities are Cases 1 and 3, and so ξ(GH)=min{γ(H),γt(Gu)+1}, while if γP(H)>γ(H), then the possibilities are Cases 2 and 3, and then ξ(GH)=min{γ(H)+1,γt(Gu)+1}.

    According to the previous result, our challenge now is to study the pairwise domination number. In particular, notice that if γ(H)=n(H)Δ(H), then γP(H)=γ(H). Therefore, the following corollary follows.

    Corollary 3.1. Let G be a graph with γ(G)=1. If H is a graph with γ(H)=n(H)Δ(H), then the following statements hold.

    (ⅰ) If δ(G)=1, then ξ(GH)=n(H)Δ(H).

    (ⅱ) If δ(G)2, then ξ(GH)=min{n(H)Δ(H),γt(Gu)+1}, where uV(G) is a vertex of maximum degree.

    Lemma 4.1. Let G be a connected graph and let H be a graph. If W is a ξ(GH)-set, then WG is a distance-equalizer set of G.

    Proof. Assume that there are two different vertices g,gV(G)WG. For every hV(H) there exists (u,v)WB(g,h)|(g,h), and so uWGBg|g, which implies that WG is a distance-equalizer set of G.

    As we can expect, the following result holds.

    Theorem 4.1. For any connected graph G and any graph H,

    ξ(G)ξ(GH)ξ(G)n(H).

    Proof. Let W be a ξ(GH)-set. By Lemma 1, WG is a distance-equalizer set of G. Therefore,

    ξ(GH)=|W||WG|ξ(G).

    Now, let X be a ξ(G)-set. We proceed to show that W=X×V(H) is a distance-equalizer set of GH. To this end, let (g,h),(g,h)V(GH)W. Obviously, g,gV(G)X. Hence, if g=g, then W(V(G){g})×V(H)B(g,h)|(g,h). Now, if gg, then there exists xXBg|g, which implies that (x,y)WB(g,h)|(g,h) for every yV(H). Therefore, W is a distance-equalizer set of GH and, as a result,

    ξ(GH)|W|=|X||V(H)|=ξ(G)n(H).

    Next, we discuss the tightness of these bounds. First, we characterize the graphs G such that ξ(GH)=ξ(G) for every graph H. If Bg|g for every pair of different vertices g,gV(G), then there exists a set XV(G) such that for every pair of different vertices g,gV(G), there exists a vertex xX such that dG(g,x)=dG(g,x). In such a case, we say that X is a total distance-equalizer set. Thus, we can define the total equidistant dimension of G, denoted by ξt(G), as the minimum cardinality among all total distance-equalizer sets of G. If there exists g,gV(G) such that Bg|g=, then we can assume that ξt(G)=+, and so we can agree that ξt(G)ξ(G) for every connected graph G.

    For instance, for any complete graph of order n3, we have ξt(Kn)=3>1=ξ(Kn). In the case of an odd order cycle, the bisector of every pair of vertices has cardinality one and every vertex forms a bisector, which implies that ξt(C2k+1)=2k+1. In Figure 3, we show two examples of connected graphs with Bg|g for every pair of different vertices g,gV(G). In both cases, the set of black coloured vertices is a ξt(G)-set and ξt(G)=ξ(G).

    Figure 3.  Two graphs with Bg|g for every pair of different vertices g,gV(G).

    Proposition 4.1. If G is a graph with ξt(G)<+, then ξ(GH)ξt(G) for every graph H.

    Proof. It is readily seen that for every ξt(G)-set X and every vertex h of a graph H, the set X×{h} is a distance-equalizer of GH, which implies that ξ(GH)ξt(G) for every graph H.

    Proposition 4.2. Given a connected graph G of order at least two, the following statements are equivalent.

    (ⅰ) ξ(GH)=ξ(G) for every graph H.

    (ⅱ) ξt(G)=ξ(G).

    Proof. (ⅱ)(ⅰ). If ξt(G)=ξ(G), then by the lower bound given in Theorem 4.1 and Proposition 4.1, we conclude that (ⅰ) follows.

    (ⅰ)(ⅱ). Assume that ξ(GH)=ξ(G) for every graph H of order at least two. By Lemma 1, for any graph H and any ξ(GH)-set W, we have that WG is a ξ(G)-set, which implies that |Ww|=1 for every wWG. Now, suppose that there exist two different vertices g,gV(G) such that Bg|gWG=. We differentiate three cases.

    Case 1. dG(g,g)3. In this case, WB(g,h)|(g,h)(WGBg|g)×V(H)= for every (g,h),(g,h)W, which is a contradiction.

    Case 2. dG(g,g)=2. Let H be a graph with γ(H)=1. Let us conveniently select two vertices h,hV(H). If gWG, then we take hV(H) such that NGH(g,h)Wg, otherwise we take h as an arbitrary vertex of H. Analogously, if gWG, then we take hV(H) such that NGH(g,h)Wg, otherwise we take h as an arbitrary vertex of H. Hence, WB(g,h)|(g,h)(WGBg|g)×V(H)=, which is a contradiction.

    Case 3. dG(g,g)=1. In this case, for any graph H with γ(H)2, there exist vertices h,hV(H) satisfying Wg({g}×NH[h])= and Wg({g}×NH[h])=. Hence, WB(g,h)|(g,h)(WGBg|g)×V(H)=, which is a contradiction.

    According to the three cases above, WG is a total distance-equalizer set of G with |WG|=ξ(G). Therefore, ξt(G)=ξ(G).

    Next, we consider a class of graphs G where ξ(GH)=ξ(G)n(H) for every graph H. To this end, we need to introduce the following result and some additional terminology.

    Proposition 4.3. [9] Let G be a bipartite graph with partite sets A and B. If X is a distance-equalizer set of G, then AX or BX. Consequently, ξ(G)min{|A|,|B|}.

    We recall that a graph is 2-antipodal if every vertex has exactly one diametral vertex, i.e., G is 2-antipodal if for every vertex vV(G) there exists exactly one vertex vV(G) such that dG(v,v)=diam(G). For instance, every hypercube Qk is a bipartite 2-antipodal graph and every cycle graph C2k is a bipartite 2-antipodal graph. In particular, ξ(Q3)=4, and if k is even, then ξ(C2k)=k. The equidistant dimension of cycle graphs was studied in [9].

    Figure 4 shows two bipartite 2-antipodal graphs where ξ(G)=n(G)2. The graph on the left is 5-regular and has diameter 3, while the one on the right is 3-regular and has diameter 5.

    Figure 4.  Two bipartite 2-antipodal graphs where ξ(G)=n(G)2.

    Proposition 4.4. Let G be a bipartite 2-antipodal graph G of diameter 2k+13. If ξ(G)=n(G)2, then for any graph H,

    ξ(GH)=n(G)n(H)2.

    Proof. Let V1 and V2 be the partite sets of G. Since G is a 2-antipodal graph of odd diameter, every vertex in V1 has its antipodal vertex in V2, and so |V1|=|V2|.

    Let W be a ξ(GH)-set. By Lemma 4.1 and Proposition 4.3, we can assume that V1WG. Let gV1 and let gV2 be the antipodal vertex of g. Since the distance between two vertices in the same partite set is even and the distance between vertices of different partite sets is odd, Bg|g=. Now, since dG(g,g)=2k+13, for every h,hV(H) we have that B(g,h)|(g,h)=Bg|g×V(H)=, which implies that either V(Hg)W or V(Hg)W. Therefore, ξ(GH)|V1|n(H)=n(G)2n(H)=ξ(G)n(H), and by the upper bound given in Theorem 4.1 we complete the proof.

    In this section, we will use the following notation. Let V(Pn)={u1,,un}, where consecutive subscripts correspond to adjacent vertices of the path. Let Hi be the copy of H in PnH associated to uiV(Pn). Given a set WV(PnH), we define the sets Wi=WV(Hi) for every i{1,,n}.

    Lemma 5.1. For any integer n4 and any graph H of order at least two, there exists a ξ(PnH)-set W satisfying the following properties.

    (ⅰ) W1=.

    (ⅱ) |W2|γ(H).

    (ⅲ) |Wj|=n(H) for every even number j{4,,n}.

    Proof. Let W be a ξ(PnH)-set. First, we proceed to show that we can take W in such a way that |W1|n(H)1. To this end, we define

    l=minj{1,,n}{j:|Wj|n(H)1}.

    Observe that l is well defined, as ξ(PnH)<n(PnH). Let Yi={hV(H):(ui,h)W}, i.e., Wi={ui}×Yi. If |Y1|n(H)1, then we are done. Now, if Y1=V(H), then from W we can construct a set S=ni=1Si where Si={ui}×Yi+l1 for every i{1,,nl+1} while Si={ui}×V(H) for every i{nl+2,,n}. Since S is a ξ(PnH)-set with |S1|n(H)1, we are done. With this fact in mind, from now on we can assume that W is a ξ(PnH)-set such that |W1| is minimum among all ξ(PnH)-sets. We claim that W1=. Suppose, to the contrary, that there exists a vertex (u1,h)W1. Since |W1|n(H)1, it is easy to check that W=(W{(u1,h)}){(u2,h)} is a ξ(PnH)-set with |W1|<|W1|, which is a contradiction. Therefore, (ⅰ) follows.

    In order to prove (ⅱ) and (ⅲ), we assume that W1=. Thus, if W2 is not a dominating set of H2, then there exists (u2,h)V(H2)NH2(W2) and no vertex in W is equidistant to (u2,h) and any vertex in V(H1), which is a contradiction. Therefore, W2 is a dominating set of H2, and so |W2|γ(H2)=γ(H).

    Finally, to prove (ⅲ), we only need to observe that for any even number j{4,,n}, the distance from any vertex in V(H1) to any vertex in V(Hj) is odd, and since W1=, we conclude that |Wj|=n(H).

    Since the cases n=2 and n=3 were previously considered in Theorem 3.1, we restrict ourselves to the case n4.

    Proposition 5.1. For any graph H of order at least two, ξ(P4H)=γ(H)+n(H).

    Proof. For any ξ(PnH)-set X satisfying Lemma 5.1, we have ξ(P4H)=|X||X2|+|X4|=γ(H)+n(H).

    To conclude the proof, we only need to observe that for any γ(H)-set S, we have that X={u2}×SV(H4) is a distance-equalizer set of P4H, which implies that ξ(P4H)|X|=γ(H)+n(H).

    Proposition 5.2. For any integer n5 and any graph H of order at least three,

    ξ(PnH)=n2n(H)+n42.

    Proof. For any vV(H), we define the set

    W=(n2i=1V(H2i))(n42i=1{(u2i+1,v)}).

    Let (ui,w),(uj,w)V(PnH)W be two different vertices. Notice that i and j are odd. If i=j, then any vertex in W2=V(H2)W is equidistant to (ui,w) and (uj,w). Now, if ij, then W(i+j)/2, and so vertex (u(i+j)/2,v)W(i+j)/2W is equidistant to (ui,w) and (uj,w). Therefore, W is a distance-equalizer set of PnH, which implies that

    ξ(PnH)|W|=n2n(H)+n42. (5.1)

    We proceed to prove the lower bound ξ(PnH)n2n(H)+n42. To this end, we take a ξ(PnH)-set X satisfying Lemma 2 and assume first that n is odd. We consider two cases.

    Case 1. n=5. If |X2|n(H)1, then X5=V(H5), as the distance from vertices in V(H2) to vertices in V(H5) is odd. Hence, ξ(P5H)=|X||X2|+|X4|+|X5|1+2n(H)=n2n(H)+n42, as required. Now, assume |X2|=n(H). If X3=, then |X5|=n(H), as no vertex in X is equidistant to vertices in V(H1) and vertices in V(H5). Thus, ξ(P5H)=|X||X2|+|X4|+|X5|=3n(H)>n2n(H)+n42, which contradicts (5.1). Hence, X3, and so ξ(P5H)=|X||X2|+|X3|+|X4|1+2n(H)=n2n(H)+n42, as required.

    Case 2. n7. Suppose that |X2|n(H)1. In such a case, Xj=V(Hj) for every odd number j5, as the distance from vertices in V(H2) to vertices in V(Hj) is odd. Since n7,

    ξ(PnH)=|X||X2|+ni=4|Xi|1+(n3)n(H)>n2n(H)+n42,

    which contradicts (5.1). Hence, Xi=V(Hi) for every even number in. Thus, by taking I as the set of odd numbers belonging to {1,,n}, we obtain that

    ξ(PnH)=|X|=n2n(H)+jI|Xj|. (5.2)

    We proceed now to show that jI|Xj|n42. Let I=I{1,n}. We already know that the upper bound is reached when |Xj|=1 for every jI and |X1|=|Xn|=0. Suppose to the contrary that there exists an odd number lI such that Xl=. Since in Pn we have that Bul2|ul+2={ul}, we conclude that |Xl2|=n(H) or |Xl+2|=n(H). In general, if 3ln+12, then |Xl2j|=n(H) or |Xl+2j|=n(H) for every j{1,,l12}, while if n+12ln2, then |Xl2j|=n(H) or |Xl+2j|=n(H) for every j{1,,nl2}. With these facts in mind, we take

    l=maxjI{j:Xj= and jn+12}.

    Hence, if n3ln+12, then

    jI|Xj|l12j=1(|Xl2j|+|Xl+2j|)l12n(H)n36n(H)n32=n42. (5.3)

    Therefore, by combining (5.1) with (5.2) and (5.3), we obtain the result. The same reasoning works if we omit the restriction ln3 and consider that Xj for every jI with j>n+12. In such a case, we have

    jI|Xj|l12n(H)+(|I|1)(l1))32(l1)+|I|(l1))|I|=n42. (5.4)

    Therefore, by combining (5.1) with (5.2) and (5.4), we obtain the result.

    Assume that there exists jI with Xj= and j>n+12. We define

    l=minjI{j:Xj= and jn+12}.

    Now, if n+12l2n3+1, then

    jI|Xj|nl2j=1(|Xl2j|+|Xl+2j|)nl2n(H)n36n(H)n32=n42. (5.5)

    Therefore, by combining (5.1) with (5.2) and (5.5), we obtain the result.

    Now, if 1ln31 and 2n3+2ln, then we have that |Xj|1 for every jI such that 2l+1j2ln2. Thus, there are lln+12 different values for j with these requirements. In this case,

    jI|Xj|l12n(H)+nl2n(H)+(lln+12)32((n1)(ll))+12(2(ll)(n+1))=12(2n4(ll))12(2n4(n1))=n32=n42.

    Therefore, by combining this inequality with (5.1) and (5.2), we obtain the result.

    Finally, if n is even, then we already know that Xn=V(Hn), which implies that XXn is a distance-equalizer set of Pn1H. Hence,

    ξ(PnH)=|X|ξ(Pn1H)+n(H) =(n12n(H)+n52)+n(H)=(n22n(H)+n42)+n(H)=n2n(H)+n42.

    Therefore, from this bound and (5.1), we conclude the proof.

    In this section, we will use the following notation. Let V(Cn)={u0,,un1}, where consecutive subscripts correspond to adjacent vertices of the cycle, and the addition of subscripts will be modulo n. As above, given a set WV(CnH), we define the sets Wi=WV(Hi) for every i{0,,n1}.

    Since the case n=3 was previously considered in Theorem 3.1, we restrict ourselves to the case n4.

    Proposition 6.1. Let H be a graph of order n(H)2. If, for any γ(H)-set S, there exists a vertex hV(H)S such that SNH(h), then ξ(C4H)=2γ(H)+1, otherwise ξ(C4H)=2γ(H).

    Proof. It is readily seen that if S is a γ(H)-set, then for any vV(H) we have that S={u0,u2}×S{(u1,v)} is a distance-equalizer set of C4H. Thus,

    ξ(C4H)|S|=2|S|+1=2γ(H)+1. (6.1)

    Now, if SNH(h) for every vertex hV(H)S, then S={u0,u2}×S is a distance-equalizer set of C4H, which implies that

    ξ(C4H)|S|=2|S|=2γ(H). (6.2)

    Notice that if H is an empty graph, then S=V(H), which implies that S is a distance-equalizer set of C4H, and so (6.2) follows.

    From now on, let X be a ξ(C4H)-set and let i{0,,3}. If neither Xi nor Xi+1 are dominating sets of Hi and Hi+1, respectively, then there exist two vertices (ui,h)V(Hi)Xi and (ui+1,h)V(Hi+1)Xi+1 such that B(ui,h)|(ui+1,h)X=, which is a contradiction. Thus, there exists j{0,,3} such that Xj and Xj+2 are dominating sets of Hi and Hi+2, respectively. Hence, |Xj|γ(H) and |Xj+2|γ(H), which implies that

    ξ(C4H)|Xj|+|Xj+2|2γ(H). (6.3)

    From (6.2) and (6.3), we can conclude that if H is an empty graph or there exists a γ(H)-set S such that SNH(h) for every vertex hV(H)S, then ξ(C4H)=2γ(H).

    Finally, assume that for any γ(H)-set A, there exists a vertex hV(H)A such that ANH(h). Obviously, if |Xj|+|Xj+2|>2γ(H), then we are done by (6.1). Now, consider the case |Xj|=|Xj+2|=γ(H)<n(H). If Xj+1=Xj1=, then B(uj,h)|(uj+2,h)X= for every pair of vertices (uj,h)V(Hj)Xj and (uj+2,h)V(Hj+2)Xj+2 such that XjNHj(uj,h) and Xj+2NHj+2(uj+2,h), which is a contradiction. Thus, |Xj+1|+|Xj1|1, and so

    ξ(C4H)=|X||Xj|+|Xj+2|+1=2γ(H)+1. (6.4)

    Therefore, by (6.1) and (6.4), we conclude the proof.

    Proposition 6.2. Let H be a graph of order at least two. If γ(H)=δ(H)=1, then ξ(C5H)=4, otherwise, ξ(C5H)=5.

    Proof. The proof is simple, we will describe the idea, leaving the details to the reader.

    Assume γ(H)=δ(H)=1. It is readily seen that if hV(H) is a vertex of degree one and hV(H){h} is a universal vertex, then X={u0,u2,u3}×{h}{(u0,h)} is a distance-equalizer set, and so ξ(C5H)|X|=4.

    It is easy to check that no set of cardinality three is a distance-equalizer set of C5H. Therefore, ξ(C5H)=4.

    From now on, assume that γ(H)2 or δ(H)1. We already know that ξ(C5H)5, by Proposition 4.1. Finally, through a case analysis, we can check that no set of cardinality four is a distance-equalizer set of C5H. Therefore, ξ(C5H)5.

    It was shown in [9] that ξ(Cn)n12 for every odd integer n3. We proceed too show that the bound can be improved for n5.

    Lemma 6.1. If n5 is an odd integer, then ξ(Cn)n+12.

    Proof. Let W be a ξ(Cn)-set and let V(Cn)={0,,n1}, where consecutive vertices are adjacent. If for every pair of adjacent vertices of Cn, at least one of them belongs to W, then ξ(Cn)n+12 and we are done. Thus, we can assume, without loss of generality, that W{0,n1}=. Since n is an odd integer, for any i{1,,n12}, we have that Bi|ni={0}. Thus, from 0W, we deduce that iW or niW, which implies that ξ(Cn)n12.

    Suppose that ξ(Cn)=n12. Notice that, in this case, |W{i,ni}|=1 for every i{1,,n12}. Now, since W{0,n1}=, we have that n12W, and since |W{n12,n+12}|=1, we have that n+12W. If n1(mod4), then Bn1|n+12={n14} and B0|n+12={nn14}, which is a contradiction, as |W{n14,nn14}|=1. Analogously, if n3(mod4), then B0|n+12={n+14} and Bn1|n+12={nn+14}, which is a contradiction, as |W{n+14,nn+14}|=1. Therefore, ξ(Cn)n12+1=n+12.

    Proposition 6.3. Let H be a graph of order at least two. If n7 is an odd integer, then ξ(CnH)=n.

    Proof. By Proposition 4.1, we conclude that ξ(CnH)n. Hence, we proceed to show that ξ(CnH)n.

    Let W be a ξ(CnH)-set and let k=n12. If Wi for every i{0,,n1}, then ξ(CnH)=ni=0|Wi|n and we are done. From now on, we suppose, without loss of generality, that W0=. Since two vertices (ui,y)V(Hi)Wi and (uni,y)V(Hni)Wni have to be equalized by W, we deduce the following constraints, where λ=1 if δ(H)=0 while λ2 otherwise,

    |W1|λor|Wn1|λ,|W2|=n(H)or|Wn2|=n(H),|Wk1|=n(H)or|Wk+2|=n(H),|Wk|γ(H)or|Wk+1|γ(H).

    Hence,

    ξ(CnH)=n1i=0|Wi|λ+(k2)n(H)+γ(H). (6.5)

    Suppose that n1i=0|Wi|=λ+(k2)n(H)+γ(H). In such a case, |WCn|=n12, and by combining Lemmas 4.1 and 6.1, we obtain n12=|WCn|ξ(Cn)n+12, which is a contradiction. Thus,

    ξ(CnH)=n1i=0|Wi|1+λ+(k2)n(H)+γ(H). (6.6)

    Furthermore, if δ(H)=0, then γ(H)2 and λ=1, while if δ(H)1, then γ(H)1 and λ2. This implies that in any case we have λ+γ(H)3. Therefore, if n(H)3, then (6.6) leads to

    ξ(CnH)=n1i=0|Wi|4+(k2)n(H)4+3(k2)=(2k+1)+(k3)2k+1=n,

    as required.

    From now on, assume n(H)=2. We consider first HK2. In this case, λ=2 and γ(H)=1. Without loss of generality, we can assume that |W1|=2. Thus, if |Wn1|=2, then ξ(CnK2)=n1i=0|Wi|4+2(k2)+1=2k+1=n and we are done. Suppose that |Wn1|1.

    Case 1. |Wn1|=1. If |Wk+1|=2, then we are done, as ξ(CnK2)=n1i=0|Wi|3+2(k2)+2=2k+1=n. Now, we consider the case |Wk+1|1. For the sake of clarity, we will simplify the notation by taking three vertices z0V(H0), zn1V(Hn1)Wn1 and zk+1V(Hk+1)Wk+1. Notice that if n1(mod4), then Bzn1|zk+1=V(Hk2) and Bz0|zk+1=V(Hnk2), which implies that Wk2 and Wnk2, and so |Wk2|+|Wnk2|3. Hence, ξ(CnK2)=n1i=0|Wi|3+(2(k2)+1)+1=2k+1=n, as required. Analogously, if n3(mod4), then Bz0|zk+1=V(Hk+12) and Bzn1|zk+1=V(Hk+12), which implies that Wk+12 and Wnk+12, and so |Wk+12|+|Wnk+12|3. Hence, ξ(CnK2)=n1i=0|Wi|3+(2(k2)+1)+1=2k+1=n, as required.

    Case 2. Wn1=. Observe that |Wk|1, as Bz0|zn1=V(Hk). Now, if |Wk+1|=2, then we are done, as ξ(CnK2)=n1i=0|Wi|2+2(k2)+3=2k+1=n. Assume |Wk+1|1. Notice also that |Wn2|=2. If |W2|=2, then we are done, as ξ(CnK2)=n1i=0|Wi|2+(2(k2)+2)+1=2k+1=n. Assume |W2|1. Thus, |Wk+1|=1, as for every z2V(H2)W2 we have that Bz2|zn1=V(Hk+1). As in Case 1, if n1(mod4), then we reach to |Wk2|+|Wnk2|3, and so ξ(CnK2)=n1i=0|Wi|2+(2(k2)+1)+2=2k+1=n, as required. Analogously, if n3(mod4), then we reach to |Wk+12|+|Wnk+12|3. Hence, ξ(CnK2)=n1i=0|Wi|2+(2(k2)+1)+2=2k+1=n, as required.

    According to the two cases above, the proof is complete for HK2. From now on we assume that H is the empty graph, i.e., HN2. In this case, λ=1 and γ(H)=2. Without loss of generality, we can assume that |Wk|=2. Thus, if |Wk+1|=2, then ξ(CnK2)=n1i=0|Wi|1+2(k2)+4=2k+1=n and we are done. From now on, we assume that |Wk+1|1. Now, if |W1|+|Wn1|3, then we are done, as ξ(CnK2)=n1i=0|Wi|3+2(k2)+2=2k+1=n. Thus, we assume 1|W1|+|Wn1|2 and we differentiate the following cases.

    Case 1'. |W1|=0 and |Wn1|=2. In this case, |Wk+1|=1 and so ξ(CnK2)=n1i=0|Wi|2+2(k2)+3=2k+1=n.

    Case 2'. |W1|=2 and |Wn1|=0. By analogy to Case 1, we deduce that either |Wk2|+|Wnk2|3 or |Wk+12|+|Wnk+12|3. Hence, we reach to ξ(CnK2)=n1i=0|Wi|2+(2(k2)+1)+2=2k+1=n.

    Case 3'. |W1|=1 and |Wn1|1. In this case, we have that |Wk+1|=1 and, as above, we deduce that either |Wk2|+|Wnk2|3 or |Wk+12|+|Wnk+12|3. Hence, we reach to ξ(CnK2)=n1i=0|Wi|1+(2(k2)+1)+3=2k+1=n.

    Case 4'. |W1|1 and |Wn1|=1. This case is analogous to the previous one.

    According to the four cases above, the proof is complete.

    Proposition 6.4. Let n6 be an integer. The following statements hold for any graph H of order at least two.

    (a) If n2(mod4), then ξ(CnH)=n2n(H).

    (b) If n0(mod4), then ξ(CnH)=n2n(H)+n4.

    Proof. If n2(mod4), then Proposition 4 leads to ξ(CnH)=n2n(H). From now on, we assume that n0(mod4) and n8. Let UV(CnH) be a set satisfying the following properties:

    |Ui|=n(H) whenever i is odd.

    |UiUi+n/2|=1 whenever i0(mod2).

    A simple case analysis shows that U is a distance-equalizer set of CnH. Hence,

    ξ(CnH)|U|=n2n(H)+n4. (6.7)

    It remains necessary to prove that ξ(CnH)n2n(H)+n4. Let W be a ξ(CnH)-set. Suppose that there are two consecutive copies of H, say Hl and Hl+1, such that |Wl|<n(H) and |Wl+1|<n(H). Without loss of generality, we can consider that l=0. Notice that for any h,hV(H) and k{1,,n42}, we have that B(u0,h)|(u2k+1,h)=. Thus, |W2k+1|=n(H) for every k{1,,n42}. By analogy, we deduce that |W2k+2|=n(H) for every k{1,,n42}. Furthermore, |Wn1|=n(H) or |W2|=n(H), as B(un1,h)|(u2,h)= for every h,hV(H). In addition, if a vertex (ui,v)W is equidistant to a vertex in V(H0)W0 and a vertex in V(H1)W1, then i=0 or i=1, which implies that |W0|+|W1|1. In summary,

    ξ(CnH)1+n(H)+(n4)n(H)>n2n(H)+n4,

    which contradicts (6.7). Hence, we conclude that for every pair of consecutive copies of H, say Hl and Hl+1, we have that |Wl|=n(H) or |Wl+1|=n(H). Without loss of generality, we assume that |Wi|=n(H) whenever i is odd. Now, if W0=Wn/2=, then |W2j|=n(H) or |Wn2j|=n(H) for every j{1,,n44}. Thus, by the minimality of |W|, we have that |W0|+|Wn/2|1. The same reasoning applies to conclude that |Wi|+|Wi+n/2|1 whenever i is even. Therefore,

    ξ(CnH)=|W|=n22i=0|W2l+1|+n22i=0|W2l|n2n(H)+n4. (6.8)

    From (6.7) and (6.8), we conclude the proof.

    In this section, we discuss the following basic question: How difficult is it to compute the equidistant dimension of a graph? The decision problem associated with the problem of finding the equidistant dimension of a graph can be expressed in the following form.

    Distance-equalizer set problem (DESP)

    Instance: A connected graph G and a positive integer kn(G).

    Question: Does G have a distance-equalizer set of cardinality at most k?

    We shall now formally define another known decision problem that we need to continue our study.

    Dominating set problem (DSP)

    Instance: A graph H and a positive integer kn(H).

    Question: Does H have a dominating set of cardinality at most k?

    The following known result will be one of our main tools.

    Theorem 7.1. [8] DSP is NP-complete.

    Our second tool will be the graph shown in the following figure.

    We are now in a position to present the following result.

    Theorem 7.2. DESP is NP-complete, even for the class of lexicographic product graphs.

    Proof. We must do two things. First, we must show that DESP belongs to the class NP, which is easy to do, since it is easy to verify a "yes" instance of DESP in polynomial time. That is, for a graph G, a positive integer k, and an arbitrary set of vertices XV(G) with |X|k, it is easy to verify in polynomial time (by computing first the distance matrix) whether X is a distance-equalizer set of G.

    Second, we must construct a reduction from a known NP-complete problem to DESP. We can use DSP, by Theorem 7.1. Given an instance I=(H,k) of DSP, we construct an instance I=(GH,k) of DESP, where G is the graph shown in Figure 5. We must show that I is a "yes" instance of DSP if and only if I is a "yes" instance of DESP, in this case for k=3k. To do so, let X={a1,a2,a3} be the set of vertices of degree 4 in G and let biV(G) be the vertex of degree 1 that is adjacent to ai for every i{1,2,3}, and let z be the vertex of degree 3 in G.

    Figure 5.  The graph G used in the proof of Theorem 7.2. The set X={a1,a2,a3} forms a ξ(G)-set.

    Now, we proceed to show that if SV(H) is a dominating set of H with |S|k, then X×S is a distance-equalizer of GH with |X×S|k. To this end, we differentiate the following cases for two different vertices (g,h),(g,h)V(GH)X×S and, for each of these cases, we will show that there exists at least one vertex (x,s)X×S such that dGH((x,s),(g,h))=dGH((x,s),(g,h)).

    Case 1. g=g. For every aiX{g} and every sS we have that (ai,s)X×S and by Remark 2.1 we have

    dGH((ai,s),(g,h))=dG(ai,g)=dG(ai,g)=dGH((ai,s),(g,h)).

    Case 2. {g,g}={ai,bi} for some i{1,2,3}. Without loss of generality, we can take g=ai and g=bi. In this case, since hV(H)S and S is a dominating set of H, there exists at least one vertex sSNH(h). Hence, (ai,s)X×S and by Remark 2.1 we have

    dGH((ai,s),(g,h))=dGH((ai,s),(ai,h))=dH(s,h)=1=dG(ai,bi)=dGH((ai,s),(bi,h))=dGH((ai,s),(g,h)).

    Case 3. gg and {g,g}{ai,bi} for every i{1,2,3}. If {g,g}={bl,bm}, then for j{1,2,3}{l,m} we have dG(g,aj)=2=dG(g,aj). Thus, for every sS we have that (aj,s)X×S and by Remark 2.1 we have

    dGH((aj,s),(g,h))=dG(aj,g)=dG(aj,g)=dGH((aj,s),(g,h)). (7.1)

    Now, if {g,g}={al,am}, then for j{1,2,3}{l,m} we have dG(g,aj)=1=dG(g,aj), and so we arrive to (7.1). If (g,g)=(al,bj) for jl, then dG(g,aj)=1=dG(g,aj), and again we arrive to (7.1). Assume, without loss of generality, that g=z is the central vertex of G. In such a case, we have g=bj or g=ai for i,j{1,2,3}. In the first case, dG(g,aj)=1=dG(g,aj), and so we arrive to (7.1). In the second case, since S is a dominating set, there exists sSNH(h) and so dGH((g,h),(ai,s))=dH(h,s)=1=dG(g,ai)=dGH((g,h),(ai,s)). According to the three cases above, X×S is a distance-equalizer of GH.

    Therefore, we conclude that if I is a "yes" instance of DSP, then I is a "yes" instance of DESP.

    Conversely, let W be a distance-equalizer set of GH with |W|k. Suppose that there exists i{1,2,3} such that neither Wai nor Wbi are dominating sets of Hai and Hbi, respectively. Thus, there exists at least one vertex (ai,h)V(Hai)Wai such that WaiNGH(ai,h)= and there exists at least one vertex (bi,h)V(Hbi)Wbi such that WbiNGH(bi,h)=. We proceed to show that, with the assumptions above, dGH((x,y),(ai,h))dGH((x,y),(bi,h)) for every (x,y)W. To this end, we differentiate the following three cases.

    Case 1'. (x,y)W(WaiWbi). In this case, xai and xbi, which implies that

    dGH((x,y),(ai,h))=dG(x,ai)dG(x,ai)+dG(ai,bi)=dG(x,bi)=dGH((x,y),(bi,h)).

    Case 2'. (x,y)Wai. In this case, x=ai. Since (ai,h)V(Hai)Wai and WaiNGH(ai,h)=, we have that dGH((x,y),(ai,h))=2. On the other side, dGH((x,y),(bi,h))=dGH((ai,y),(bi,h))=dG(ai,bi)=1. Therefore, dGH((x,y),(ai,h))dGH((x,y),(bi,h)).

    Case 3'. (x,y)Wbi. In this case, x=bi. Now, since (bi,h)V(Hbi)Wbi and WbiNGH(bi,h)=, we have that dGH((x,y),(bi,h))=2. On the other side, dGH((x,y),(ai,h))=dGH((bi,y),(ai,h))=dG(bi,ai)=1. Therefore, dGH((x,y),(ai,h))dGH((x,y),(bi,h)).

    According to the three cases above, dGH((x,y),(ai,h))dGH((x,y),(bi,h)) for every (x,y)W, which contradicts the fact that W is a distance-equalizer set of GH. Hence, either Wai is a dominating set of Hai or Wbi is a dominating set of Hbi for every i{1,2,3}, which implies that H has a dominating set of cardinality at most 13|W|k. Therefore, we conclude that if I is a "yes" instance of DESP, then I is a "yes" instance of DSP.

    If S is the set of vertices of degree two of P4, then the set X×S described in the proof of Theorem 7.2 corresponds to the set of black coloured vertices shown in Figure 6, which forms a ξ(GP4)-set.

    Figure 6.  The graph GP4.

    In this paper, we deal with the problem of finding the equidistant dimension of the lexicographic product GH of two graphs G and H. To carry out the study when the domination number of G is equal to one, we have distinguished two cases depending on whether G has minimum degree one or not. In both cases, the result depends on some domination parameters on H. Two of these parameters are the domination number and the total domination number, which are well-known parameters. In contrast, the third parameter required for the study is completely new (the pairwise domination number).

    As we can expect, ξ(G)ξ(GH)ξ(G)n(H) for every connected graph G and every graph H. The discussion of the case ξ(GH)=ξ(G) leads to the challenge of investigating a new parameter that we call the total equidistant dimension of a graph.

    We also obtain the value of ξ(GH) for some particular classes of graphs, including the cases where G is a path or a cycle, and we show that the general problem of finding the equidistant dimension of a graph is NP-hard.

    Some specific open problems derived from the discussion are listed below.

    ● Theorem 3.1 shows the need for an extensive study on pairwise domination. In particular, it would be convenient to characterize the graphs with γP(H)=γ(H).

    ● We learned from Proposition 4.2 that ξ(GH)=ξ(G) for every graph H if and only if ξt(G)=ξ(G). This statement shows the need to develop a detailed study on the total equidistant dimension of a graph.

    ● In Proposition 4.4, the assumptions are that G is a bipartite 2-antipodal graph G of diameter 2k+13 with ξ(G)=n(G)2. However, a problem to be clarified is the existence (or non-existence) of bipartite 2-antipodal graphs of diameter 2k+13 with ξ(G)>n(G)2.

    ● To complete the study proposed in Section 5, it remains to investigate the following cases. If n(H)=2, then for n5 and n{9,10} we conjecture that ξ(PnH)=3n52 whenever n is odd, and ξ(PnH)=3n42 whenever n is even, while ξ(P9H)=10 and ξ(P10H)=12.

    The authors declare they have not used Artificial Intelligence (AI) tools in the creation of this article.

    The authors were supported by the SGR Grant 2021 00115.

    Juan Alberto Rodríguez-Velázquez is an editorial board member and was not involved in the editorial review or the decision to publish this article. The authors declare that they have no conflicts of interest.



    [1] B. S. Anand, M. Changat, S. Klavžar, I. Peterin, Convex sets in lexicographic products of graphs, Graphs Combin., 28 (2012), 77–84. https://doi.org/10.1007/s00373-011-1031-4 doi: 10.1007/s00373-011-1031-4
    [2] G. A. Barragán-Ramírez, A. Estrada-Moreno, Y. Ramírez-Cruz, J. A. Rodríguez-Velázquez, The local metric dimension of the lexicographic product of graphs, Bull. Malays. Math. Sci. Soc., 42 (2019), 2481–2496. https://doi.org/10.1007/s40840-018-0611-3 doi: 10.1007/s40840-018-0611-3
    [3] K. Casel, A. Estrada-Moreno, H. Fernau, J. A. Rodríguez-Velázquez, Weak total resolvability in graphs, Discuss. Math. Graph Theory, 36 (2016), 185–210.
    [4] A. Estrada-Moreno, C. García-Gómez, Y. Ramírez-Cruz, J. A. Rodríguez-Velázquez, The simultaneous strong metric dimension of graph families, Bull. Malays. Math. Sci. Soc., 39 (2016), 175–192. https://doi.org/10.1007/s40840-015-0268-0 doi: 10.1007/s40840-015-0268-0
    [5] A. Estrada-Moreno, I. G. Yero, J. A. Rodríguez-Velázquez, Relationships between the 2-metric dimension and the 2-adjacency dimension in the lexicographic product of graphs, Graphs Combin., 32 (2016), 2367–2392. https://doi.org/10.1007/s00373-016-1736-5 doi: 10.1007/s00373-016-1736-5
    [6] A. Estrada-Moreno, I. G. Yero, J. A. Rodríguez-Velázquez, The k-metric dimension of the lexicographic product of graphs, Discrete Math., 339 (2016), 1924–1934. https://doi.org/10.1016/j.disc.2015.12.024 doi: 10.1016/j.disc.2015.12.024
    [7] M. Feng, K. S. Wang, On the fractional metric dimension of corona product graphs and lexicographic product graphs, 2012, arXiv: 1206.1906.
    [8] M. R. Garey, D. S. Johnson, Computers and intractability: a guide to the theory of NP-completeness, New York: W. H. Freeman and Company, 1979.
    [9] A. González, C. Hernando, M. Mora, The equidistant dimension of graphs, Bull. Malays. Math. Sci. Soc., 45 (2022), 1757–1775. https://doi.org/10.1007/s40840-022-01295-z doi: 10.1007/s40840-022-01295-z
    [10] R. Hammack, W. Imrich, S. Klavžar, Handbook of product graphs, 2 Eds., Boca Raton: CRC Press, 2011. https://doi.org/10.1201/b10959
    [11] T. W. Haynes, S. T. Hedetniemi, P. J. Slater, Fundamentals of domination in graphs, Boca Raton: CRC Press, 1998. https://doi.org/10.1201/9781482246582
    [12] T. W. Haynes, S. T. Hedetniemi, P. J. Slater, Domination in graphs: Volume 2: Advanced topics, New York: Routledge, 1998. https://doi.org/10.1201/9781315141428
    [13] M. A. Henning, A. Yeo, Total domination in graphs, New York: Springer, 2013. https://doi.org/10.1007/978-1-4614-6525-6
    [14] W. Imrich, S. Klavžar, Product graphs: structure and recognition, New York: Wiley, 2000.
    [15] M. Jannesari, B. Omoomi, The metric dimension of the lexicographic product of graphs, Discrete Math., 312 (2012), 3349–3356. https://doi.org/10.1016/j.disc.2012.07.025 doi: 10.1016/j.disc.2012.07.025
    [16] C. X. Kang, I. G. Yero, E. Yi, The fractional strong metric dimension in three graph products, Discrete Appl. Math., 251 (2018), 190–203. https://doi.org/10.1016/j.dam.2018.05.051 doi: 10.1016/j.dam.2018.05.051
    [17] S. Klavžar, D. Kuziak, I. Peterin, I. G. Yero, A Steiner general position problem in graph theory, Comput. Appl. Math., 40 (2021), 223. https://doi.org/10.1007/s40314-021-01619-y doi: 10.1007/s40314-021-01619-y
    [18] S. Klavžar, D. Kuziak, I. G. Yero, Further contributions on the outer multiset dimension of graphs, Results Math., 78 (2023), 50. https://doi.org/10.1007/s00025-022-01829-8 doi: 10.1007/s00025-022-01829-8
    [19] S. Klavžar, P. K. Neethu, S. V. Ullas Chandran, The general position achievement game played on graphs, Discrete Appl. Math., 317 (2022), 109–116. https://doi.org/10.1016/j.dam.2022.04.019 doi: 10.1016/j.dam.2022.04.019
    [20] S. Klavžar, I. G. Yero, The general position problem and strong resolving graphs, Open Math., 17 (2019), 1126–1135. https://doi.org/10.1515/math-2019-0088 doi: 10.1515/math-2019-0088
    [21] D. Kuziak, I. G. Yero, J. A. Rodríguez-Velázquez, Closed formulae for the strong metric dimension of lexicographic product graphs, Discuss. Math. Graph Theory, 36 (2016), 1051–1064. https://doi.org/10.7151/dmgt.1911 doi: 10.7151/dmgt.1911
    [22] I. Peterin, I. G. Yero, Edge metric dimension of some graph operations, Bull. Malays. Math. Sci. Soc., 43 (2020), 2465–2477. https://doi.org/10.1007/s40840-019-00816-7 doi: 10.1007/s40840-019-00816-7
    [23] Y. Ramírez-Cruz, A. Estrada-Moreno, J. A. Rodríguez-Velázquez, The simultaneous metric dimension of families composed by lexicographic product graphs, Graphs Combin., 32 (2016), 2093–2120. https://doi.org/10.1007/s00373-016-1675-1 doi: 10.1007/s00373-016-1675-1
    [24] J. A. Rodríguez-Velázquez, Lexicographic metric spaces: basic properties and the metric dimension, Appl. Anal. Discrete Math., 14 (2020), 20–32.
    [25] J. A. Rodríguez-Velázquez, Solution of the Chen-Chvátal conjecture for specific classes of metric spaces, AIMS Math., 6 (2021), 7766–7781. https://doi.org/10.3934/math.2021452 doi: 10.3934/math.2021452
    [26] S. W. Saputro, R. Simanjuntak, S. Uttunggadewa, H. Assiyatun, E. T. Baskoro, A. N. M. Salman, et al., The metric dimension of the lexicographic product of graphs, Discrete Math., 313 (2013), 1045–1051. https://doi.org/10.1016/j.disc.2013.01.021 doi: 10.1016/j.disc.2013.01.021
  • This article has been cited by:

    1. S. Gajavalli, A. Berin Greeni, On strong geodeticity in the lexicographic product of graphs, 2024, 9, 2473-6988, 20367, 10.3934/math.2024991
  • Reader Comments
  • © 2024 the Author(s), licensee AIMS Press. This is an open access article distributed under the terms of the Creative Commons Attribution License (http://creativecommons.org/licenses/by/4.0)
通讯作者: 陈斌, bchen63@163.com
  • 1. 

    沈阳化工大学材料科学与工程学院 沈阳 110142

  1. 本站搜索
  2. 百度学术搜索
  3. 万方数据库搜索
  4. CNKI搜索

Metrics

Article views(1160) PDF downloads(55) Cited by(1)

Figures and Tables

Figures(6)

/

DownLoad:  Full-Size Img  PowerPoint
Return
Return

Catalog