betaFeedback

WorksMathematics

On two problems concerning the geodesic transversal number of graphs

Abstract

We establish sharp upper and lower bounds on the geodesic transversal number of hypercubes. We also obtain a lower bound on the geodesic transversal number of Hamming graphs. As applications, we provide negative answers to two open problems concerning the geodesic transversal number.

Introduction

Every graph considered in this paper is finite, simple, and connected. Let GG be a graph. We always use V(G)V(G) and E(G)E(G) to denote the vertex set and edge set of GG, respectively. Given two vertices uu and vv in GG, the distance between uu and vv is denoted by dG(u,v)d_G(u,v), or simply by d(u,v)d(u,v) when no confusion can arise. For two distinct vertices x,y∈V(G)x,y \in V(G), we say a vertex v∈V(G)v \in V(G) distinguishes xx and yy whenever d(v,x)≠d(v,y)d(v,x) \ne d(v,y). A subset S⊆V(G)S \subseteq V(G) is called a metric generator of GG if for every pair of distinct vertices x,y∈V(G)x,y \in V(G), there exists a vertex in SS such that it distinguishes xx and yy. A metric generator of GG with minimum cardinality is called a metric basis of GG, and the cardinality of a metric basis is referred to as the metric dimension of GG. In the 1970s, the concept of a metric dimension was introduced independently by Harary and Melter [2], and Slater [10]. The metric dimension of a graph has a wide range of applications, including robot navigation in networks, chemistry, pattern recognition and image processing, and so on (see [11]).

Given a vertex v∈V(G)v \in V(G) and an edge e={u,w}∈E(G)e = \{u,w\} \in E(G), the distance d(v,e)d(v,e) between vv and ee is defined by d(v,e)=min⁡{d(v,u),d(v,w)}d(v,e) = \min\{d(v,u),d(v,w)\}. Let O(G)=V(G)∪E(G)O(G) = V(G) \cup E(G). We say a vertex vv of GG distinguishes two distinct elements x,y∈O(G)x,y \in O(G) (vertices or edges) if d(v,x)≠d(v,y)d(v,x) \ne d(v,y). For a subset SS of V(G)V(G), we say SS is a mixed metric generator of GG provided that, for every pair of distinct elements x,y∈O(G)x,y \in O(G), there exists a vertex in SS such that it distinguishes xx and yy. The cardinality of a mixed metric generator with minimum size, denoted by mdim⁡(G)\operatorname{mdim}(G), is called the mixed metric dimension of GG. Kelenc et al. [4] first introduced the concept of a mixed metric dimension. In [4], it was proved that computing the mixed metric dimension of a general graph is NP-hard.

Let x,y∈V(G)x,y \in V(G). A geodesic is a shortest path between a pair of vertices in a graph. In particular, if PP is a shortest path from xx to yy, then PP is called a x−yx-y geodesic. A geodesic PP in a graph is said to be maximal if there exists no other geodesic in GG, which contains PP as a sub-path. A subset SS of V(G)V(G) is a geodesic transversal of GG provided that any maximal geodesic in GG contains at least one vertex in SS. The geodesic transversal number of GG, denoted by gt⁡(G)\operatorname{gt}(G), is the minimum cardinality of a geodesic transversal of GG. The geodesic transversal number of a graph is also known as the maximal shortest paths cover number of a graph; see, for example, [8]. The geodesic transversal number of join and lexicographic product of graphs was studied in [9] A vertex subset SS is called a gt-set of GG if SS is a geodesic transversal of GG such that ∣S∣=gt⁡(G)|S| = \operatorname{gt}(G). The geodesic-transversal problem is NP-complete [6]. A geodesic packing of GG is a set of vertex-disjoint maximal geodesics. The maximum cardinality of a geodesic packing of GG is called the geodesic packing number of GG, and is denoted by gpack⁡(G)\operatorname{gpack}(G). In fact, the geodesic transversal problem and the geodesic packing problem are dual min-max invariant problems. It is proved in [7] that the decision version of the geodesic packing number is NP-complete.

In [3], the authors obtained some results on the mixed metric dimension and geodesic transversal number of a graph. They showed that gt⁡(G)≤mdim⁡(G)\operatorname{gt}(G) \le\operatorname{mdim}(G) holds for any tree, unicyclic graph, and block graph. Thus, they posed the following problem.

Problem 1.1 ([3 Problem 5.1]) Does gt⁡(G)≤mdim⁡(G)\operatorname{gt}(G) \le\operatorname{mdim}(G) hold for every connected graph GG?

