IMFM Institute of Mathematics, Physics and Mechanics Jadranska 19, 1000 Ljubljana, Slovenia Preprint series Vol. 50 (2012), 1179 ISSN 2232-2094 SOME STEINER CONCEPTS ON LEXICOGRAPHIC PRODUCTS OF GRAPHS Bijo S. Anand Manoj Changat Iztok Peterin Prasanth G. Narasimha-Shenoi Ljubljana, July 3, 2012 Some Steiner Concepts on Lexicographic Products of Graphs* Bijo S Anand Department of Futures Studies, University of Kerala Trivandrum-695034, India bijos_anand@yahoo.com Manoj Changat Department of Futures Studies, University of Kerala Trivandrum-695034, India mchangat@gmail.com i CM 00 o Iztok Peterin^ University of Maribor, FEECS Smetanova 17, 2000 Maribor, Slovenia iztok.peterin@uni-mb.si Prasanth G. Narasimha-Shenoi* Department of Mathematics, Government College, Chittur, Palakkad-678 104, India prasanthgns@gmail.com Abstract The smallest tree that contains all vertices of a subset W of V(G) is called a Steiner tree. The number of edges of such a tree is the Steiner distance of W and union of all Steiner trees of W form a Steiner interval. Both of them are described for the lexicographic product in the present work. We also give a complete answer for the following invariants with respect to the Steiner convexity: the Steiner number, the rank, the hull number, and the Caratheodory number, and a partial answer for the Radon number. At the end we locate and repair a small mistake from [7]. 0* Work supported by the Ministry of Science of Slovenia and by the Ministry of Science and Technology of India under the bilateral India-Slovenia grants BI-IN/10-12-001 and INT/SLOVENIA-P-17/2009, respectively. ^Supported by the Ministry of Science of Slovenia under the grant P1-0297. The author is also with IMFM, Jadranska 19, 1000 Ljubljana, Slovenia. ^Supported by the University Grants Commission, Govt. of India under the grant MRP(S)-864/10-11/KLCA042/UGC-SWRO. CM 00 00 o» o CM Key words: Lexicographic product; Steiner convexity; Steiner set; Steiner distance 2010 Math. Subj. Class.: 05C05, 05C76 3 1 Introduction and preliminaries Let W be a subset of a set of vertices V(G) of a graph G. A Steiner tree of W is a minimum connected subgraph (if it exists) of G that contains all vertices of W. Clearly Steiner tree is a tree. If W has exactly two vertices u and v, then its Steiner tree is a shortest u, v-path or a u, v-geodesic. Hence Steiner trees are natural generalization of geodesics. Similarly we have following generalizations. The number of edges on an u, v-geodesic is the usual (geodetic) distance dG(u, v) between u and v in G. The number of edges on a Steiner tree for W is the Steiner distance dG(W) of W in G. The geodesic interval IG(u, v) contains all vertices lying on an u, v-geodesic of G. The Steiner interval S/G(W) contains all vertices of a Steiner tree of W. A subset C of V(G) is geodesically convex if IG(u, v) is a subset of C for every pair u and v from C. Similarly C is Steiner convex if SIG(W) is a subset of C for every W C C. It is easy to see that if C induce a complete graph or if C = V(G), then C is a convex set for both geodesic and Steiner convexity. Such sets are called 00 trivial (geodesic or Steiner) convex sets. For W C V(G), let Ig[W] be an union of intervals IG(u, v) for every pair u, v G W, this is IG[W] = Uu,veWIG(u, v). A set W of vertices of G is called a geodetic set if IG(W) = V(G). A geodetic set of minimum cardinality is a minimum geodetic set and its cardinality is the geodetic number g(G) of G. If SIg(W) = V(G), then we call W a Steiner set of G. A S Steiner set of minimum cardinality is a minimum Steiner set and its cardinality is the Steiner number s(G) of G. In an analogue fashion we can define the above concepts for the other convexities induced by different type of paths like induced path, detour path, any path, and the others; see [11]. The Steiner tree problem is a well-known problem with several applications. Its origin is in Euclidean (or other metric) space. In combinatorics Steiner trees play an important role in combinatorial optimization and application to combinatorial designs and transportation, to name just a few. For instance, see [2, 21] for some development in approximation algorithms. In general, the problem of finding a Steiner distance is NP-hard problem, see [17]. The beginning of graph theoretical approach to Steiner distance was probably made by Chartrand et. al. in [13]. Since then many papers appeared on the topic. For a small collection see [1, 4, 9, 13, 14, 20, 21, 22, 25] and the references therein. In particular, note that Steiner number was introduced by Chartrand and Zhang in [14]. In the second section we completely describe the Steiner distance, Steiner intervals, and the Steiner number with respect a to lexicographic product of graphs. In [4, 9] authors worked on a variation of Steiner problems on multi sets (instead of sets). Both definitions coincide for Steiner convexity, since we take all subsets of cm 00 00 C in the definition of a Steiner convex set C and not only k-subsets of C. (The latest is known as the k-Steiner convexity.) Not much is known about Steiner convexity. The pioneer work was done in [19] and continued in [5] on the so-called local Steiner convexity. For the general Steiner convexity, the non-trivial (geodesic and Steiner) convex sets of lexicographic product of graphs are characterized in [1]. We will use this result in the third section to describe some of the well-known convex invariants on lexicographic product graphs with respect to the Steiner convexity. The study of convexity invariants like the Caratheodory, the Helly, the Radon, the Hull numbers, and rank is one of the classical problems in combinatorial convexity. For the geodesic convexity an interesting observation due to Duchet in [16] states that these convexity invariants can be arbitrary in the sense that given any positive integers c, h, and r, there exists a finite graph whose geodesic convexity has Caratheodory, Helly, and Radon numbers c, h, and r, respectively. This result motivates to study these invariants for other graph convexities, see [3, 11, 12, 15], in particular in our case in third section the Steiner convexity. In the last section we briefly discuss a small mistake from [7] and correct it, while in the remaining of this section we define the convexity invariants and introduce some notations. Let A be a subset of V(G) for some graph G. The geodesic convex hull ch(A) of A is the smallest geodesic convex set that contains A, while the Steiner convex hull sch(A) of A is the smallest Steiner convex set that contains A. We will use sch(A) in the following definitions, since we are mainly interested in the Steiner convexity. The Steiner Caratheodory number of a graph G is the smallest integer c(G) (if it CO exists) such that for any finite subset A of V(G), sch(A) equals to U{sch(S) : S C CO A, |S| < c(G)}. The Radon number of G is the smallest integer r(G) (if it exists) such that every r(G)-element set S C V(G) admits a Radon partition Si and S2, that is S = Si U S2, Si n S2 = 0, and sch(Si) n sch(S2) = 0. A subset A of V(G) is Steiner convexly independent if a sch(A — {a}) for every a e A. Cardinality of a maximum convexly independent set is known as Steiner rank, srank(G) for short. A subset A of V(G) is called a Steiner hull set of G if sch(A) = V(G), and a Steiner hull set of G of the minimum cardinality is a minimum Steiner hull set in G. The cardinality of a minimum Steiner hull set in G is called the Steiner hull number sh(G) of G. All these concepts are direct generalizations from the geodesic convexity. However they can be defined on general convexities. For more about this topic see the book [24]. We will use for a graph G the standard notations NG(g) for the open neighborhood, {9' : 99' e E(G)} and w(G) for the order of a maximum complete subgraph. A simplicial vertex is a vertex 9 whose NG(g) induce a complete graph. By A(G) we denote the number of all simplicial vertices of G. If a vertex is not simplicial it is called a A-vertex. For a subset A of V(G), we denote by (A) the subgraph of G induced by A. The lexicographic product of graphs G and H is the graph G o H (also denoted by o a» cm 00 cm cm 00 00 G[H]) with the vertex set V(G) x V(H). Vertices (gi, hi) and (g2, h2) are adjacent if either g1g2 G E(G) or g1 = g2 and h1h2 G E(H). The lexicographic product create a constant interest in the research community over the years. The intersection from past decade with other topics in this work can be found in [1, 6, 8, 23]. A product is called non-trivial if both factors are graphs on at least two vertices. It is easy to see that G o H is connected if and only if G is connected. For h G V(H) call Gh = {(g, h) G G o H : g G V(G)} a G-layer in G o H and for g G V(g) call 9H = {(g, h) G G o H : h G V(H)} an H-layer in G o H. Note that |W|; W C 9H and dn(pn(W)) = |W| - 1. m Proof. If dn(pn(W)) = |W| — 1, then vertices of pn(W) induce a tree in H. If in addition W C 9H, then vertices of W induce a tree in (9H) and the proof is by nothing in this case. Assume next that W C 9H and dn(pn(W)) > |W|. Hence W does not induce a connected subgraph of G o H and dGoH(W) > | W|. On the other hand, dGoH(W) < |W|, since W U {(g', h)} induce a connected subgraph of G o H for every neighbor g' of g and any h G V (H). Let now W ^ 9H for every g G V(G). Without loss of generality we may assume that there are only p number of H-layers 9iH, i G {1,...,p}, for which W n V(9iH) = 0. Let (gi,hi)G Wn 9iH for i G {1,... ,p}. By Lemma 1, a Steiner tree of g1,... ,gp (in G) and a Steiner tree of (g1, h1),..., (gp, hp) (in GoH) have the 00 00 same size. Let T be a Steiner tree of (gi, h1),..., (gp, hp) (in GoH). Since W ^ gH, every vertex of (gi, h^), for i G {1,... ,p}, has a neighbor (gi, hi) on T that is not in H. The remaining vertices of W in each layer H, i G {1,... , p}, are also adjacent to (gi, hi) (by the definition of the lexicographic product). Let T be a tree obtained from T by adding all remaining vertices of W and for every such vertex exactly one additionaUdge to a (gi, hi) G V(T). Clearly T has dG(pG(W)) + |W| - |pg(W)| edges. If T is not a Steiner tree of W, then there exists T' which is a Steiner tree of W with less edges than T. The projection pG(T') is a tree containing pG (W) with less edges than pG(T). Since pG(T) and pG(T) have the same number of edges, we have a contradiction with the fact that pG(T) is a Steiner tree of pG(W). □ In the above theorem plays no role whether H is connected or not. However we o I 00 do not need the condition for G to be connected. If G is not connected the formula stays the same whenever all vertices of pG(W) are in the same component of G, while otherwise the Steiner distance does not exists. The same holds also for the next result. Theorem 3 Let G and H be two non-trivial graphs and let G be connected. For a subset W of V(G o H), SIGoH(W) is equal to W U ((SI(Pg(W) - Pg(W)) x V(H)) W U (NG(g) x V(H)) ({g} x SIh(ph(W))) U (NG(g) x V(H)) W W ^ gH for every g G G; W C gH and (ph(W)) > |W|; W C gH and dH(ph(W)) = |W|; W C gH and dH(ph(W)) = |W| - 1. Proof. If W C gH and dH(W) = |W| - 1, then W induce a tree in G o H and hence W itself is the Steiner interval. If W C gH and (pH(W)) > |W|, then W U |(g',h)} induce a tree for every g' G (g) and any h G V(H). Clearly this tree is a Steiner tree and hence NG (g) x V(H) C SIGoH (W). If in addition (pH(W)) = |W|, then there are also some Steiner trees completely contained in (gH}. Since (gH) is isomorphic to H, we also have {g} x (pH(W)) C SIGoH(W). Suppose that there exists an additional vertex (g',h) in SIGoH(W), where (g', h) G ({g}x SIh(Ph(W))) U(Ng(g) x V(H)). Either dG(g,g') > 2 or g' = g. If dG(g,g') > 2, this tree contains more than |W| edges. If g' = g, then h G (pH(W)). The tree that contains W and (g,h) has more than |W| edges and is not a Steiner tree for W. Let now dH(W) > |W|. If there exists a vertex (g',h) in SIGoH(W), where (g', h) G WU(NG(g) x V(H)), then again either dG(g,g') > 2 or g' = g. If dG(g,g') > 2, we have the same contradiction. If g' = g, then h G pH(W). Since dH(W) > |W|, there exists no vertex (g, h) in gH such that W U {(g, h)} induce a tree in G o H. Hence (g,h) is not in SIGoH(W). Let W ^ gH for every g G V(G). From the description of Steiner trees in the proof of Theorem 2, we can easily see the following. If g G pG(W), then gH n CM 00 00 SIgoh(W) contains only vertices of W. Otherwise, if g pG(W) and g is on some Steiner tree for pg(W) in G, then there exists a Steiner tree for W in G o H that contains (g, h) for every h e V(H). Hence [W U (SI(Pg(W) - Pg(W)) x V(H))] C SIgoh(W). If there would be an additional vertex in SIgoh(W), we would get the same contradiction as at the end of the proof of Theorem 2. □ The Steiner number of GoH mainly depends on the number of vertices of H which can be seen in the next theorem. But there is an exception. Let H be a connected graph. If a subset W of V(H) induce a connected graph, then SIH (W) = W. Hence every Steiner set S of H, that is a proper subset of V(H), does not induce a connected subgraph of H. Next we investigate those Steiner sets S for which dH(S) = |S|, called perfect Steiner sets. In other words, a Steiner set S is a perfect Steiner set if S U {v} induce a tree in H for every v e V(H) — S. There is no perfect Steiner set in a complete graph, since any proper subset of V(Kn) induce a connected subgraph. So let H be a connected non-complete graph and v a vertex of minimum degree that is not a cut vertex. We claim that S = V(H) — NH (v) is a perfect Steiner set. Indeed, S does not induce a connected subgraph of H and d(S) > |S|. On the other hand (S U {u}) is connected for every u e NH(v), since v is CM not a cut vertex. Hence dH(S) = |S| and SIh(S) = V(H) and every non-complete connected graph admits a perfect Steiner set. However this is not necessarily a minimum perfect Steiner set. As an example observe a cube Q3 and let vertices of S induce two edges at distance 2. It is easy to see that this is a perfect Steiner set of cardinality 4, while the above description gives a perfect Steiner set of cardinality 5. Now we can describe the Steiner number of any nontrivial lexicographic product. Ö r O» O CM CM CO Theorem 4 Let G and H be two non-trivial graphs and let G be connected. If A = min{| W| : W is a perfect Steiner set in H}, then s(G o H) is equal to A |V (H )| .s(G)|V (H )| if G has a universal vertex and H is connected and not complete; if G has a universal vertex and H is not connected; otherwise. Proof. Suppose first that G has a universal vertex g. If H is connected and not complete, then there exists a perfect Steiner set of H and a perfect Steiner set of minimum cardinality. Let W be such a set, that is A = |W|. Clearly S = {g} x W CD is a subset of gH and dGoH(S) = |S| = A. By Theorem 3, we have SIgoH(S) = ({g} x SIh(ph(W))) U (NG(g) x V(H)) = = ({g} x V(H)) U ((V(G) - {g}) x V(H)) = = V(G) x V(H) = V(G o H) CD and S is a Steiner set. Moreover, since S does not induce a connected subgraph, we have s(G o H) = |S| = A. o ö I CM 00 CM CM Suppose now that H is not connected. For S = gH we have (S)) = to > |S|. By Theorem 3, we have SIcoH(S) = S U (Nc(g) x V(H)) = = ({g} x V(H)) U ((V(G) - {g}) x V(H)) = = V(G) x V(H) = V(G o H) and S is a Steiner set in this case. Let S' be a smaller subset of V(G o H) than S. For every g' e V(G) there exists an h e V(H), such that (g',h) e S'. Choose g' € pc(S'). We claim that gH £ SI(S'). Indeed, if S' C gH, then by Theorem 3, (second and third possibility) and since H is not connected, g H is not entirely in SI(S'). So let S' £ g H for every g' € G. By Theorem 3, (first option) again g H is not in SI(S'). Hence S' is not a Steiner set and s(G o H) = |V(H)|. Next let H be a complete graph. If S' is a minimum Steiner set of G, then S' x V(H) clearly form a Steiner set in GoH and s(GoH) < s(G)|V(H)|. Let S be a minimum Steiner set of G o H. First note that S £ gH for every g e G, since H is complete. Next if g e pc(S), then all vertices of gH must be in S by Theorem 3. If pc(S) is not a minimum Steiner set in G, we get a contradiction with Lemma 1 or on the other hand with minimality of S. Hence s(G o H) = s(G)|V(H)|. Finally let G be a graph without an universal vertex. For every Steiner set S of G o H, S £ gH for every g e V(G) by Theorem 3. By the same theorem for every g e pc(S), the whole gH must be in S. Thus s(G o H) > s(G)|V(H)| by Lemma 1. Since S' x V(H) is a Steiner set for a minimum Steiner set S' of G, we have s(G o H) = s(G)| V(H) | and the proof is complete. □ CO In [6] the geodetic number g(G o H) was considered and g(G o H) was bounded there between 2 and 3g(G). The Theorem 4 shows that s(G o H) does not behave like g(G o H), since it grows with the number of vertices of H in most cases. 3 Invariants for G o H with respect to Steiner convexity In this section we discuss several invariants connected with convex sets on the lexicographic product with respect to Steiner convexity. Recall that a vertex u of a graph G is called a A-vertex if u is not a simplicial vertex. An induced subgraph Y of the lexicographic product G o H is called A-complete if gH n Y = gH holds for any A-vertex g of pG(Y). The subgraph K of G is (Steiner) convex if V(K) is Steiner convex in V(G). The following theorem, recently proved in [1], is needed. • i Theorem 5 [1, Theorem 3.2] Let G o H be a non-trivial, connected lexicographic product. Then a proper non-complete induced subgraph Y of G o H is Steiner convex if and only if the following conditions hold: (i) pc(Y) is Steiner convex in G, 00 CO t> I CSI 00 CSI CSI (ii) Y is A-complete, and (iii) H is complete. Also in [1] is the analogue version of this theorem (Theorem 2.1) for the geodesic convexity. The only difference is that one need to replace both words Steiner by geodesic. Hence a natural question appears whether also convex invariants have analogue solutions for both convexities in G o H. This question has a positive answer in case of all studied invariants here as we will see in next subsections. 3.1 Rank Recall that srank(G) is the cardinality of a maximum convexly independent set with respect to Steiner convexity. Theorem 6 Let G and H be two non-trivial graphs and let G be connected. With respect to Steiner convexity is , . |srank(G)|V(H)| : if H is complete; srank(G o H) = < (^w(G)w(H) : otherwise. Proof. Suppose first that H is not a complete graph. By Theorem 5, V(G o H) has only trivial Steiner convex sets. Thus the only Steiner convex sets are subsets of V(G) that induce a complete graph and V(G o H). Let A be a subset of V(G o H) on at least three vertices which does not induce a complete graph. Let (g,h) and (g',h') be two non-adjacent vertices of A and (g", h") a third vertex. By Theorem CO 5, sch(A — (g",h//)) = V(G o H). Thus all (maximum) Steiner convex sets induce CO complete graphs in G o H. Since vertices of a complete graph always form a Steiner convexly independent set, we need to find a maximum clique in G o H. Let C C V(GoH) be a set that induce a maximum clique in GoH. Clearly pG(C) = CG induce a maximum complete subgraph in G and its size is w(G). Moreover gH n C induce a complete subgraph in (gH} for every g e pG(C). If |gH n C| < w(H), we have a contradiction with the maximality of C, since Kw(-G) o ) is a complete graph. Hence srank(G o H) = w(G)w(H). Let now H be a complete graph. Let srank(G) = r and let Ai be a Steiner convexly independent set with |A1| = r. By the definition a e sch(A1 — a) for every a e A1. We show next that A1 x V(H) is Steiner convexly independent. If not, we can find an (a1, h1) e A1xV(H) such that (a1,h1) e sch(A1 xV(H) — {(a1, h1)}). We can find (b1,^1),..., e A1 x V(H) — {(a1,h1)} whose Steiner tree contains (a1, h1). Without loss of generality we can assume that b1,..., br, r < m, are in the projection of (b1,^1),..., (bm,^m) in G. By Lemma 1, the Steiner tree of b1,..., br contains a1. That is a1 e sch(A1 — a1), a contradiction, and A1 x V(H) is maximal. Since every Steiner convexly independent subset of V(GoH) projects to a Steiner convexly independent subset of V(G), clearly A1 x V(H) is a maximum Steiner convexly independent set, otherwise we have a contradiction with A1 being a maximum 00 CO I CSI CO CSI CSI CO Steiner convexly independent set of V(G). Hence srank(G o H) = srank(G)|V(H)| and the proof is complete. □ The same theorem holds if we replace all terminology connected to Steiner convexity by the same terminology with respect to geodesic convexity. The only other change is in second paragraph of the proof, where we replace a Steiner tree by a shortest path in the case of geodesic convexity and conclusion follows the same lines. IN 3.2 Hull number i—l The hull number of lexicographic product of graphs with respect to geodetic convexity is described in [8]. Here we prove an analogue result for Steiner convexity. First we prove a lemma in order to prove the theorem. Lemma 7 If H is a complete graph, then every simplicial vertex of a graph G o H belongs to any Steiner hull set of G o H. o Proof. If a simplicial vertex (g, h) is not in a Steiner hull set A, then it is not in any Steiner interval of any subset of V(G o H) by Theorem 3. A contradiction with A being a Steiner hull set. □ Recall that we denote the number of simplicial vertices of graph G by A(G). It is a straightforward observation that (g, h) e V(G o H) is a simplicial vertex if and only if g is a simplicial vertex of G and H is a complete graph. CO Theorem 8 Let G and H be two non-trivial graphs and let G be connected. With respect to Steiner convexity is . 12 : H is not complete; sh(G o H) = < [A(G)|V(H)| + h(G) - A(G) : H is complete. Proof. Let first H be a non-complete graph. Since G o H has no proper Steiner convex sets other than cliques by Theorem 5, the convex hull of any two non-adjacent vertices will be G o H. Hence in this case sh(G o H) = 2. Let now H be a complete graph. By Lemma 7, every simplicial vertex must be in any hull set and there are exactly A(G)|V(H)| simplicial vertices in G o H. Let A = {gi,... ,#a(g),^i, ... ,ifc} be a minimal hull set of G, where gi,...,9\(g) are simplicial vertices and i^ ...,ik are A-vertices of G. We will prove that A = { 91 H,..., 9AH, (^1, h1),..., (ik, h1)} is a minimal hull set of G o H. First observe a subset B = A x {h1}. By Theorem 3, SI(B) contains all vertices in all 9H layers for which g 2, was constructed with the property that Gk has a k-Steiner convex subset that is not (k + 1)-Steiner convex. This family is an example for graphs with large Steiner Caratheodory number, since c(Gfc) > k. Again the same result and proof can be stated if we replace Steiner terminology by the geodesic one. Note only that in the proof Lemma 9, we cannot refer to Lemma 1. However the geodesic version of Lemma 1 is an easy task for the students. Hence we leave the details to the reader. 3.4 Radon number Clearly r(G) > w(G), since in a complete subgraph Kw(-G) for every partition S1 and S2 we have sch(S1) n sch(S2) = 0. Also for complete graphs the Radon number does not exist. CD Theorem 11 Let G and H be two non-trivial graphs, at most one complete and let G be connected. The Radon number with respect to Steiner convexity is (i) r(G o H) = w(G)w(H) + 1 if H is not complete; (ii) max{r(G), w(G)w(H) + 1} < r(G o H) < (r(G) — 1)w(H) + 1 if H is complete. m Proof. Since w(G o H) = w(G)w(H), we always have r(G o H) > w(G)w(H) + 1. For (i), let H be a non-complete graph. If S is a subset of V(G o H) of cardinality w(G)w(H) + 1, then there exists two non-adjacent vertices (g, h) and (g',h'). Sets Si = {(g, h), (g', h')} and S2 = S — Si form a Radon partition. Indeed, Si US2 = S, cm 00 00 Si n S2 = 0, and sch(Si) n sch(S2) = 0, since sch(Si) = V(G o H) by Theorem 5. Hence r(G o H) = w(G)w(H) + 1 if H is a non-complete graph. For (ii), let H be a complete graph, which implies that G is not. Choose any subset S of V(G o H) of cardinality (r(G) - 1)|V(H)| + 1. The cardinality of pG(S) is at least r(G). Let S' be any subset of pG(S) of cardinality r(G). Let Si and S2 form a Radon partition for S'. By S1 we denote all vertices of S that projects to Si and S2 = S - S1. Clearly S1 U S2 = S and S1 n S2 = 0. Let v e sch(S') n sch(S2). Since S' n S2 = 0, then v e S1 or v e S2. Without loss of generality we may assume that v e S1. But then the whole layer vH is in sch(S1). Thus sch(S1) n sch(S2) = 0 and S1 and S2 form a Radon partition of S. Hence r(GoH) < (r(G) - 1)|V(H)| +1. For the lower bound we may assume that r(G) > w(G)w(H) + 1. Let S be a subset of V(G) of cardinality r(G) — 1 that does not admit a Radon partition. Observe S' = S x {h}. If S' admits a Radon partition S1 and S2, then also S = pG(S') admits a Radon partition S1 = pG(S') and S2 = pG(S2) which is not possible. Hence r(G o H) > r(G) and the proof is complete. □ o CSI CM o While in most cases one can expect that r(G) < w(G)w(H) + 1, this is not always the case. Let K+ be a graph obtained from Kn by subdividing each edge by CM a vertex. It is easy to see that a set S of all original vertices of Kn does not admit a Radon partition and is thus r(K+) > n + 1. For G = K+n+1 and H = K^, I < n, we have r(G) > w(G)w(H) + 1. The following corollary is a direct application of (ii) in Theorem 11. £ Corollary 12 Let H be a complete graph and G a connected graph. If r(G) = w(G) + 1, then r(G o H) = w(G)w(H) + 1 (with respect to the Steiner convexity). I-H As an example that the lower bound of (ii) in Theorem 11 is not always attained let G = C2k+1, k > 2, and H = Kn. It is easy to see that r(C2k+1) = 4 and we have 2n + 1 < r(G o H) < 3n + 1 by (ii) of Theorem 11. Let uv e E(C2fc+1) and w the antipodal vertex of u and v on C2k+1. For S = {(w,h)} U ({v,u} x V(H)), where h e V(H), it is easy to see that S has no Radon partition. Since |S| = 2n + 1 we have 2n + 1 < r(G o H). Moreover, every subset of V(G o H) of cardinality 2n + 2 has a Radon partition and we have r(C2k+1 o Kn) = 2n + 2 (we leave the details to the reader). As in the previous subsections of this section we can state analogue results for the geodesic convexity if we replace Steiner terminology by geodesic one. CO CD 4 Erratum product, we found a small error in the Proposition 14 of the paper [7], and we have While going through the hull number, rank, and Steiner number of lexicographic CM 00 00 rectified the proposition. We state the definition which is used in that paper and proposition as it is. But first we define the strong product. The strong product of graphs G and H is the graph G IXI H with the vertex set V(G) x V(H). Vertices (gi,hi) and (g2, h2) are adjacent if either g1g2 G E(G) and h1 = h2 or g1 = g2 and h1h2 G E(H) or g1g2 G E(G) and h1 h2 G E(H). Definition 13 Let S be a set of vertices in a graph G. Then, S is said to satisfy the condition (A) if, for every vertex x G S, there exists two vertices y, z G S \ x such that x G I[y, z]. (B) if there are two vertices x, y G S such that x G I[S \ x] and y G I[S \ y] o Proposition 14 [7, Proposition 5] Let G be a graph with a minimum geodetic set S satisfying the condition (A). Then, for every positive integer n, g(GBKn) = g(G). Example 15 (Counter example for Proposition 14) Let G = C6 and H = Kn. Let uv and xy be two opposite edges of C6. Set S = {u, x,v,z} is the minimum geodetic set that satisfies the condition (A) and g(G) = 2. But we can see that g(G B H) = 4 > g(G). 00 We modify the Proposition 14 as follows. Proposition 16 Let G be a graph with a minimum geodetic set S satisfying the condition (A). Then, for every positive integer n, g(G B Kn) = |S|. CO Proof. We can see that |S| need not be g(G) as in Example 15. The proof follows CO from the proof of the Proposition 5 in [7] by replacing g(G) by |S|. □ References [1] B. S. Anand, M. Changat, S. Klavzar, I. Peterin, Convex Sets in Lexicographic Products of Graphs, Graphs Combin. 28 (2012) 77-84. W [2] S. Arora, Approximation schemes for NP-hard geometric optimization problems: a survey, Math. Program. 97 (2003) 43-69. [3] K. Balakrishnan, M. Changat, Hull numbers of path convexities on graphs, in: Convexity in Discrete Structures (M. Changat, S. KlavZar, H. M. Mulder, A. Vijayakumar, eds.), Lecture Notes Ser. 5, Ramanujan Math. Soc. (2008) 47-55. [4] B. Bresar, M. Changat, J. Mathews, I. Peterin, P. G. Narasimha-Shenoi, A. Tepeh Horvat, Steiner intervals, geodesic intervals, and betweenness, Discrete Math. 309 (2009) 6114-6125. CM 00 CO IN [5] B. Bresar, T. Gologranc, On a local 3-Steiner convexity, European J. Combin. 32 (2011) 1222-1235. [6] B. Bresar, T. Kraner Sumenjak, A. Tepeh, The geodetic number of the lexicographic product of graphs, Discrete Math. 311 (2011) 1693-1698. [7] J. Caceres, C. Hernando, M. Mora, I. M. Pelayo, M. L. Puertas, On the geodetic and the hull numbers in strong product graphs, Comput. Math. Appl. 60 (2010) 3020-3031. [8] S. R. Canoy Jr., G. B. Cagaanan, On the Hull Number of the Composition of Graphs, Ars Combin. 75 (2005) 113-119. [9] M. Changat, A. K. Lakshmikuttyamma, J. Mathews, I. Peterin, P. G. Narasimha-Shenoi, A. Tepeh, A note on 3-Steiner intervals and betweenness, Discrete Math. 311 (2011) 2601-2609. [10] M. Changat, J. Mathews, P. G. Narasimha-Shenoi, I. Peterin, n-ary transit functions in graphs, Discuss. Math. Graph Theory 30 (2010) 671-685. I CM [11] M. Changat, H. M. Mulder, G. Sierksma, Convexities Related to Path Properties on Graphs, Discrete Math. 290 (2005) 117-131. [12] M. Changat, J. Mathew, On Triangle path convexity in graphs, Discrete Math. 206 (1999) 91-95. CO [13] G. Chartrand, O. R. Oellermann, S. Tian, H. B. Zou, Steiner distance in graphs, Casopis Pro. Pest. Mat. 114 (1989) 399-410. [14] G. Chartrand, P. Zhang, The Steiner Number of a Graph, Discrete Math. 242 (2002) 41-54. [15] P. Duchet, Convex sets in graphs II. Minimal path convexity, J. Combin. Theory Ser. B 44 (1988) 307-316. [16] P. Duchet, Discrete Convexity: retractions and morphisms and partition problem, in: Proc. of the conf. on graph connections (R. Balakrishnan, H. M. Mulder and A. Vijayakumar eds.), New Delhi (1999) 87-90. CD [17] M. R. Garey, D. S. Johnson, Computers and Intractability: A Guide to NP-completnes, Freeman, New York, 1979. [18] R. Hammack, W. Imrich, S. Klavzar, Handbook of Product Graphs, Second Edition, CRC Press, Boca Raton, FL, 2011. CD [19] M. Henning, M. H. Nielsen, O. R. Oellermann, Local Steiner convexity, Euro pean J. Combin. 30 (2009) 1186-1193. 00 00 IN CO CD Jh CD CO u a CD U [20] C. Hernando, T. Jiang, M. Mora, I.M. Pelayo, C. Seara, On the Steiner, geodetic and hull numbers of graphs, Discrete Math. 293 (2005) 139-154. [21] A. Moss, Y. Rabani, Approximation algorithms for constrained node weighted Steiner tree problems, SIAM J. Comput. 37 (2007) 460-481. [22] O. R. Oellermann, M. L. Puertas, Steiner intervals and Steiner geodetic numbers in distance-hereditary graphs, Discrete Math. 307 (2007) 88-96. [23] I. Peterin, Pre-hull number and lexicographic product, Discrete Math. 312 (2012) 2153-2157. [24] M. L. J. van de Vel, Theory of Convex Structures, North Holland, Amsterdam, 1993. [25] H. G. Yeh, C.-Y. Chiang, S.-H. Peng, Steiner centers and Steiner medians of graphs, Discrete Math. 308 (2008) 5298-5307. o