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 be a graph. We always use and to denote the vertex set and edge set of , respectively. Given two vertices and in , the distance between and is denoted by , or simply by when no confusion can arise. For two distinct vertices , we say a vertex distinguishes and whenever . A subset is called a metric generator of if for every pair of distinct vertices , there exists a vertex in such that it distinguishes and . A metric generator of with minimum cardinality is called a metric basis of , and the cardinality of a metric basis is referred to as the metric dimension of . 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 and an edge , the distance between and is defined by . Let . We say a vertex of distinguishes two distinct elements (vertices or edges) if . For a subset of , we say is a mixed metric generator of provided that, for every pair of distinct elements , there exists a vertex in such that it distinguishes and . The cardinality of a mixed metric generator with minimum size, denoted by , is called the mixed metric dimension of . 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 . A geodesic is a shortest path between a pair of vertices in a graph. In particular, if is a shortest path from to , then is called a geodesic. A geodesic in a graph is said to be maximal if there exists no other geodesic in , which contains as a sub-path. A subset of is a geodesic transversal of provided that any maximal geodesic in contains at least one vertex in . The geodesic transversal number of , denoted by , is the minimum cardinality of a geodesic transversal of . 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 is called a gt-set of if is a geodesic transversal of such that . The geodesic-transversal problem is NP-complete [6]. A geodesic packing of is a set of vertex-disjoint maximal geodesics. The maximum cardinality of a geodesic packing of is called the geodesic packing number of , and is denoted by . 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 holds for any tree, unicyclic graph, and block graph. Thus, they posed the following problem.
Problem 1.1 ([3 Problem 5.1]) Does hold for every connected graph ?
In [7], it was proved that for any graph , and the upper bound is sharp. Moreover, can be arbitrarily bigger than ; see, for example, and . Clearly, in (), any maximal geodesic has length . Thus, and . As a result, is less than or equal to an absolute constant. For any graph , the following problem was posed.
Problem 1.2 [7 Problem 2.5] Is there an absolute constant such that , for all graphs ?
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 -dimensional hypercube has vertex set
Namely, every vertex of is an -tuple whose coordinate is either 0 or 1. Two vertices in are adjacent if and only if they differ in exactly one coordinate. Let . The complement of is denoted by , that is
Moreover, we write , that is, denotes the number of 1-entries in the vector . For two vertices of , let denote their bitwise addition modulo 2. For example, if and , then . For any and , define
It is easy to see that .
By the basic properties of , the following is valid.
Remark 2.1 A path of is a maximal geodesic if and only if , and each coordinate changes exactly once along . More precisely, let , and let be a permutation of . Define
where is the -th standard unit vector. We have that
is a maximal geodesic of .
For and , Hamming graph is the graph with vertex set
in which two vertices are adjacent if and only if they differ in exactly one coordinate. In general, we denote by . Thus, has vertices and is -regular. The distance between two vertices equals the number of coordinates in which they differ. Consequently, has diameter . Moreover, every maximal geodesic of has length and contains vertices. In particular, is the -dimensional hypercube .
The following result will be used in the proof of the subsequent theorems.
Lemma 2.2 Let be finite sets, and let . For any , let , and let be the number of maximal intervals of consecutive integers in . Then
In particular, we have
Proof. For any , we have . Set . Clearly, , and
Now, consider the sum . For fixed , its contribution to this sum equals the number of indices such that both and belong to . Since consists of maximal intervals of consecutive integers and contains integers in total, the number of such adjacent pairs is . Indeed, an interval containing integers contributes exactly adjacent pairs. Summing over all intervals gives . As a result, we have that
It follows that
as desired.
The geodesic transversal number of hypercubes
The main result of this section is the following theorem:
Theorem 3.1 For any , we have
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 , we have that .
Proof. Let
Then . It suffices to prove that is a geodesic transversal. Now let
be a maximal geodesic of . Thus, by Remark 2.1, we see that . Set . Then . Now without loss of generality, assume that . Then
Note that, by Remark 2.1, each coordinate changes exactly once along . It follows that
As a result, there exists at least one index in such that . It follows that , and so is a geodesic transversal, as desired.
Lemma 3.3 For any , we have that .
Proof. Suppose that is a gt-set of . Let . In the following, we consider two cases for .
Case 1. , where .
Set
where is the -th standard unit vector. For any , let
Then by Remark 2.1, we see that
is a maximal geodesic. If for each , and for each , then by (3), we can choose a maximal geodesic from to such that every vertex in this maximal geodesic does not belong to , which contradicts the definition of . We conclude that
or
For any , write
Note that . Thus, (4) is equivalent to
Furthermore, since for each , we deduce that (5) is equivalent to
Now, in either (4) or (5), it follows that
and hence, we have
In view of Lemma 2.2, we deduce that , which implies that . In other words, we obtain
Case 2. , where .
Assume first (1) and (2). Then, according to Remark 2.1, we infer that
is a maximal geodesic. Let
Then, similar to the proof of Case 1, we conclude that
Combining (7) and Lemma 2.2, we obtain
As a result,
Finally, combining (6) and (8), we have , as desired.
Now, Theorem 3.1 follows from Lemmas 3.2 and 3.3.
Remark 3.4 It is straightforward to verify that and . Thus, both the upper and lower bounds in Theorem 3.1 are sharp. In fact, by Theorem 3.1, we also can obtain that , , and .
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 denote the class of all finite connected graphs with at least two vertices. Then there exist connected graphs such that
Proof. Consider first for . Then, it follows from [5 Corollary 2.8] that . Thus, by [1 Sect. 2], we obtain
Moreover, in view of Theorem 3.1, we have . This forces that
Next we consider . By [6 Proposition 3.2], we have . Furthermore, it follows from [4 Theorem 4.3] that . Thus, we deduce
We conclude that (9) holds, as desired. □
Now, we give a negative answer to Problem 1.1. By Theorem 3.5, we have for all sufficiently large . In fact, by Theorem 3.1 and (10), we have
as desired.
The geodesic transversal number of Hamming graphs
For convenience, in the following, let
In this section, we mainly prove the following theorem:
Theorem 4.1 For integers and , we have
where 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 be a gt-set of , and write
Then no maximal geodesic is entirely contained in . A -dimensional binary coordinate block in is a vertex set of the form
where and for every . Clearly, such a block contains vertices and induces a subgraph isomorphic to the hypercube .
Lemma 4.2 contains no any -dimensional binary coordinate block.
Proof. Suppose, for a contradiction, that contains a -dimensional binary coordinate block, say , where and for every . Then, by changing the coordinates one at a time, in any order, we can obtain a maximal geodesic of length from to . Clearly, every vertex in this maximal geodesic belongs to , which contradicts the definition of .
Lemma 4.3 Let denote the maximum cardinality of a subset in that contains no any -dimensional binary coordinate block. Then, for any fixed integer , we have
where is a positive constant depending only on .
Proof. We proceed by induction on . If , then clearly, , and so (13) holds whenever , as desired.
In the following, suppose that and (13) holds for . Let be a subset of that contains no any -dimensional binary coordinate block. For any , define
Furthermore, for any , define
Clearly, we have
For distinct , we claim that contains no any binary coordinate block in . In fact, if contains a -dimensional binary coordinate block, then we can extend it to a -dimensional binary coordinate block by adjoining as a new coordinate factor, which is impossible because this new -dimensional binary coordinate block is contained in . Thus, by the induction hypothesis, there exists a positive constant depending only on such that
Also, for every , considering the number of all pairs of sets and so that , we obtain
Now by (14) and the Cauchy–Schwarz inequality, we deduce
Note that for every positive integer . It follows that
Moreover, by (15), (16), and , we conclude
Combining (17) and (18), we deduce
If , then by , as desired. Finally, we may assume that . Then . It follows from (19) that
which is equivalent to
This proof is now complete.
Now, by Lemmas 4.2 and 4.3, we have . Thus, Theorem 4.1 follows from the fact .
Next, we give a negative answer to Problem 1.2. We first consider . It is clear that the number of vertices in every geodesic packing of must be a multiple of . This gives an upper bound for , that is
Now, combining (20) and (12), we deduce
Thus, for a absolute constant , we may take positive integer with . Then, for sufficiently large , we have
Namely, there exists a graph such that
where 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]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]F. Harary, R. A. Melter, On the metric dimension of a graph, Ars Combin., 2 (1976), 191–195.
- [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]A. Kelenc, D. Kuziak, A. Taranenko, I. G. Yero, Mixed metric dimension of graphs, Appl. Math. Comput. 314 (2017), 429–438.
- [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]P. Manuel, B. Brešar, S. Klavžar, The geodesic-transversal problem, Appl. Math. Comput., 413 (2022), 126621.arxiv.org/abs/2101.08042
- [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]I. Peterin, G. Semanišin, On maximal shortest paths cover, Mathematics, 9 (2021), 1592.DOI
- [9]I. Peterin, G. Semanišin, Geodesic transversal problem for join and lexicographic product of graphs, Comput. Appl. Math., 41 (2022), 128.DOI
- [10]P. J. Slater, Leaves of trees, Congr. Numer., 14 (1975), 549–559.
- [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