In [7], it was proved that gpack⁡(G)≤gt⁡(G)\operatorname{gpack}(G) \le\operatorname{gt}(G) for any graph GG, and the upper bound is sharp. Moreover, gt⁡(G)\operatorname{gt}(G) can be arbitrarily bigger than gpack⁡(G)\operatorname{gpack}(G); see, for example, gt⁡(Kn)=n−1\operatorname{gt}(K_n) = n-1 and gpack⁡(Kn)=⌊n2⌋\operatorname{gpack}(K_n) = \left\lfloor\frac{n}{2} \right\rfloor. Clearly, in Kn,nK_{n,n} (n≥2n \ge2), any maximal geodesic has length 22. Thus, gpack⁡(Kn,n)=⌊2n3⌋\operatorname{gpack}(K_{n,n}) = \left\lfloor\frac{2n}{3} \right\rfloor and gt⁡(Kn,n)=n\operatorname{gt}(K_{n,n}) = n. As a result, gt⁡(Kn,n)/gpack⁡(Kn,n)\operatorname{gt}(K_{n,n})/\operatorname{gpack}(K_{n,n}) is less than or equal to an absolute constant. For any graph GG, the following problem was posed.

Problem 1.2 [7 Problem 2.5] Is there an absolute constant CC such that gt⁡(G)gpack⁡(G)≤C\frac{\operatorname{gt}(G)}{\operatorname{gpack}(G)} \le C, for all graphs GG?

In this paper, we establish sharp upper and lower bounds on the geodesic transversal number of hypercubes. We also obtain a lower bound on the geodesic transversal number of Hamming graphs. As applications, we give negative answers to Problems 1.1 and 1.2.

Preliminaries

The nn-dimensional hypercube QnQ_n has vertex set

V(Qn)={0,1}n={(x1,x2,…,xn):xi∈{0,1} for any 1≤i≤n}.V(Q_n)=\{0,1\}^{n}=\{(x_1,x_2,\ldots,x_n):x_i\in\{0,1\}\text{ for any }1\leq i\leq n\}.

Namely, every vertex of QnQ_n is an nn-tuple whose coordinate is either 0 or 1. Two vertices in QnQ_n are adjacent if and only if they differ in exactly one coordinate. Let x=(x1,x2,…,xn)∈V(Qn)x=(x_1,x_2,\ldots,x_n)\in V(Q_n). The complement of xx is denoted by xˉ\bar{x}, that is

xˉ=(1−x1,1−x2,…,1−xn).\bar{x}=(1-x_1,1-x_2,\ldots,1-x_n).

Moreover, we write ∣x∣=∑i=1nxi|x|=\sum_{i=1}^{n}x_i, that is, ∣x∣|x| denotes the number of 1-entries in the vector xx. For two vertices x,yx,y of V(Qn)V(Q_n), let x⊕yx\oplus y denote their bitwise addition modulo 2. For example, if x=(1,0,1,0)x=(1,0,1,0) and y=(1,1,1,0)y=(1,1,1,0), then x⊕y=(0,1,0,0)x\oplus y=(0,1,0,0). For any S⊆V(Qn)S\subseteq V(Q_n) and x∈V(Qn)x\in V(Q_n), define

S⊕x={s⊕x:s∈S}.S\oplus x=\{s\oplus x:s\in S\}.

It is easy to see that ∣S⊕x∣=∣S∣|S\oplus x|=|S|.

By the basic properties of QnQ_n, the following is valid.

Remark 2.1 A path P=(a,a1,…,an)P=(a,a_1,\ldots,a_n) of QnQ_n is a maximal geodesic if and only if aˉ=an\bar{a}=a_n, and each coordinate changes exactly once along PP. More precisely, let x=(x1,…,xn)∈V(Qn)x=(x_1,\ldots,x_n)\in V(Q_n), and let π\pi be a permutation of {1,…,n}\{1,\ldots,n\}. Define

x(0)=x,x(k)=x⊕eπ(1)⊕⋯⊕eπ(k),1≤k≤n,x^{(0)}=x,\qquad x^{(k)}=x\oplus e_{\pi(1)}\oplus\cdots\oplus e_{\pi(k)},\qquad1\leq k\leq n,

where eie_i is the ii-th standard unit vector. We have that

P=(x(0),x(1),…,x(n))P=(x^{(0)},x^{(1)},\ldots,x^{(n)})

is a maximal geodesic of QnQ_n.

For k≥1k\geq1 and n≥2n\geq2, Hamming graph H(k,n)H(k,n) is the graph with vertex set

{(x1,x2,…,xk):xi∈{0,1,2,…,n−1} for each 1≤i≤k},\{(x_1,x_2,\ldots,x_k):x_i\in\{0,1,2,\ldots,n-1\}\text{ for each }1\leq i\leq k\},

