
Let V(G) be the vertex set of a simple and connected graph G. A subset S⊆V(G) is a distance-equalizer set of G if, for every pair of vertices u,v∈V(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 ξ(G∘H), where G∘H denotes the lexicographic product of two graphs G and H. The aim was to express ξ(G∘H) 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)≤ξ(G∘H)≤ξ(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
[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 S⊆V(G) is a distance-equalizer set of G if, for every pair of vertices u,v∈V(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 ξ(G∘H), where G∘H denotes the lexicographic product of two graphs G and H. The aim was to express ξ(G∘H) 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)≤ξ(G∘H)≤ξ(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,v∈V(G), denoted by dG(u,v), is defined to be the length of a shortest path connecting u and v in G. A subset S⊆V(G) is a distance-equalizer set of G if, for every pair of vertices u,v∈V(G)∖S, there exists a vertex s∈S 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 G∘H of two graphs G and H. The aim is to express ξ(G∘H) 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 G∘H 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 ξ(G∘H) can be expressed in terms of domination parameters of H, while if G is a path of a cycle of order n, then ξ(G∘H) can be expressed in terms of n and the order of H. As we can expect, ξ(G)≤ξ(G∘H)≤ξ(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 ξ(G∘H)=ξ(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 G∘H where the domination number of G is equal to one. Section 4 is devoted to considering the general bounds ξ(G)≤ξ(G∘H)≤ξ(G)n(H) and discussing the extremal cases. The classes of lexicographic product graphs G∘H 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 G∘H whose vertex set is V(G∘H)=V(G)×V(H) and (g,h) is adjacent with (g′,h′) in G∘H 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 g∈V(G), the subgraph of G∘H induced by {g}×V(H) is isomorphic to H. For simplicity, we will denote this subgraph by Hg. Given a set W⊆V(G)×V(H), the restriction of W to V(Hg) is Wg=W∩V(Hg), while the projection of W on V(G) is given by
WG={g∈V(G):Wg≠∅}. |
For instance, Figure 1 shows the graph P4∘P3, 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}.
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.
(ⅰ) dG∘H((g,h),(g′,h′))=dG(g,g′) for g≠g′.
(ⅱ) dG∘H((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 G∘H 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 g∈V(G) will be denoted by NG(g)={g′∈V(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 g∈V(G) is given by |NG(g)|.
For short, if (g,h)∈V(G∘H), then we will use the notation NG∘H(g,h), instead of NG∘H((g,h)).
Now, the open neighborhood of a set S⊆V(G) is defined to be NG(S)=∪g∈SNG(g), and the closed neighborhood as NG[S]=∪g∈SNG[g]=S∪NG(S). The minimum degree of G will be denoted by δ(G), i.e.,
δ(G)=min{|NG(g)|:g∈V(G)}. |
Now, the maximum degree of G will be denoted by Δ(G), i.e.,
Δ(G)=max{|NG(g)|:g∈V(G)}. |
Given two different vertices g,g′∈V(G), we define the bisector of g and g′ as
Bg|g′={u∈V(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 X⊆V(G) is a distance-equalizer set of G if X∩Bg|g′≠∅ for every pair of different vertices g,g′∈V(G)∖X.
Notice that, for every pair of different vertices g,g′∈V(G) and every h,h′∈V(H), the bisectors in G and the bisectors in G∘H 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 G∘H 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 S⊆V(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 G−u is the subgraph of G induced by V(G)∖{u}.
We shall show in Theorem 3.1 that if δ(G)=1, then either ξ(G∘H)=γ(H) or ξ(G∘H)=γ(H)+1, while if δ(G)≥2, then either ξ(G∘H)=min{γ(H),γt(G−u)+1} or ξ(G∘H)=1+min{γ(H),γt(G−u)}. In both cases, the problem of deciding the precise value of ξ(G∘H) will depend on the value of the pairwise domination number of H.
We say that a dominating set X⊆V(H) is a pairwise dominating set of H if, for any pair of vertices u,v∈V(H)∖X, there exists a vertex w∈X 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.
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 u∈V(G) be a vertex of degree Δ(G). The following statements hold for any graph H of order at least two.
(ⅰ) If δ(G)=1, then ξ(G∘H)={γ(H),ifγP(H)=γ(H),γ(H)+1,otherwise.
(ⅱ) If δ(G)≥2, then ξ(G∘H)={min{γ(H),γt(G−u)+1},ifγP(H)=γ(H),1+min{γ(H),γt(G−u)},otherwise.
Proof. Let u∈V(G) be a vertex of degree n(G)−1 and let S⊆V(H) be a γ(H)-set. We proceed to show that W={u}×S∪{(u′,v)} is a distance-equalizer set of G∘H for every u′∈V(G)∖{u} and v∈V(H). We differentiate the following cases for every pair of vertices (g,h),(g′,h′)∈V(G∘H)∖W.
(a) If g≠u and g′≠u, then (g,h) and (g′,h′) are adjacent to every vertex in {u}×S⊆W.
(b) If g=g′=u, then (g,h) and (g′,h′) are adjacent to (u′,v)∈W.
(c) If g=u and g′≠u, then (g,h) and (g′,h′) are adjacent to every vertex (u,s)∈W such that s∈S∩NH(h).
According to the three cases above, W is a distance-equalizer set of G∘H, which implies that ξ(G∘H)≤|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 G∘H (we leave the details to the reader). Therefore, in this case, ξ(G∘H)≤|{u}×X|=γ(H). In summary, for any graph H,
ξ(G∘H)≤{γ(H), if γP(H)=γ(H),γ(H)+1, otherwise. | (3.1) |
Let Z be a ξ(G∘H)-set where ZG has maximum cardinality among all ξ(G∘H)-sets. Without loss of generality, we can assume that u∈ZG. We differentiate the following three cases for the set Z.
Case 1. |ZG|=1. Since Zu⊆NG∘H(u′,v) for every u′∈V(G)∖{u} and every v∈V(H), we have that NG∘H(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(G∘H), where u′≠u, we have that Z′={u}×Y∪{(u′,v)} is a ξ(G∘H)-set with |Z′G|=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, ξ(G∘H)=|Zu|=γ(H)=γP(H).
Case 2. |ZG|=2. Let u′∈V(G)∖{u} such that Z=Zu∪Zu′. 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,
dG∘H((u,v),(u,h))=2≠1=dG∘H((u′,v′),(u,h)), |
and for every (u′,h′)∈Zu′,
dG∘H((u,v),(u′,h′))=1≠2=dG∘H((u′,v′),(u′,h′)), |
which is a contradiction. Therefore, either |Zu|≥γ(H) or |Zu′|≥γ(H), which implies that ξ(G∘H)=|Z|=|Zu|+|Zu′|≥γ(H)+1, and by (3.1) we can conclude that ξ(G∘H)=γ(H)+1. Notice that, in this case, γ(H)<γP(H).
Case 3. |ZG|≥3. If |Zg|≥γ(H) for some g∈ZG, then ξ(G∘H)=|Z|≥|Zg|+2≥γ(H)+2, which contradicts (3.1). Thus, |Zg|<γ(H) for every g∈ZG. As a result, for any g∈V(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 g≠u, there exists (g′,h′)∈Z∖(Zg∪Zu), which is adjacent to (g,hg) and (u,hu). As a result, ZG∖{u} is a total dominating set of G−u, and so ξ(G∘H)=|Z|≥|ZG∖{u}|+1≥γt(G−u)+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, G−u does not have isolated vertices. We claim that, by taking any γt(G−u)-set X′ and any vertex y∈V(H), it follows that W′=({u}∪X′)×{y} is a distance-equalizer set of G∘H. To prove this claim, we consider the following possibilities for two different vertices (g,h),(g′,h′)∈V(G∘H)∖W′.
(a') If g≠u and g′≠u, 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 g′≠u, then (g,h) and (g′,h′) are adjacent to every vertex (x,y)∈W′ such that x∈X′∩NG−u(g′).
Thus, W′ is a distance-equalizer set of G∘H, which implies that
ξ(G∘H)≤γt(G−u)+1. | (3.2) |
Therefore, in Case 3 we have ξ(G∘H)=γt(G−u)+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 ξ(G∘H)=min{γ(H),γt(G−u)+1}, while if γP(H)>γ(H), then the possibilities are Cases 2 and 3, and then ξ(G∘H)=min{γ(H)+1,γt(G−u)+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 ξ(G∘H)=n(H)−Δ(H).
(ⅱ) If δ(G)≥2, then ξ(G∘H)=min{n(H)−Δ(H),γt(G−u)+1}, where u∈V(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 ξ(G∘H)-set, then WG is a distance-equalizer set of G.
Proof. Assume that there are two different vertices g,g′∈V(G)∖WG. For every h∈V(H) there exists (u,v)∈W∩B(g,h)|(g′,h), and so u∈WG∩Bg|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)≤ξ(G∘H)≤ξ(G)n(H). |
Proof. Let W be a ξ(G∘H)-set. By Lemma 1, WG is a distance-equalizer set of G. Therefore,
ξ(G∘H)=|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 G∘H. To this end, let (g,h),(g′,h′)∈V(G∘H)∖W′. Obviously, g,g′∈V(G)∖X. Hence, if g=g′, then W′⊆(V(G)∖{g})×V(H)⊆B(g,h)|(g′,h′). Now, if g≠g′, then there exists x∈X∩Bg|g′, which implies that (x,y)∈W′∩B(g,h)|(g′,h′) for every y∈V(H). Therefore, W′ is a distance-equalizer set of G∘H and, as a result,
ξ(G∘H)≤|W′|=|X||V(H)|=ξ(G)n(H). |
Next, we discuss the tightness of these bounds. First, we characterize the graphs G such that ξ(G∘H)=ξ(G) for every graph H. If Bg|g′≠∅ for every pair of different vertices g,g′∈V(G), then there exists a set X⊆V(G) such that for every pair of different vertices g,g′∈V(G), there exists a vertex x∈X 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,g′∈V(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 n≥3, 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,g′∈V(G). In both cases, the set of black coloured vertices is a ξt(G)-set and ξt(G)=ξ(G).
Proposition 4.1. If G is a graph with ξt(G)<+∞, then ξ(G∘H)≤ξ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 G∘H, which implies that ξ(G∘H)≤ξt(G) for every graph H.
Proposition 4.2. Given a connected graph G of order at least two, the following statements are equivalent.
(ⅰ) ξ(G∘H)=ξ(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 ξ(G∘H)=ξ(G) for every graph H of order at least two. By Lemma 1, for any graph H and any ξ(G∘H)-set W, we have that WG is a ξ(G)-set, which implies that |Ww|=1 for every w∈WG. Now, suppose that there exist two different vertices g,g′∈V(G) such that Bg|g′∩WG=∅. We differentiate three cases.
Case 1. dG(g,g′)≥3. In this case, W∩B(g,h)|(g′,h′)⊆(WG∩Bg|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,h′∈V(H). If g∈WG, then we take h∈V(H) such that NG∘H(g,h)∩Wg≠∅, otherwise we take h as an arbitrary vertex of H. Analogously, if g′∈WG, then we take h′∈V(H) such that NG∘H(g′,h′)∩Wg′≠∅, otherwise we take h′ as an arbitrary vertex of H. Hence, W∩B(g,h)|(g′,h′)⊆(WG∩Bg|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,h′∈V(H) satisfying Wg∩({g}×NH[h])=∅ and Wg′∩({g′}×NH[h′])=∅. Hence, W∩B(g,h)|(g′,h′)⊆(WG∩Bg|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 ξ(G∘H)=ξ(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 A⊆X or B⊆X. 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 v∈V(G) there exists exactly one vertex v′∈V(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.
Proposition 4.4. Let G be a bipartite 2-antipodal graph G of diameter 2k+1≥3. If ξ(G)=n(G)2, then for any graph H,
ξ(G∘H)=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 ξ(G∘H)-set. By Lemma 4.1 and Proposition 4.3, we can assume that V1⊆WG. Let g∈V1 and let g′∈V2 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+1≥3, for every h,h′∈V(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, ξ(G∘H)≥|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 Pn∘H associated to ui∈V(Pn). Given a set W⊆V(Pn∘H), we define the sets Wi=W∩V(Hi) for every i∈{1,…,n}.
Lemma 5.1. For any integer n≥4 and any graph H of order at least two, there exists a ξ(Pn∘H)-set W satisfying the following properties.
(ⅰ) W1=∅.
(ⅱ) |W2|≥γ(H).
(ⅲ) |Wj|=n(H) for every even number j∈{4,…,n}.
Proof. Let W be a ξ(Pn∘H)-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 ξ(Pn∘H)<n(Pn∘H). Let Yi={h∈V(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+l−1 for every i∈{1,…,n−l+1} while Si={ui}×V(H) for every i∈{n−l+2,…,n}. Since S is a ξ(Pn∘H)-set with |S1|≤n(H)−1, we are done. With this fact in mind, from now on we can assume that W is a ξ(Pn∘H)-set such that |W1| is minimum among all ξ(Pn∘H)-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 ξ(Pn∘H)-set with |W′1|<|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 n≥4.
Proposition 5.1. For any graph H of order at least two, ξ(P4∘H)=γ(H)+n(H).
Proof. For any ξ(Pn∘H)-set X satisfying Lemma 5.1, we have ξ(P4∘H)=|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}×S∪V(H4) is a distance-equalizer set of P4∘H, which implies that ξ(P4∘H)≤|X′|=γ(H)+n(H).
Proposition 5.2. For any integer n≥5 and any graph H of order at least three,
ξ(Pn∘H)=⌊n2⌋⋅n(H)+⌈n−42⌉. |
Proof. For any v∈V(H), we define the set
W=(⌊n2⌋⋃i=1V(H2i))⋃(⌈n−42⌉⋃i=1{(u2i+1,v)}). |
Let (ui,w),(uj,w′)∈V(Pn∘H)∖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 i≠j, then W(i+j)/2≠∅, and so vertex (u(i+j)/2,v)∈W(i+j)/2⊆W is equidistant to (ui,w) and (uj,w′). Therefore, W is a distance-equalizer set of Pn∘H, which implies that
ξ(Pn∘H)≤|W|=⌊n2⌋⋅n(H)+⌈n−42⌉. | (5.1) |
We proceed to prove the lower bound ξ(Pn∘H)≥⌊n2⌋⋅n(H)+⌈n−42⌉. To this end, we take a ξ(Pn∘H)-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, ξ(P5∘H)=|X|≥|X2|+|X4|+|X5|≥1+2n(H)=⌊n2⌋⋅n(H)+⌈n−42⌉, 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, ξ(P5∘H)=|X|≥|X2|+|X4|+|X5|=3n(H)>⌊n2⌋⋅n(H)+⌈n−42⌉, which contradicts (5.1). Hence, X3≠∅, and so ξ(P5∘H)=|X|≥|X2|+|X3|+|X4|≥1+2n(H)=⌊n2⌋⋅n(H)+⌈n−42⌉, as required.
Case 2. n≥7. Suppose that |X2|≤n(H)−1. In such a case, Xj=V(Hj) for every odd number j≥5, as the distance from vertices in V(H2) to vertices in V(Hj) is odd. Since n≥7,
ξ(Pn∘H)=|X|≥|X2|+n∑i=4|Xi|≥1+(n−3)n(H)>⌊n2⌋⋅n(H)+⌈n−42⌉, |
which contradicts (5.1). Hence, Xi=V(Hi) for every even number i≤n. Thus, by taking I as the set of odd numbers belonging to {1,…,n}, we obtain that
ξ(Pn∘H)=|X|=⌊n2⌋⋅n(H)+∑j∈I|Xj|. | (5.2) |
We proceed now to show that ∑j∈I|Xj|≥⌈n−42⌉. Let I−=I∖{1,n}. We already know that the upper bound is reached when |Xj|=1 for every j∈I− and |X1|=|Xn|=0. Suppose to the contrary that there exists an odd number l∈I− such that Xl=∅. Since in Pn we have that Bul−2|ul+2={ul}, we conclude that |Xl−2|=n(H) or |Xl+2|=n(H). In general, if 3≤l≤n+12, then |Xl−2j|=n(H) or |Xl+2j|=n(H) for every j∈{1,…,l−12}, while if n+12≤l≤n−2, then |Xl−2j|=n(H) or |Xl+2j|=n(H) for every j∈{1,…,n−l2}. With these facts in mind, we take
l=maxj∈I{j:Xj=∅ and j≤n+12}. |
Hence, if n3≤l≤n+12, then
∑j∈I|Xj|≥l−12∑j=1(|Xl−2j|+|Xl+2j|)≥l−12n(H)≥n−36n(H)≥n−32=⌈n−42⌉. | (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 l≥n3 and consider that Xj≠∅ for every j∈I with j>n+12. In such a case, we have
∑j∈I|Xj|≥l−12n(H)+(|I|−1)−(l−1))≥32(l−1)+|I−|−(l−1))≥|I−|=⌈n−42⌉. | (5.4) |
Therefore, by combining (5.1) with (5.2) and (5.4), we obtain the result.
Assume that there exists j∈I with Xj=∅ and j>n+12. We define
l′=minj∈I{j:Xj=∅ and j≥n+12}. |
Now, if n+12≤l′≤2n3+1, then
∑j∈I|Xj|≥n−l′2∑j=1(|Xl′−2j|+|Xl′+2j|)≥n−l′2n(H)≥n−36n(H)≥n−32=⌈n−42⌉. | (5.5) |
Therefore, by combining (5.1) with (5.2) and (5.5), we obtain the result.
Now, if 1≤l≤n3−1 and 2n3+2≤l′≤n, then we have that |Xj|≥1 for every j∈I such that 2l+1≤j≤2l′−n−2. Thus, there are l′−l−n+12 different values for j with these requirements. In this case,
∑j∈I|Xj|≥l−12n(H)+n−l′2n(H)+(l′−l−n+12)≥32((n−1)−(l′−l))+12(2(l′−l)−(n+1))=12(2n−4−(l′−l))≥12(2n−4−(n−1))=n−32=⌈n−42⌉. |
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 X∖Xn is a distance-equalizer set of Pn−1∘H. Hence,
ξ(Pn∘H)=|X|≥ξ(Pn−1∘H)+n(H) =(⌊n−12⌋⋅n(H)+⌈n−52⌉)+n(H)=(n−22⋅n(H)+n−42)+n(H)=⌊n2⌋⋅n(H)+⌈n−42⌉. |
Therefore, from this bound and (5.1), we conclude the proof.
In this section, we will use the following notation. Let V(Cn)={u0,…,un−1}, where consecutive subscripts correspond to adjacent vertices of the cycle, and the addition of subscripts will be modulo n. As above, given a set W⊆V(Cn∘H), we define the sets Wi=W∩V(Hi) for every i∈{0,…,n−1}.
Since the case n=3 was previously considered in Theorem 3.1, we restrict ourselves to the case n≥4.
Proposition 6.1. Let H be a graph of order n(H)≥2. If, for any γ(H)-set S, there exists a vertex h∈V(H)∖S such that S⊆NH(h), then ξ(C4∘H)=2γ(H)+1, otherwise ξ(C4∘H)=2γ(H).
Proof. It is readily seen that if S is a γ(H)-set, then for any v∈V(H) we have that S′={u0,u2}×S∪{(u1,v)} is a distance-equalizer set of C4∘H. Thus,
ξ(C4∘H)≤|S′|=2|S|+1=2γ(H)+1. | (6.1) |
Now, if S∖NH(h)≠∅ for every vertex h∈V(H)∖S, then S″={u0,u2}×S is a distance-equalizer set of C4∘H, which implies that
ξ(C4∘H)≤|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 C4∘H, and so (6.2) follows.
From now on, let X be a ξ(C4∘H)-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
ξ(C4∘H)≥|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 S∖NH(h)≠∅ for every vertex h∈V(H)∖S, then ξ(C4∘H)=2γ(H).
Finally, assume that for any γ(H)-set A, there exists a vertex h∈V(H)∖A such that A⊆NH(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=Xj−1=∅, 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 Xj⊆NHj(uj,h) and Xj+2⊆NHj+2(uj+2,h′), which is a contradiction. Thus, |Xj+1|+|Xj−1|≥1, and so
ξ(C4∘H)=|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 ξ(C5∘H)=4, otherwise, ξ(C5∘H)=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 h∈V(H) is a vertex of degree one and h′∈V(H)∖{h} is a universal vertex, then X={u0,u2,u3}×{h′}∪{(u0,h)} is a distance-equalizer set, and so ξ(C5∘H)≤|X|=4.
It is easy to check that no set of cardinality three is a distance-equalizer set of C5∘H. Therefore, ξ(C5∘H)=4.
From now on, assume that γ(H)≥2 or δ(H)≠1. We already know that ξ(C5∘H)≤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 C5∘H. Therefore, ξ(C5∘H)≥5.
It was shown in [9] that ξ(Cn)≥n−12 for every odd integer n≥3. We proceed too show that the bound can be improved for n≥5.
Lemma 6.1. If n≥5 is an odd integer, then ξ(Cn)≥n+12.
Proof. Let W be a ξ(Cn)-set and let V(Cn)={0,…,n−1}, 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,n−1}=∅. Since n is an odd integer, for any i∈{1,…,n−12}, we have that Bi|n−i={0}. Thus, from 0∉W, we deduce that i∈W or n−i∈W, which implies that ξ(Cn)≥n−12.
Suppose that ξ(Cn)=n−12. Notice that, in this case, |W∩{i,n−i}|=1 for every i∈{1,…,n−12}. Now, since W∩{0,n−1}=∅, we have that n−12∈W, and since |W∩{n−12,n+12}|=1, we have that n+12∉W. If n≡1(mod4), then Bn−1|n+12={n−14} and B0|n+12={n−n−14}, which is a contradiction, as |W∩{n−14,n−n−14}|=1. Analogously, if n≡3(mod4), then B0|n+12={n+14} and Bn−1|n+12={n−n+14}, which is a contradiction, as |W∩{n+14,n−n+14}|=1. Therefore, ξ(Cn)≥n−12+1=n+12.
Proposition 6.3. Let H be a graph of order at least two. If n≥7 is an odd integer, then ξ(Cn∘H)=n.
Proof. By Proposition 4.1, we conclude that ξ(Cn∘H)≤n. Hence, we proceed to show that ξ(Cn∘H)≥n.
Let W be a ξ(Cn∘H)-set and let k=n−12. If Wi≠∅ for every i∈{0,…,n−1}, then ξ(Cn∘H)=∑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 (un−i,y′)∈V(Hn−i)∖Wn−i have to be equalized by W, we deduce the following constraints, where λ=1 if δ(H)=0 while λ≥2 otherwise,
|W1|≥λor|Wn−1|≥λ,|W2|=n(H)or|Wn−2|=n(H),⋮|Wk−1|=n(H)or|Wk+2|=n(H),|Wk|≥γ(H)or|Wk+1|≥γ(H). |
Hence,
ξ(Cn∘H)=n−1∑i=0|Wi|≥λ+(k−2)n(H)+γ(H). | (6.5) |
Suppose that ∑n−1i=0|Wi|=λ+(k−2)n(H)+γ(H). In such a case, |WCn|=n−12, and by combining Lemmas 4.1 and 6.1, we obtain n−12=|WCn|≥ξ(Cn)≥n+12, which is a contradiction. Thus,
ξ(Cn∘H)=n−1∑i=0|Wi|≥1+λ+(k−2)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
ξ(Cn∘H)=n−1∑i=0|Wi|≥4+(k−2)n(H)≥4+3(k−2)=(2k+1)+(k−3)≥2k+1=n, |
as required.
From now on, assume n(H)=2. We consider first H≅K2. In this case, λ=2 and γ(H)=1. Without loss of generality, we can assume that |W1|=2. Thus, if |Wn−1|=2, then ξ(Cn∘K2)=∑n−1i=0|Wi|≥4+2(k−2)+1=2k+1=n and we are done. Suppose that |Wn−1|≤1.
Case 1. |Wn−1|=1. If |Wk+1|=2, then we are done, as ξ(Cn∘K2)=∑n−1i=0|Wi|≥3+2(k−2)+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 z0∈V(H0), zn−1∈V(Hn−1)∖Wn−1 and zk+1∈V(Hk+1)∖Wk+1. Notice that if n≡1(mod4), then Bzn−1|zk+1=V(Hk2) and Bz0|zk+1=V(Hn−k2), which implies that Wk2≠∅ and Wn−k2≠∅, and so |Wk2|+|Wn−k2|≥3. Hence, ξ(Cn∘K2)=∑n−1i=0|Wi|≥3+(2(k−2)+1)+1=2k+1=n, as required. Analogously, if n≡3(mod4), then Bz0|zk+1=V(Hk+12) and Bzn−1|zk+1=V(Hk+12), which implies that Wk+12≠∅ and Wn−k+12≠∅, and so |Wk+12|+|Wn−k+12|≥3. Hence, ξ(Cn∘K2)=∑n−1i=0|Wi|≥3+(2(k−2)+1)+1=2k+1=n, as required.
Case 2. Wn−1=∅. Observe that |Wk|≥1, as Bz0|zn−1=V(Hk). Now, if |Wk+1|=2, then we are done, as ξ(Cn∘K2)=∑n−1i=0|Wi|≥2+2(k−2)+3=2k+1=n. Assume |Wk+1|≤1. Notice also that |Wn−2|=2. If |W2|=2, then we are done, as ξ(Cn∘K2)=∑n−1i=0|Wi|≥2+(2(k−2)+2)+1=2k+1=n. Assume |W2|≤1. Thus, |Wk+1|=1, as for every z2∈V(H2)∖W2 we have that Bz2|zn−1=V(Hk+1). As in Case 1, if n≡1(mod4), then we reach to |Wk2|+|Wn−k2|≥3, and so ξ(Cn∘K2)=∑n−1i=0|Wi|≥2+(2(k−2)+1)+2=2k+1=n, as required. Analogously, if n≡3(mod4), then we reach to |Wk+12|+|Wn−k+12|≥3. Hence, ξ(Cn∘K2)=∑n−1i=0|Wi|≥2+(2(k−2)+1)+2=2k+1=n, as required.
According to the two cases above, the proof is complete for H≅K2. From now on we assume that H is the empty graph, i.e., H≅N2. In this case, λ=1 and γ(H)=2. Without loss of generality, we can assume that |Wk|=2. Thus, if |Wk+1|=2, then ξ(Cn∘K2)=∑n−1i=0|Wi|≥1+2(k−2)+4=2k+1=n and we are done. From now on, we assume that |Wk+1|≤1. Now, if |W1|+|Wn−1|≥3, then we are done, as ξ(Cn∘K2)=∑n−1i=0|Wi|≥3+2(k−2)+2=2k+1=n. Thus, we assume 1≤|W1|+|Wn−1|≤2 and we differentiate the following cases.
Case 1'. |W1|=0 and |Wn−1|=2. In this case, |Wk+1|=1 and so ξ(Cn∘K2)=∑n−1i=0|Wi|≥2+2(k−2)+3=2k+1=n.
Case 2'. |W1|=2 and |Wn−1|=0. By analogy to Case 1, we deduce that either |Wk2|+|Wn−k2|≥3 or |Wk+12|+|Wn−k+12|≥3. Hence, we reach to ξ(Cn∘K2)=∑n−1i=0|Wi|≥2+(2(k−2)+1)+2=2k+1=n.
Case 3'. |W1|=1 and |Wn−1|≤1. In this case, we have that |Wk+1|=1 and, as above, we deduce that either |Wk2|+|Wn−k2|≥3 or |Wk+12|+|Wn−k+12|≥3. Hence, we reach to ξ(Cn∘K2)=∑n−1i=0|Wi|≥1+(2(k−2)+1)+3=2k+1=n.
Case 4'. |W1|≤1 and |Wn−1|=1. This case is analogous to the previous one.
According to the four cases above, the proof is complete.
Proposition 6.4. Let n≥6 be an integer. The following statements hold for any graph H of order at least two.
(a) If n≡2(mod4), then ξ(Cn∘H)=n2⋅n(H).
(b) If n≡0(mod4), then ξ(Cn∘H)=n2⋅n(H)+n4.
Proof. If n≡2(mod4), then Proposition 4 leads to ξ(Cn∘H)=n2⋅n(H). From now on, we assume that n≡0(mod4) and n≥8. Let U⊆V(Cn∘H) be a set satisfying the following properties:
● |Ui|=n(H) whenever i is odd.
● |Ui∪Ui+n/2|=1 whenever i≡0(mod2).
A simple case analysis shows that U is a distance-equalizer set of Cn∘H. Hence,
ξ(Cn∘H)≤|U|=n2⋅n(H)+n4. | (6.7) |
It remains necessary to prove that ξ(Cn∘H)≥n2⋅n(H)+n4. Let W be a ξ(Cn∘H)-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,h′∈V(H) and k∈{1,…,n−42}, we have that B(u0,h)|(u2k+1,h′)=∅. Thus, |W2k+1|=n(H) for every k∈{1,…,n−42}. By analogy, we deduce that |W2k+2|=n(H) for every k∈{1,…,n−42}. Furthermore, |Wn−1|=n(H) or |W2|=n(H), as B(un−1,h)|(u2,h′)=∅ for every h,h′∈V(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,
ξ(Cn∘H)≥1+n(H)+(n−4)n(H)>n2⋅n(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 |Wn−2j|=n(H) for every j∈{1,…,n−44}. 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,
ξ(Cn∘H)=|W|=n−22∑i=0|W2l+1|+n−22∑i=0|W2l|≥n2⋅n(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 k≤n(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 k≤n(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 X⊆V(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′=(G∗∘H,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 bi∈V(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∗.
Now, we proceed to show that if S⊆V(H) is a dominating set of H with |S|≤k, then X×S is a distance-equalizer of G∗∘H with |X×S|≤k′. To this end, we differentiate the following cases for two different vertices (g,h),(g′,h′)∈V(G∘H)∖X×S and, for each of these cases, we will show that there exists at least one vertex (x,s)∈X×S such that dG∘H((x,s),(g,h))=dG∘H((x,s),(g′,h′)).
Case 1. g=g′. For every ai∈X∖{g} and every s∈S we have that (ai,s)∈X×S and by Remark 2.1 we have
dG∘H((ai,s),(g,h))=dG(ai,g)=dG(ai,g′)=dG∘H((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 h∈V(H)∖S and S is a dominating set of H, there exists at least one vertex s∈S∩NH(h). Hence, (ai,s)∈X×S and by Remark 2.1 we have
dG∘H((ai,s),(g,h))=dG∘H((ai,s),(ai,h))=dH(s,h)=1=dG(ai,bi)=dG∘H((ai,s),(bi,h))=dG∘H((ai,s),(g′,h′)). |
Case 3. g≠g′ 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 s∈S we have that (aj,s)∈X×S and by Remark 2.1 we have
dG∘H((aj,s),(g,h))=dG(aj,g)=dG(aj,g′)=dG∘H((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 j≠l, 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 s∈S∩NH(h′) and so dG∘H((g′,h′),(ai,s))=dH(h′,s)=1=dG(g,ai)=dG∘H((g,h),(ai,s)). According to the three cases above, X×S is a distance-equalizer of G∗∘H.
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 G∗∘H 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 Wai∩NG∘H(ai,h)=∅ and there exists at least one vertex (bi,h′)∈V(Hbi)∖Wbi such that Wbi∩NG∘H(bi,h′)=∅. We proceed to show that, with the assumptions above, dG∘H((x,y),(ai,h))≠dG∘H((x,y),(bi,h′)) for every (x,y)∈W. To this end, we differentiate the following three cases.
Case 1'. (x,y)∈W∖(Wai∪Wbi). In this case, x≠ai and x≠bi, which implies that
dG∘H((x,y),(ai,h))=dG(x,ai)≠dG(x,ai)+dG(ai,bi)=dG(x,bi)=dG∘H((x,y),(bi,h′)). |
Case 2'. (x,y)∈Wai. In this case, x=ai. Since (ai,h)∈V(Hai)∖Wai and Wai∩NG∘H(ai,h)=∅, we have that dG∘H((x,y),(ai,h))=2. On the other side, dG∘H((x,y),(bi,h′))=dG∘H((ai,y),(bi,h′))=dG(ai,bi)=1. Therefore, dG∘H((x,y),(ai,h))≠dG∘H((x,y),(bi,h′)).
Case 3'. (x,y)∈Wbi. In this case, x=bi. Now, since (bi,h′)∈V(Hbi)∖Wbi and Wbi∩NG∘H(bi,h′)=∅, we have that dG∘H((x,y),(bi,h′))=2. On the other side, dG∘H((x,y),(ai,h))=dG∘H((bi,y),(ai,h))=dG(bi,ai)=1. Therefore, dG∘H((x,y),(ai,h))≠dG∘H((x,y),(bi,h′)).
According to the three cases above, dG∘H((x,y),(ai,h))≠dG∘H((x,y),(bi,h′)) for every (x,y)∈W, which contradicts the fact that W is a distance-equalizer set of G∗∘H. 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 ξ(G∗∘P4)-set.
In this paper, we deal with the problem of finding the equidistant dimension of the lexicographic product G∘H 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)≤ξ(G∘H)≤ξ(G)n(H) for every connected graph G and every graph H. The discussion of the case ξ(G∘H)=ξ(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 ξ(G∘H) 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 ξ(G∘H)=ξ(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+1≥3 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+1≥3 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 n≥5 and n∉{9,10} we conjecture that ξ(Pn∘H)=3n−52 whenever n is odd, and ξ(Pn∘H)=3n−42 whenever n is even, while ξ(P9∘H)=10 and ξ(P10∘H)=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
![]() |
1. | S. Gajavalli, A. Berin Greeni, On strong geodeticity in the lexicographic product of graphs, 2024, 9, 2473-6988, 20367, 10.3934/math.2024991 |