ARS MATHEMATICA CONTEMPORANEA ISSN 1855-3966 (printed edn.), ISSN 1855-3974 (electronic edn.) ARS MATHEMATICA CONTEMPORANEA 17 (2019) 481-491 https://doi.org/10.26493/1855-3974.1725.2e5 (Also available at http://amc-journal.eu) Strong geodetic problem on complete multipartite graphs* * Vesna Iršič , Matjaž Konvalinka Faculty of Mathematics and Physics, University of Ljubljana, Slovenia Institute of Mathematics, Physics and Mechanics, Ljubljana, Slovenia Received 15 June 2018, accepted 18 June 2019, published online 13 November 2019 Abstract The strong geodetic problem is to find the smallest number of vertices such that by fixing one shortest path between each pair, all vertices of the graph are covered. In this paper we study the strong geodetic problem on complete bipartite graphs. Some results for complete multipartite graphs are also derived. Finally, we prove that the strong geodetic problem restricted to (general) bipartite graphs is NP-complete. Keywords: Geodetic problem, strong geodetic problem, (complete) bipartite graphs, (complete) multipartite graphs. Math. Subj. Class.: 05C12, 05C70, 68Q17 1 Introduction The strong geodetic problem was introduced in [1] as follows. Let G = (V, E) be a graph. For a set S C V, and for each pair of vertices {x, y} C S, x = y, define 7(x, y) as a selected fixed shortest path between x and y. We set I(S) = {g(x,y): x,y e S}, and V(7(S)) = Upef(S) V(7). If V(I(S)) = V for some 7(S), then the set S is called a strong geodetic set. This means that the selected fixed geodesies between vertices from S cover all vertices of the graph G. If G has just one vertex, then its vertex is considered the unique strong geodetic set. The strong geodetic problem is to find a minimum strong *The authors would like to thank Sandi Klavžar and Valentin Gledel for a number of helpful conversations and suggestions. We also thank the (anonymous) referee for a detailed reading of the paper and numerous suggested improvements. E-mail addresses: vesna.irsic@fmf.uni-lj.si (Vesna Iršic), matjaz.konvalinka@fmf.uni-lj.si (Matjaž Konvalinka) ©® This work is licensed under https://creativecommons.Org/licenses/by/4.0/ 482 Ars Math. Contemp. 17 (2019) 349-368 geodetic set of G. The size of a minimum strong geodetic set is the strong geodetic number of G and is denoted by sg(G). A strong geodetic set of size sg(G) is also called an optimal strong geodetic set. In the first paper [1], it was proved that the problem is NP-complete. The invariant has also been determined for complete Apollonian networks [1], thin grids and cylinders [14], and balanced complete bipartite graphs [12]. Some properties of the strong geodetic number of Cartesian product of graphs have been studied in [13]. Recently, a concept of strong geodetic cores has been introduced and applied to the Cartesian product graphs [9]. An edge version of the problem was defined and studied in [16]. The strong geodetic problem is just one of the problems which aim to cover all vertices of a graph with shortest paths. Another such problem is the geodetic problem, in which we determine the smallest number of vertices such that the geodesics between them cover all vertices of the graph [3, 5, 10, 11]. Note that we may use more than one geodesic between the same pair of vertices. Thus this problem seems less complex than the strong geodetic problem. The geodetic problem is known to be NP-complete on general graphs [2], on chordal and bipartite weakly chordal graphs [6], on co-bipartite graphs [7], and on graphs with maximal degree 3 [4]. However, it is polynomial on co-graphs and split graphs [6], on proper interval graphs [8], on block-cactus graphs and monopolar chordal graphs [7]. Moreover, the geodetic number of complete bipartite (and multipartite) graphs is straightforward to determine, i.e. sg(Kn,m) = min{n, m, 4} [11]. Recall from [12] that the strong geodetic problem on a complete bipartite graph can be presented as a (non-linear) optimization problem as follows. Let (X, Y) be the bipartition of Kn,m and SUT, S C X, T C Y, its strong geodetic set. Let |S| = s and |T| = t. Thus, sg(Kn,n) < s + t. With geodesics between vertices from S we wish to cover vertices in Y - T. Vice versa, with geodesics between vertices from T we are covering vertices in X - S. The optimization problem for sg(Kn,m) reads as follows: This holds due to the fact that every geodesic in a complete bipartite graph is either of length 0, 1 (an edge), or 2 (a path with both endvertices in the same part of the bipartition). If a strong geodetic set S has k vertices in one part of the bipartition, then geodesics between those vertices can cover at most (2) vertices in the other part. The exact value is known for balanced complete bipartite graphs: if n > 6, then min s +t subject to: 0 < s < n 0 < t < m (1.1) s, t G Z. 8n - 7 is not a perfect square, 8n - 7 is a perfect square. See [12, Theorem 2.1]. V. Irsic and M. Konvalinka: Strong geodetic problem on complete multipartite graphs 483 In the following section, we generalize the above result to all complete bipartite graphs. To conclude the introduction, we state the following interesting and surprisingly important fact. Lemma 1.1 (Shifting Lemma). Let Kni..,nr be a complete multipartite graph with the multipartition Xi,..., Xr, |Xj| = nj for i G [r]. Let S = Si U • • • U Sr be an optimal strong geodetic set, with Si C Xj and |Sj| = sj for i G [r]. If si < s2, s3 and s2 < n2, s3 < n3, then there exist x G Si and y G S2 U S3, such that S U {y} — {x} is also an optimal strong geodetic set. Proof. Let G = Kn1}...,nr, |Xj| = nj, |Sj| = sj for i G [r]. Suppose Sj = 0,Xj for i G {1, 2, 3}. Without loss of generality, si = min{si, s2, s3}, and let geodesics between vertices of Si cover fewer vertices in X2 — S2 than in X3 — S3. Select vertices x G Si and y G X2 — S2. Geodesics between vertices from Si can be fixed in such a way that no vertex in X2 is covered with a geodesic containing x. This is trivial for si G {1, 2,3}, and follows from m 2 < (si-i) for si > 4. Now consider T = S U {y} — {x}, T| = |S|. We will prove that T is a strong geodetic set of G. Fix geodesics between vertices in T in the same way as in S, except those containing x or y. As x G T, at most si — 1 vertices U in V(G) — Xi — X2 are uncovered. But geodesics containing y can cover the vertex x, as well as s2 — 1 other vertices in V(G) — X2. As we have s2 — 1 > si — 1, those geodesics can be fixed in such a way that U is covered. □ Proposition 1.2. For every complete multipartite graph there exist an optimal strong geodetic set such that its intersection with all but two parts of the multipartition is either empty or the whole part. Proof. Let G = Kni..,nr, |Xj| = nj, be a multipartite graph. The Shifting Lemma states that every strong geodetic set with three or more parts of size not equal to 0 or nj can be transformed into a strong geodetic set of the same size, where one of these parts becomes smaller and one larger. After repeating this procedure on other such triples, at most two parts can have size different from 0 or nj. □ The rest of the paper is organized as follows. In the next section, some further results about the strong geodetic number of complete bipartite graphs are obtained. In Section 3 we discuss the strong geodetic problem on complete multipartite graphs. Finally, in Section 4 the complexity of the strong geodetic problem on multipartite and complete multipartite graphs is discussed. 2 On complete bipartite graphs In this section, we give a complete description of the strong geodetic number of a complete bipartite graph. Instead of giving an explicit formula for sg(Kn m), we classify the triples (n, m, k) for which sg(Kn,m) = k. Define f ( O) 1 + /max{^ — 1, 2^ f (a,O ) = a — 1+1 2 484 Ars Math. Contemp. 17 (2019) 349-368 Theorem 2.1. For positive integers n, m and k, (n,m) 3 and max{n,m} > 3. The statement follows from the following (note that the sum s1 + s2 equals k for every (s1, s2) that appears below). Note that all different optimal solutions are described here, hence some of the conditions overlap. 1. If n < 3 and m = f (k, n) = k, or m = f (k, i — 1) and f (k, k — i — 1) < n < f (k, k — i) for i < 4, or m = f (k, i — 1) and n = f (k, k — i — 1) for i < 4, then (0, k) is an optimal solution. Symmetrically, if m < 3 and n = f (k, m) = k, or f (k, i — 1) < m < f (k, i) and n = f (k, k — i — 1) for i > k — 4, then (k, 0) is an optimal solution. V. Irsic and M. Konvalinka: Strong geodetic problem on complete multipartite graphs 485 Figure 1: All pairs (n, m) for which sg(Kn,m) = 12. 2. If 3 < n < k and m = f (k, n), then (n, k—n) is an optimal solution. Symmetrically, if 3 < m < k and n = f (k, m), then (k — m, m) is an optimal solution. 3. If f (k, i — 1) < m < f (k, i) and f (k, k — i — 1) < n < f (k, k — i) for 4 < i < k — 4, or m = f (k, i — 1) and f (k, k — i — 1) < n < f (k, k — i) for i > 3, or f (k, i — 1) < m < f (k, i) and n = f (k, k — i — 1) for i < k — 3, or m = f (k, i — 1) and n = f (k, k — i — 1) for 3 < i < k — 3, then (i, k — i) is an optimal solution. 4. If f (k, i — 1) < m < f (k, i) and n = f (k, k — i — 1) for i < k — 4, or m = f (k, i — 1) and n = f (k, k — i — 1) for 2 < i < k — 4, then (i + 1, k — i — 1) is an optimal solution. 5. If m = f (k, i — 1) and f (k, k — i — 1) < n < f (k, k — i) for i > 4, or m = f (k, i — 1) and n = f (k, k — i — 1) for 4 < i < k — 2, then (i — 1, k — i + 1) is an optimal solution. It is easy to see that the above solutions give rise to the strong geodetic sets of size k. For example, in the first case, the part of the bipartition of size m is a strong geodetic set with parameters (0, k). What remains to be proved is sg(Kn,m) > k for each case. This can be shown by a simple case analysis. As the reasoning is similar in all cases, we demonstrate only two of them. Let X be the part of the bipartition of size n and Y the part of size m. Also, let S = Si U S2, where Sx Ç X, S2 Ç Y, be some strong geodetic set. • The case k>n > 3 and m = k — 1 + (n22i) = k — n + Q): If Si = X, then geodesics between these vertices cover at most 2 vertices in Y, so at least k — n vertices in Y must also lie in a strong geodetic set. Hence, |S| > n — (k — n) = k. If Si = X, geodesics between these vertices cover at most (n2"i) vertices in Y, so at least k — 1 vertices from Y must lie in a strong geodetic set. Hence, |S| > |Si| + (k — 1). If Si = 0 or |S21 > k, we have |S| > k. Otherwise, S = S2 and contains exactly k — 1 vertices. But then the remaining vertices in Y are not covered. • The case where f (k, i — 1) < m < f (k, i) and f (k, k — i — 1) < n < f (k, k — i) 486 Ars Math. Contemp. 17 (2019) 349-368 for 4 < i < k — 4: We can write fk - i - 2\ n = k — 1+i j + l, l € {1, ...,k — i — 2}, m = k — 1+ ^ — ^ + j, j €{1,...,i — 2}. Suppose |S| < k — 1. If |S1| < i — 2, these vertices cover at most (i-2) vertices in X, thus at least k vertices remain uncovered and |S | > k. Hence, |S1| > i — 1. Similarly, |S2| > k — i — 1. If |S1| = i — 1, then (i-1) vertices in Y are covered. As k + j — i + 1 are left uncovered, it holds that |S2| > k — i + 2 and thus |S| > k +1. If |S2| = k — i — 1, then (fc-2-1) vertices in X are covered. As l + i + 1 are left uncovered, it holds that |S1| > i + 2 and thus |S | > k + 1. Hence |S11 > i and S | > k — i and thus |S| > k. □ The first condition from Theorem 2.1 can be simplified as follows. Corollary 2.3. If n > 3 and m > ("), then sg(K„jm) = m +1 — (n-1). f n < 3 and m > n, then sg(Kn,m) = m. When m < , Theorem 2.1 is harder to apply. Note, however, that the theorem suggests that m is approximately equal to k — 1 + , and n is approximately equal to k — 1 + (fc-2-1). Furthermore, note that we can rewrite the system of equations (with known m,n and variables k, i) m = k —1+(i"21), n = k — 1+ fc-2-1) as a polynomial equation of degree 4 for k (say by subtracting the two equations, solving for i, and plugging the result into one of the equations), and solve it explicitly. It seems that one of the four solutions is always very close to sg(Km,n). Denote the minimal distance between sg(Km,n) and a solution k of m = k — 1 + (i-1), n = k — 1 + (fc-2-1) by e(m, n). Then our data is indicated in Table 2. Table 2: The difference between the exact and estimated values of sg(Km,n) for different values of n. n 10 100 1000 10000 100000 max{e(m,n) : n < m < } 1.094 1.774 1.941 1.983 1.995 We conjecture the following. Conjecture 2.4. If n < m < , then e(m,n) < 2. If the conjecture is true, sg(Km,n) is among the (at most 16) positive integers that are at distance < 2 from one of the four solutions of the system m = k - 1 + (i-1), n = k - 1 + (fc-2-1). For each of these (at most) 16 candidates, there are at most three (consecutive) i's for which f (k, i -1) < m < f (k, i), found easily by solving the quadratic equation m = k — 1 + (i-1). For each such i, check if f (k, k — i — 1) < n < f (k, k — i). This allows for computation of sg(Km,n ) with a constant number of operations. V. Irsic and M. Konvalinka: Strong geodetic problem on complete multipartite graphs 487 3 On complete multipartite graphs The optimization problem (1.1) can be generalized to complete multipartite graphs. However, solving such a program seems rather difficult. Hence, we present an approximate program which gives a nice lower bound for the strong geodetic number of a complete multipartite graph. If i vertices from one part are in a strong geodetic set, geodesics between them cover at most (2) other vertices. In the following, we do not take into account the condition that they can only cover vertices in other parts, and that the number of selected vertices must be an integer. Recall the notation (1mi,..., kmk} which describes a partition with m2 parts of size i, 1 < i < k. Let G be a complete multipartite graph corresponding to the partition n = (1mi,..., kmk} and let a2j denote the number of parts of size j with exactly i vertices in the strong geodetic set. Thus we must have J]j =0 aij — mj and XjLiXjLo (2)aij > Ej^Ej^Ci - i)a2j. The second condition simplifies to Ejk=i Ej=i C+1)aij > Ejk=i Ej=o jaij = Ejk=i jmj = n. As aoj's do not appearin it anymore, we also simplify the first condition to J2j=i a2j < mj and get k j " "ij min ^^ ¿a. j=1i=1 j subject to: ^^ aj < mj i=1 (3.1) ib b C +1) aij >n j=i ¿=^2 / 0 < ajj < mj. As the sequence (2) - k is increasing for k > 3, it is better to select more vertices in a bigger part. Hence, the optimal solution is ak,k = mk ak-1,k- 1 = mk-1 ai+1,i+1 = mi+1 ai,i = Imi +-----+ 1m1 - (2)mk - • • • - C+1)mi+1 C+1) where l is the smallest positive integer such that (++) mk + ••• + (+2 ) ml+i < kmk + + 1m1 = |V (K^m, + (i121)mi+1,and ,kmk > |, which is equivalent to Zmi + • • • + 1m1 > (2)mk + sg(K( 1mi, ,kmfc >) > kmk +----+ (Z + 1)mi+1 + Zmi +-----+ m1 - (2) mk----- ('+1) mi+1 i+1 2 488 Ars Math. Contemp. 17 (2019) 349-368 The result is particularly interesting in the case when n = (km), i.e. when we observe a multipartite graph with m parts of size k, as we get l = k and Sg(K(fcm) ) > 2km k + 1 On the other hand, considering a strong geodetic set consisting only of the whole parts of the bipartition yields an upper bound. At least l G Z, where 1(k + (2) ) > mk, parts must be in a strong geodetic set. Hence, 2m k + 1 k. sg(K( k m)) < This implies the following result. Proposition 3.1. If k, n G N and (k + 1) | 2m, then sg(K