in which two vertices are adjacent if and only if they differ in exactly one coordinate. In general, we denote V(H(k,n))V(H(k,n)) by {0,1,…,n−1}k\{0,1,\ldots,n-1\}^{k}. Thus, H(k,n)H(k,n) has nkn^k vertices and is k(n−1)k(n-1)-regular. The distance between two vertices equals the number of coordinates in which they differ. Consequently, H(k,n)H(k,n) has diameter kk. Moreover, every maximal geodesic of H(k,n)H(k,n) has length kk and contains k+1k+1 vertices. In particular, H(k,2)H(k,2) is the kk-dimensional hypercube QkQ_k.

The following result will be used in the proof of the subsequent theorems.

Lemma 2.2 Let A0,A1,…,AmA_0,A_1,\ldots,A_m be m+1m+1 finite sets, and let U=⋃j=0mAjU=\bigcup_{j=0}^{m}A_j. For any x∈Ux\in U, let Ix={j∈{0,1,…,m}:x∈Aj}I_x=\{j\in\{0,1,\ldots,m\}:x\in A_j\}, and let rxr_x be the number of maximal intervals of consecutive integers in IxI_x. Then

∑j=0m∣Aj∣−∣U∣−∑j=1m∣Aj−1∩Aj∣=∑x∈U(rx−1).\sum_{j=0}^{m}|A_j|-|U|-\sum_{j=1}^{m}|A_{j-1}\cap A_j|=\sum_{x\in U}(r_x-1).

In particular, we have

∣U∣+∑j=1m∣Aj−1∩Aj∣≤∑j=0m∣Aj∣.|U|+\sum_{j=1}^{m}|A_{j-1}\cap A_j|\leq\sum_{j=0}^{m}|A_j|.

Proof. For any x∈Ux\in U, we have rx≥1r_x\geq1. Set kx=∣Ix∣k_x=|I_x|. Clearly, kx≥1k_x\geq1, and

∑j=0m∣Aj∣=∑x∈Ukx.\sum_{j=0}^{m}|A_j|=\sum_{x\in U}k_x.

Now, consider the sum ∑j=1m∣Aj−1∩Aj∣\sum_{j=1}^{m}|A_{j-1}\cap A_j|. For fixed x∈Ux\in U, its contribution to this sum equals the number of indices jj such that both j−1j-1 and jj belong to IxI_x. Since IxI_x consists of rxr_x maximal intervals of consecutive integers and contains kxk_x integers in total, the number of such adjacent pairs is kx−rxk_x-r_x. Indeed, an interval containing ℓ\ell integers contributes exactly ℓ−1\ell-1 adjacent pairs. Summing over all rxr_x intervals gives kx−rxk_x-r_x. As a result, we have that

∑j=1m∣Aj−1∩Aj∣=∑x∈U(kx−rx).\sum_{j=1}^{m}|A_{j-1}\cap A_j|=\sum_{x\in U}(k_x-r_x).

It follows that

∑j=0m∣Aj∣−∣U∣−∑j=1m∣Aj−1∩Aj∣=∑x∈Ukx−∑x∈U1−∑x∈U(kx−rx)=∑x∈U(rx−1),\sum_{j=0}^{m}|A_j|-|U|-\sum_{j=1}^{m}|A_{j-1}\cap A_j|=\sum_{x\in U}k_x-\sum_{x\in U}1-\sum_{x\in U}(k_x-r_x)=\sum_{x\in U}(r_x-1),

as desired. □\square

The geodesic transversal number of hypercubes

The main result of this section is the following theorem:

Theorem 3.1 For any n≥2n\geq2, we have

⌈2n⌊n/2⌋+1⌉≤gt⁡(Qn)≤(n⌊n/2⌋).\left\lceil\frac{2^n}{\lfloor n/2\rfloor+1}\right\rceil\leq\operatorname{gt}(Q_n)\leq\binom{n}{\lfloor n/2\rfloor}.

As an application of the above result, we will give a negative answer to Problem 1.1. We begin by proving the following lemma.

Lemma 3.2 For any n≥1n\geq1, we have that gt⁡(Qn)≤(n⌊n/2⌋)\operatorname{gt}(Q_n)\leq\binom{n}{\lfloor n/2\rfloor}.

Proof. Let

L={x∈V(Qn):∣x∣=⌊n2⌋}.L=\left\{x\in V(Q_n): |x|=\left\lfloor\frac{n}{2}\right\rfloor\right\}.

Then ∣L∣=(n⌊n/2⌋)|L|=\binom{n}{\lfloor n/2\rfloor}. It suffices to prove that LL is a geodesic transversal. Now let

P=(v0,v1,…,vn)P=(v_0,v_1,\ldots,v_n)

be a maximal geodesic of QnQ_n. Thus, by Remark 2.1, we see that vn‾=v0\overline{v_n}=v_0. Set ∣v0∣=r|v_0|=r. Then ∣vn∣=n−r|v_n|=n-r. Now without loss of generality, assume that r≤n−rr\leq n-r. Then

∣v0∣≤n2,∣vn∣≥n2.|v_0|\leq\frac{n}{2},\qquad|v_n|\geq\frac{n}{2}.

Note that, by Remark 2.1, each coordinate changes exactly once along PP. It follows that

∣vi∣−∣vi−1∣=1,1≤i≤n.\lvert v_i\rvert-\lvert v_{i-1}\rvert=1,\qquad1\le i\le n.

As a result, there exists at least one index ll in {0,1,2,…,n}\{0,1,2,\ldots,n\} such that ∣vl∣=⌊n/2⌋\lvert v_l\rvert=\lfloor n/2\rfloor. It follows that vl∈Lv_l\in L, and so LL is a geodesic transversal, as desired. □\square

Lemma 3.3 For any n≥2n\ge2, we have that gt⁡(Qn)≥⌈2n⌊n/2⌋+1⌉\operatorname{gt}(Q_n)\ge\left\lceil\frac{2^n}{\lfloor n/2\rfloor+1}\right\rceil.

Proof. Suppose that SS is a gt-set of QnQ_n. Let x∈V(Qn)x\in V(Q_n). In the following, we consider two cases for nn.

Case 1. n=2mn=2m, where m≥1m\ge1.

Set

q0=0,qj=e1⊕e2⊕⋯⊕e2j,1≤j≤m.(1)q_0=0,\qquad q_j=e_1\mathbin{\oplus}e_2\mathbin{\oplus}\cdots\mathbin{\oplus}e_{2j},\qquad1\le j\le m. \tag*{(1)}

where eie_i is the ii-th standard unit vector. For any 1≤j≤m1\le j\le m, let

yi∈Ti:={x⊕qj−1⊕e2j,x⊕qj−1⊕e2j−1}.(2)y_i\in T_i:=\{x\mathbin{\oplus}q_{j-1}\mathbin{\oplus}e_{2j},x\mathbin{\oplus}q_{j-1}\mathbin{\oplus}e_{2j-1}\}. \tag*{(2)}

Then by Remark 2.1, we see that

(x,y1,x⊕q1,y2,x⊕q2,…,ym,x⊕qm)(3)(x,y_1,x\mathbin{\oplus}q_1,y_2,x\mathbin{\oplus}q_2,\ldots,y_m,x\mathbin{\oplus}q_m) \tag*{(3)}

is a maximal geodesic. If x⊕qi∉Sx\mathbin{\oplus}q_i\notin S for each 0≤i≤m0\le i\le m, and Ti⊈ST_i\not\subseteq S for each 1≤j≤m1\le j\le m, then by (3), we can choose a maximal geodesic from xx to x⊕qmx\mathbin{\oplus}q_m such that every vertex in this maximal geodesic does not belong to SS, which contradicts the definition of SS. We conclude that

x⊕qi∈S for some 0≤i≤m(4)x\mathbin{\oplus}q_i\in S\text{ for some }0\le i\le m \tag*{(4)}

or

Tj⊆S for some 1≤j≤m.(5)T_j\subseteq S\text{ for some }1\le j\le m. \tag*{(5)}

For any y∈V(Qn)y\in V(Q_n), write

Ai=S⊕qi,0≤i≤m.A_i=S\mathbin{\oplus}q_i,\qquad0\le i\le m.

Note that −1≡1(mod2)-1\equiv1\pmod2. Thus, (4) is equivalent to

x∈⋃i=0mAi.x\in\bigcup_{i=0}^{m}A_i.

Furthermore, since qj=qj−1⊕e2j−1⊕e2jq_j=q_{j-1}\mathbin{\oplus}e_{2j-1}\mathbin{\oplus}e_{2j} for each 1≤j≤m1\le j\le m, we deduce that (5) is equivalent to

x∈(Aj−1∩Aj)⊕e2j−1 for some 1≤j≤m.x\in(A_{j-1}\cap A_j)\mathbin{\oplus}e_{2j-1}\text{ for some }1\le j\le m.

Now, in either (4) or (5), it follows that

V(Qn)⊆(⋃j=0mAj)∪(⋃i=1m((Ai−1∩Ai)⊕e2i−1)),V(Q_n)\subseteq\left(\bigcup_{j=0}^{m}A_j\right)\cup\left(\bigcup_{i=1}^{m}\left((A_{i-1}\cap A_i)\mathbin{\oplus}e_{2i-1}\right)\right),

and hence, we have

22m≤∣⋃j=0mAj∣+∑i=1m∣Ai−1∩Ai∣.2^{2m} \le\left|\bigcup_{j=0}^{m} A_j\right|+\sum_{i=1}^{m}|A_{i-1}\cap A_i|.

In view of Lemma 2.2, we deduce that 22m≤∑j=0m∣Aj∣=(m+1)∣S∣2^{2m}\le\sum_{j=0}^{m}|A_j|=(m+1)|S|, which implies that ∣S∣≥22mm+1|S|\ge\frac{2^{2m}}{m+1}. In other words, we obtain

gt⁡(Q2m)≥⌈22mm+1⌉.(6)\operatorname{gt}(Q_{2m})\ge\left\lceil\frac{2^{2m}}{m+1}\right\rceil. \tag*{(6)}

Case 2. n=2m+1n=2m+1, where m≥1m\ge1.

Assume first (1) and (2). Then, according to Remark 2.1, we infer that

(x,y1,x⊕q1,y2,x⊕q2,…,ym,x⊕qm,x⊕qm⊕e2m+1)(x,y_1,x\oplus q_1,y_2,x\oplus q_2,\ldots,y_m,x\oplus q_m,x\oplus q_m\oplus e_{2m+1})

is a maximal geodesic. Let

Ai=S⊕qi,Am+1=S⊕⨁j=1nej,0≤i≤m.A_i=S\oplus q_i,\quad A_{m+1}=S\oplus\bigoplus_{j=1}^{n}e_j,\quad0\le i\le m.

Then, similar to the proof of Case 1, we conclude that

22m+1≤∣⋃j=0m+1Aj∣+∑i=1m∣Ai−1∩Ai∣.(7)2^{2m+1}\le\left|\bigcup_{j=0}^{m+1} A_j\right|+\sum_{i=1}^{m}|A_{i-1}\cap A_i|. \tag*{(7)}

Combining (7) and Lemma 2.2, we obtain

22m+1≤∣⋃j=0m+1Aj∣+∑i=1m∣Ai−1∩Ai∣+∣Am∩Am+1∣≤∑j=0m+1∣Aj∣=(m+2)∣S∣.2^{2m+1}\le\left|\bigcup_{j=0}^{m+1} A_j\right|+\sum_{i=1}^{m}|A_{i-1}\cap A_i|+|A_m\cap A_{m+1}|\le\sum_{j=0}^{m+1}|A_j|=(m+2)|S|.

As a result,

gt⁡(Q2m+1)≥⌈22m+1m+2⌉.(8)\operatorname{gt}(Q_{2m+1})\ge\left\lceil\frac{2^{2m+1}}{m+2}\right\rceil. \tag*{(8)}

Finally, combining (6) and (8), we have gt⁡(Qn)≥⌈2n⌈n/2⌉+1⌉\operatorname{gt}(Q_n)\ge\left\lceil\frac{2^n}{\lceil n/2\rceil+1}\right\rceil, as desired. □\square

Now, Theorem 3.1 follows from Lemmas 3.2 and 3.3.

Remark 3.4 It is straightforward to verify that gt⁡(Q2)=2\operatorname{gt}(Q_2)=2 and gt⁡(Q3)=3\operatorname{gt}(Q_3)=3. Thus, both the upper and lower bounds in Theorem 3.1 are sharp. In fact, by Theorem 3.1, we also can obtain that gt⁡(Q2)=2\operatorname{gt}(Q_2)=2, gt⁡(Q3)=3\operatorname{gt}(Q_3)=3, and gt⁡(Q4)=6\operatorname{gt}(Q_4)=6.

The following theorem indicates that the geodesic transversal number and the mixed metric dimension can be arbitrarily separated in either direction over the class of connected graphs.

Theorem 3.5 Let G\mathcal{G} denote the class of all finite connected graphs with at least two vertices. Then there exist connected graphs G,HG,H such that

sup⁡G∈Ggt⁡(G)mdim⁡(G)=∞,sup⁡H∈Gmdim⁡(H)gt⁡(H)=∞.(9)\sup_{G\in\mathcal{G}} \frac{\operatorname{gt}(G)}{\operatorname{mdim}(G)} = \infty,\qquad\sup_{H\in\mathcal{G}} \frac{\operatorname{mdim}(H)}{\operatorname{gt}(H)} = \infty. \tag*{(9)}

Proof. Consider first QnQ_n for n≥3n \ge3. Then, it follows from [5 Corollary 2.8] that mdim⁡(Qn)=dim⁡(Qn)\operatorname{mdim}(Q_n)=\dim(Q_n). Thus, by [1 Sect. 2], we obtain

mdim⁡(Qn)=dim⁡(Qn)≤n.(10)\operatorname{mdim}(Q_n)=\dim(Q_n)\le n. \tag*{(10)}

Moreover, in view of Theorem 3.1, we have gt⁡(Qn)≥2nn+1\operatorname{gt}(Q_n)\ge\frac{2^n}{n+1}. This forces that

gt⁡(Qn)mdim⁡(Qn)≥2nn(n+1)⟶∞.(11)\frac{\operatorname{gt}(Q_n)}{\operatorname{mdim}(Q_n)}\ge\frac{2^n}{n(n+1)}\longrightarrow\infty. \tag*{(11)}

Next we consider K1,nK_{1,n}. By [6 Proposition 3.2], we have gt⁡(K1,n)=1\operatorname{gt}(K_{1,n})=1. Furthermore, it follows from [4 Theorem 4.3] that mdim⁡(K1,n)=n\operatorname{mdim}(K_{1,n})=n. Thus, we deduce

mdim⁡(K1,n)gt⁡(K1,n)=n⟶∞.\frac{\operatorname{mdim}(K_{1,n})}{\operatorname{gt}(K_{1,n})}=n\longrightarrow\infty.

We conclude that (9) holds, as desired. □

Now, we give a negative answer to Problem 1.1. By Theorem 3.5, we have gt⁡(Qn)>mdim⁡(Qn)\operatorname{gt}(Q_n)>\operatorname{mdim}(Q_n) for all sufficiently large nn. In fact, by Theorem 3.1 and (10), we have

mdim⁡(Qn)≤n<gt⁡(Qn),n≥4,\operatorname{mdim}(Q_n)\le n<\operatorname{gt}(Q_n),\qquad n\ge4,

as desired.

The geodesic transversal number of Hamming graphs

For convenience, in the following, let

Gk,n=H(k,n),[n]={0,1,2,…,n−1},V(Gk,n)=[n]k.G_{k,n}=H(k,n),\qquad[n]=\{0,1,2,\ldots,n-1\},\qquad V(G_{k,n})=[n]^k.

In this section, we mainly prove the following theorem:

Theorem 4.1 For integers k≥1k\ge1 and n≥2n\ge2, we have

gt⁡(Gk,n)≥nk−Ok⋅nk−21−k,(12)\operatorname{gt}(G_{k,n})\ge n^k-O_k\cdot n^{k-2^{1-k}}, \tag*{(12)}

where OkO_k is a positive constant depending only on $k.

Using Theorem 4.1, we will give a negative answer to Problem 1.2. We first prove Theorem 4.1. Let SS be a gt-set of Gk,nG_{k,n}, and write

A:=V(Gk,n)∖S.A:=V(G_{k,n})\setminus S.

Then no maximal geodesic is entirely contained in AA. A kk-dimensional binary coordinate block in Gk,nG_{k,n} is a vertex set of the form

{a1,b1}×{a2,b2}×⋯×{ak,bk}\{a_1,b_1\}\times\{a_2,b_2\}\times\cdots\times\{a_k,b_k\}

where ai,bi∈[n]a_i,b_i\in[n] and ai≠bia_i\ne b_i for every i∈{1,…,k}i\in\{1,\ldots,k\}. Clearly, such a block contains 2k2^k vertices and induces a subgraph isomorphic to the hypercube QkQ_k.

Lemma 4.2 AA contains no any kk-dimensional binary coordinate block.

Proof. Suppose, for a contradiction, that AA contains a kk-dimensional binary coordinate block, say {a1,b1}×{a2,b2}×⋯×{ak,bk}\{a_1,b_1\}\times\{a_2,b_2\}\times\cdots\times\{a_k,b_k\}, where ai,bi∈[n]a_i,b_i\in[n] and ai≠bia_i\ne b_i for every i∈{1,…,k}i\in\{1,\ldots,k\}. Then, by changing the coordinates one at a time, in any order, we can obtain a maximal geodesic of length kk from (a1,a2,…,ak)(a_1,a_2,\ldots,a_k) to (b1,b2,…,bk)(b_1,b_2,\ldots,b_k). Clearly, every vertex in this maximal geodesic belongs to AA, which contradicts the definition of AA.

Lemma 4.3 Let fk(n)f_k(n) denote the maximum cardinality of a subset in [n]k[n]^k that contains no any kk-dimensional binary coordinate block. Then, for any fixed integer k≥1k\ge1, we have

fk(n)=Ok⋅nk−21−k,(13)f_k(n)=O_k\cdot n^{k-2^{1-k}}, \tag*{(13)}

where OkO_k is a positive constant depending only on kk.

Proof. We proceed by induction on kk. If k=1k=1, then clearly, f1(n)=1f_1(n)=1, and so (13) holds whenever O1=1O_1=1, as desired.

In the following, suppose that k≥2k\ge2 and (13) holds for k−1k-1. Let AA be a subset of [n]k[n]^k that contains no any kk-dimensional binary coordinate block. For any i∈[n]i\in[n], define

Ai={x∈[n]k−1:(i,x)∈A}.A_i=\{x\in[n]^{k-1}:(i,x)\in A\}.

Furthermore, for any x∈[n]k−1x\in[n]^{k-1}, define

d(x)=∣{i∈[n]:x∈Ai}∣.d(x)=|\{i\in[n]:x\in A_i\}|.

Clearly, we have

∑x∈[n]k−1d(x)=∣A∣.(14)\sum_{x\in[n]^{k-1}}d(x)=|A|. \tag*{(14)}

For distinct i,j∈[n]i,j\in[n], we claim that Ai∩AjA_i\cap A_j contains no any binary coordinate block in [n]k−1[n]^{k-1}. In fact, if Ai∩AjA_i\cap A_j contains a (k−1)(k-1)-dimensional binary coordinate block, then we can extend it to a kk-dimensional binary coordinate block by adjoining {i,j}\{i,j\} as a new coordinate factor, which is impossible because this new kk-dimensional binary coordinate block is contained in AA. Thus, by the induction hypothesis, there exists a positive constant Ok−1O_{k-1} depending only on kk such that

∣Ai∩Aj∣≤Ok−1⋅nk−1−22−k.(15)|A_i\cap A_j|\le O_{k-1}\cdot n^{k-1-2^{2-k}}. \tag*{(15)}

Also, for every x∈[n]k−1x\in[n]^{k-1}, considering the number of all pairs of sets AiA_i and AjA_j so that x∈Ai∩Ajx\in A_i\cap A_j, we obtain

∑1≤i<j≤n∣Ai∩Aj∣=∑x∈[n]k−1(d(x)2).(16)\sum_{1\le i<j\le n}|A_i\cap A_j|=\sum_{x\in[n]^{k-1}}\binom{d(x)}{2}. \tag*{(16)}

Now by (14) and the Cauchy–Schwarz inequality, we deduce

∑x∈[n]k−1d(x)2≥(∑x∈[n]k−1d(x))2nk−1=∣A∣2nk−1.\sum_{x\in[n]^{k-1}}d(x)^2\ge\frac{\left(\sum_{x\in[n]^{k-1}}d(x)\right)^2}{n^{k-1}}=\frac{|A|^2}{n^{k-1}}.

Note that (m2)=m2−m2\binom{m}{2}=\frac{m^2-m}{2} for every positive integer mm. It follows that

∑x∈[n]k−1(d(x)2)=12(∑x∈[n]k−1d(x)2−∑x∈[n]k−1d(x))≥12(∣A∣2nk−1−∣A∣).(17)\sum_{x\in[n]^{k-1}}\binom{d(x)}{2}=\frac{1}{2}\left(\sum_{x\in[n]^{k-1}}d(x)^2-\sum_{x\in[n]^{k-1}}d(x)\right)\ge\frac{1}{2}\left(\frac{|A|^2}{n^{k-1}}-|A|\right). \tag*{(17)}

Moreover, by (15), (16), and (n2)≤n22\binom{n}{2}\le\frac{n^2}{2}, we conclude

∑x∈[n]k−1(d(x)2)≤(n2)Ok−1nk−1−21−k≤Ok−12nk+1−21−k.(18)\sum_{x\in[n]^{k-1}}\binom{d(x)}{2}\le\binom{n}{2}O_{k-1}n^{k-1-2^{1-k}}\le\frac{O_{k-1}}{2}n^{k+1-2^{1-k}}. \tag*{(18)}

Combining (17) and (18), we deduce

∣A∣2≤∣A∣nk−1+Ok−1n2k−22−k.(19)|A|^2\le|A|n^{k-1}+O_{k-1}n^{2k-2^{2-k}}. \tag*{(19)}

If ∣A∣≤2nk−1|A|\le2n^{k-1}, then ∣A∣≤2nk−21−k|A|\le2n^{k-2^{1-k}} by k≥2k\ge2, as desired. Finally, we may assume that ∣A∣>2nk−1|A|>2n^{k-1}. Then ∣A∣nk−1<∣A∣2/2|A|n^{k-1}<|A|^2/2. It follows from (19) that

∣A∣2/2≤Ok−1n2k−22−k,|A|^2/2\le O_{k-1}n^{2k-2^{2-k}},

which is equivalent to

∣A∣≤2Ok−1nk−21−k.|A|\le\sqrt{2O_{k-1}}n^{k-2^{1-k}}.

This proof is now complete.

Now, by Lemmas 4.2 and 4.3, we have ∣A∣≤Ok⋅nk−21−k|A|\le O_k\cdot n^{k-2^{1-k}}. Thus, Theorem 4.1 follows from the fact ∣S∣=nk−∣A∣|S|=n^k-|A|.

Next, we give a negative answer to Problem 1.2. We first consider gpack⁡(Gk,n)\operatorname{gpack}(G_{k,n}). It is clear that the number of vertices in every geodesic packing of Gk,nG_{k,n} must be a multiple of k+1k+1. This gives an upper bound for gpack⁡(Gk,n)\operatorname{gpack}(G_{k,n}), that is

gpack⁡(Gk,n)≤⌊nkk+1⌋≤nkk+1.(20)\operatorname{gpack}(G_{k,n})\le\left\lfloor\frac{n^k}{k+1}\right\rfloor\le\frac{n^k}{k+1}. \tag*{(20)}

Now, combining (20) and (12), we deduce

gt⁡(Gk,n)gpack⁡(Gk,n)≥nk−Ok⋅nk−21−knk/(k+1)=(k+1)(1−Ok⋅n−21−k)⟶k+1.\frac{\operatorname{gt}(G_{k,n})}{\operatorname{gpack}(G_{k,n})}\ge\frac{n^k-O_k\cdot n^{k-2^{1-k}}}{n^k/(k+1)}=(k+1)(1-O_k\cdot n^{-2^{1-k}})\longrightarrow k+1.

Thus, for a absolute constant CC, we may take positive integer kk with k+1>Ck+1>C. Then, for sufficiently large nn, we have

gt⁡(Gk,n)gpack⁡(Gk,n)>C.\frac{\operatorname{gt}(G_{k,n})}{\operatorname{gpack}(G_{k,n})}>C.

Namely, there exists a graph GG such that

sup⁡G∈Ggt⁡(G)gpack⁡(G)=∞,\sup_{G\in\mathcal{G}}\frac{\operatorname{gt}(G)}{\operatorname{gpack}(G)}=\infty,

where G\mathcal{G} denotes the class of all graphs, which gives a negative answer to Problem 1.2.

Conflict of interest

The authors state no conflict of interest.

References

  1. [1]J. Cáceres, C. Hernando, M. Mora, I. M. Pelayo, M. L. Puertas, C. Seara, D. R. Wood, On the metric dimension of Cartesian products of graphs, SIAM J. Discrete Math., 21 (2007), 423–441.DOI
  2. [2]F. Harary, R. A. Melter, On the metric dimension of a graph, Ars Combin., 2 (1976), 191–195.
  3. [3]H. Hua, Y. Chen, X. Hua, Further results on the mixed metric dimension of graphs, Discrete Appl. Math., 367 (2025), 99–106.DOI
  4. [4]A. Kelenc, D. Kuziak, A. Taranenko, I. G. Yero, Mixed metric dimension of graphs, Appl. Math. Comput. 314 (2017), 429–438.
  5. [5]A. Kelenc, A. T. M. Toshi, R. Škrekovski, I. G. Yero, On metric dimensions of hypercubes, Ars Math. Contemp., 23 (2023), #P2.08.arxiv.org/abs/2102.10916
  6. [6]P. Manuel, B. Brešar, S. Klavžar, The geodesic-transversal problem, Appl. Math. Comput., 413 (2022), 126621.arxiv.org/abs/2101.08042
  7. [7]P. Manuel, B. Brešar, S. Klavžar, Geodesic packing in graphs, Appl. Math. Comput., 459 (2023), 128277.arxiv.org/abs/2210.15325
  8. [8]I. Peterin, G. Semanišin, On maximal shortest paths cover, Mathematics, 9 (2021), 1592.DOI
  9. [9]I. Peterin, G. Semanišin, Geodesic transversal problem for join and lexicographic product of graphs, Comput. Appl. Math., 41 (2022), 128.DOI
  10. [10]P. J. Slater, Leaves of trees, Congr. Numer., 14 (1975), 549–559.
  11. [11]R. C. Tillquist, R. M. Frongillo, M. E. Lladser, Getting the lay of the land in discrete space: a survey of metric dimension and its applications, SIAM Rev., 65 (2023), 919–962.arxiv.org/abs/2104.07201

Paper details

vlnc:W_fjdqvrxz
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
CC BY 4.0
Usage

views · 0

downloads · 2

A view counts once per browser per day, a download each time the PDF is requested.

  • Mathematics

Not recorded for this paper

View statement
Looking for related papers…
Contents