¿^creative , ars mathematica ^commons contemporánea Also available at http://amc-journal.eu ISSN 1855-3966 (printed edn.), ISSN 1855-3974 (electronic edn.) ARS MATHEMATICA CONTEMPORANEA 12 (2017) 127-134 The strong metric dimension of generalized Sierpinski graphs with pendant vertices Ehsan Estaji Department of Mathematics and Computer Sciences, Hakim Sabzevari University, Sabzevar, Iran Juan Alberto Rodriguez-Velazquez Departament d'Enginyeria Informatica i Matematiques, Universitat Rovira i Virgili, Av. Pai'sos Catalans 26, 43007 Tarragona, Spain Received 17 February 2015, accepted 10 February 2016, published online 2 November 2016 Abstract Let G be a connected graph of order n having -(G) end-vertices. Given a positive integer t, we denote by S(G, t) the t-th generalized Sierpinski graph of G. In this note we show that if every internal vertex of G is a cut vertex, then the strong metric dimension of S (G, t) is given by , , u e(G) (n4 - 2nt-1 + l) - n +1 dims(S(G,t)) = ---1-. n1 Keywords: Strong metric dimension, Sierpinski graphs. Math. Subj. Class.: 05C12, 05C76 1 Introduction For two vertices u and v in a connected graph G, the interval 1G[u, v] between u and v is defined as the collection of all vertices that belong to some shortest u - v path. A vertex w strongly resolves two vertices u and v if v G 1G [u, w] or u G 1G [v, w]. A set S of vertices in a connected graph G is a strong metric generator for G if every two vertices of G are strongly resolved by some vertex of S. The smallest cardinality of a strong metric generator of G is called strong metric dimension and is denoted by dims (G). After the publication of E-mail addresses: ehsan.estaji@hsu.ac.ir (Ehsan Estaji), juanalberto.rodriguez@urv.cat (Juan Alberto Rodriguez-Velazquez) ©® This work is licensed under http://creativecommons.org/licenses/by/3.0/ 128 Ars Math. Contemp. 12 (2017) 111-126 the first paper [16], the strong metric dimension has been extensively studied. The reader is invited to read, for instance, the following works [10, 11, 12, 13, 15] and the references cited therein. For some basic graph classes, the strong metric dimension is easy to compute. For instance, dims (G) = n — 1 if and only if G is the complete graph of order n. For the cycle Cn of order n the strong dimension is dims(Cn) = [n/2] and if T isatreewith l(T) leaves, its strong metric dimension equals 1(T) — 1 (see [16]). Given a connected graph G and two vertices x, y G V(G), we denote by dG(x, y) the distance from x to y. A vertex u of G is maximally distant from v if for every vertex w in the open neighborhood of u, dG(v, w) < dG(u, v). If u is maximally distant from v and v is maximally distant from u, then we say that u and v are mutually maximally distant. The boundary of G = (V, E) is defined as d(G) = {u G V : there exists v G V such that u, v are mutually maximally distant}. For some basic graph classes, such as complete graphs Kn, complete bipartite graphs Kr,s, cycles Cn and hypercube graphs Qk, the boundary is simply the whole vertex set. It is not difficult to see that this property holds for all 2-antipodal1 graphs and also for all distance-regular graphs. Notice that the boundary of a tree consists exactly of the set of its leaves. A vertex of a graph is a simplicial vertex if the subgraph induced by its neighbors is a complete graph. Given a graph G, we denote by a(G) the set of simplicial vertices of G. Notice that i. When n = 3, those graphs are exactly Tower of Hanoi graphs. Later, those graphs have been called Sierpinski graphs in [7] and they were studied by now from numerous points of view. The reader is invited to read, for instance, the following recent papers [2, 5, 4, 7, 8, 9] and references therein. This construction was generalized in [3] for any graph G, by defining the t-th generalized Sierpinski graph of G, denoted by S(G, t), as the graph with vertex set V4(G) and edge set defined as follows. {u, v} is an edge if and only if there exists i e {1,..., t} such that: (i) uj = vj, if j < i; (ii) uj = vj and {uj, vj} e E(G); (iii) uj = vj and vj = uj if j > i. Figure 1: A graph G and the generalized Sierpinski graph S(G, 2) Figure 1 shows a graph G and the Sierpinski graph S(G, 2), while Figure 2 shows the Sierpinski graph S(G, 3). Notice that if {u, v} is an edge of S(G, t), there is an edge {x, y} of G and a word w such that u = wxyy ... y and v = wyxx ... x. In general, S(G, t) can be constructed recursively from G with the following process: S(G, 1) = G and, for t > 2, we copy n times S (G, t - 1) and add the letter x at the beginning of each label of the vertices belonging to the copy of S(G, t - 1) corresponding to x. Then for every edge {x, y} of 130 Ars Math. Contemp. 12 (2017) 111-126 G, add an edge between vertex xyy... y and vertex yxx ... x. See, for instance, Figure 2. Vertices of the form xx ... x are called extreme vertices. Notice that for any graph G of order n and any integer t > 2, S(G, t) has n extreme vertices and, if x has degree d(x) in G, then the extreme vertex xx ... x of S(G, t) also has degree d(x). Moreover, the degrees of two vertices yxx... x and xyy ... y, which connect two copies of S(G, t - 1), are equal to d(x) + 1 and d(y) + 1, respectively. 1. To the best of our knowledge, [14] is the first published paper studying the generalized Sierpiriski graphs. In that article, the authors obtained closed formulae for the Randic index of polymeric networks modelled by generalized Sierpiriski graphs. In this note we consider the case where every internal vertex of G is a cut vertex and we obtain a closed formula for the strong metric dimension of S(G, t). 3 The strong metric dimension of S(G, t) The following basic lemma will become an important tool to prove our main results. Lemma 3.1. Let G be a connected graph. If v is a cut vertex of G, then v ^ d(G). Proof. Let v G V (G) be a cut vertex and x G V (G)-{v}. Let Gx be the connected compo- J. A. Rodrigues-Velazquez andE. Estaji: Strong metric dimension of Sierpinski graphs 131 nentof G -{ v } containing x andlet G2 bea connected component of G—{ v } different from Gi. Since there exists y G V(G2) which is adjacent to v in G and dG(x, v) < dG(x, y), we conclude that x and v are not mutually maximally distant in G. □ An end-vertex is a vertex of a graph that has exactly one edge incident to it, while a support vertex is a vertex adjacent to an end-vertex. Theorem 3.2. Let G be a connected graph and let -(G) be the number of end-vertices of G. Then, dims (G) > -(G) - 1. Moreover, if every vertex of degree greater than one is a cut vertex, then the bound is achieved. Proof. Let G be a connected graph. Since the set Q(G) of end-vertices of G is a subset of d(G) and the subgraph of GSR induced by Q(G) is a clique, we conclude that a(GSR) > -(G) - 1. Hence, by Theorem 1.1 we obtain the lower bound. Now, if every vertex of degree greater than one is a cut vertex, by Lemma 3.1 we have that d(G) is equal to the set of end-vertices of G. Then GSR = K|e(G)| and so Theorem 1.1 leads to dims(G) = -(G) - 1. □ From now on, we will say that a vertex of degree greater than one in a graph G is an internal vertex of G. We shall show that if every internal vertex of G is a cut vertex, then the bound above is achieved for S(G, t). To begin with, we state the following lemma. Lemma 3.3. Let G be a graph of order n having -(G) end-vertices. For any positive integer t, the number of end-vertices of S(G, t) is , , u -(G) (ri - 2nt-i + 1) -(S(G, t)) = ---L. n - 1 Proof. In this proof, we denote by Sup(G) the set of support vertices of G. Also, if x G Sup(G), then -G(x) will denote the number of end-vertices of G which are adjacent to x. Let t > 2. For any x G V(G), we denote by Sx(G,t - 1) the copy of S(G,t - 1) corresponding to x in S(G, t), i.e., Sx(G, t - 1) is the subgraph of S(G, t) induced by the set {xw : w G Vt-1(G)}, which is isomorphic to S(G, t - 1). To obtain the result, we only need to determine the contribution of Sx(G, t - 1) to the number of end-vertices of S(G, t), for all x G V(G). By definition of S(G, t), there exists an edge of S(G, t) connecting the vertex xy ... y of Sx(G, t - 1) with the vertex yx ... x of Sy (G, t - 1) if and only if x and y are adjacent in G. Hence, an end-vertex xy ... y of Sx(S(G, t - 1) is adjacent in S(G, t) to a vertex yx... x of Sy (G, t - 1) if and only if y is an end-vertex of G and x is its support vertex. Thus, if x G Sup(G), then the contribution of Sx(G, t -1) to the number of end-vertices of S(G, t) is -(S(G, t - 1)) - -G(x) and, if x G Sup(G), then the contribution of Sx(G, t - 1) to the number of end-vertices of S(G, t) is -(S(G, t - 1)). Then we obtain, -(S(G,t)) = (n -| Sup(G)|)-(S(G,t - 1)) + £ (-(S(G,t - 1)) - -g(x)) xGSup(G) = n-(S(G, t - 1)) - -(G). 132 Ars Math. Contemp. 12 (2017) 111-126 Now, since -(S(G, 1)) = -(G), we have that (nt-1 - 1)' -(S(G, t)) = -(G) (ni-1 - nt-2-----n - 1) = -(G) ( nt-1 - n - 1 J Therefore, the result follows. □ The following result is a direct consequence of Theorem 3.2 and Lemma 3.3. Theorem 3.4. Let G be a connected graph of order n having -(G) end-vertices and let t be a positive integer. Then , , u e(G) (n4 - 2nt-1 + 1) - n +1 dims(S(G,t)) > --->--. n - 1 As we will show in Theorem 3.6, the bound above is tight. Lemma 3.5. Let G be a connected graph and let t be a positive integer. If every internal vertex of G is a cut vertex, then every internal vertex of S(G, t) is a cut vertex. Proof. As above, for any x G V(G), we denote by Sx(G, t - 1) the copy of S(G, t -1) corresponding to x in S(G, t). We proceed by induction on t. Let S(G, 1) = G be a connected graph such that every internal vertex is a cut vertex and assume that every internal vertex of S(G, t - 1) is a cut vertex. We differentiate two cases for any internal vertex xw of S(G, t), where x G V(G) and w G Vt-1(G). Case 1. w has degree one in S(G, t - 1). In this case xw has degree two in S(G, t). Hence, xw is adjacent to x1 w', for some x1 G V (G)-{x}, and then w = x1 x1... x1, w' = xx ... x, x1 is an end-vertex of G and x is the support of x1. As a result, {xw, x1w'} is the only edge connecting vertices in Sx1 (G, t - 1) to vertices outside the subgraph SX1 (G, t - 1). Therefore, xw is a cut vertex of S(G, t). Case 2. w is a cut vertex of S(G, t - 1). In this case, we take two connected components C1 and C2 obtained by removing w from S(G, t - 1). Suppose, for contradiction purposes, that xw is not a cut vertex of S(G, t). Then there exist two neighbours x1 , xk of x and a sequence of subgraphs SX1 (G, t - 1), Sx2 (G, t -1),..., SXk (G, t - 1) such that x1... x1 G V(C1), xk ... xk G V(C2) and there exists an edge of S(G, t) connecting Sxi (G, t - 1) to Sxi+1 (G, t - 1), for all i G {1, 2,..., k}. Note that the only vertices connecting Sxi (G, t - 1) and Sxi+1 (G, t -1) are xjxi+1xi+1... xj+1 and xi+1xjxj... x4, where xj and xj+1 are adjacent in G. Hence, x, x1, x2,..., xk, x is a cycle in G, and so there is a cycle in S(G, t - 1) of the form Pxxi ,PXiX2^2x3,... ,PXfc_ixfc, PXfcx, where Px^+i is the path of order 2t-1 from xjxH ... x4 to xi+1 xi+1... xi+1 composed by binary words on alphabet } (the paths Pxx1 and Pxkx are defined by analogy) and we identify the vertex xjxj... xj of two consecutive paths PXi-lXi and PXiXi+1 to form the cycle. As a result, there are two disjoint paths from x1x1... x1 to xkxk.... xk, which contradicts the fact that x1x1... x1 G V(C1) and xkxk.... xk G C2. Therefore, xw is a cut vertex of S(G, t). According to the two cases above, we conclude the proof by induction. □ J. A. Rodrigues-Velazquez andE. Estaji: Strong metric dimension of Sierpinski graphs 133 Our next result is obtained from Theorem 3.2 and Lemma 3.5. Theorem 3.6. Let G be a connected graph of order n having -(G) end-vertices and let t be a positive integer. If every internal vertex of G is a cut vertex, then , , u e(G) (n/' - 2ni-1 + l) - n +1 dims(S(G,t)) = ----. n-1 Obviously, if the base graph is a tree, then we can apply the formula above. In particular, we would emphasize the following particular case of this result, where K1r denotes the star graph of r leaves and Pr denotes the path graph of order r. Corollary 3.7. For any integers r,t > 2, • dims(S(Ki,r,t)) = (r +1)t-1(r - 1). • dims(S(Pr,t))=2rt - ^ r + 3. r-1 Let G be a graph of order n and let H = {H1,H2,... ,Hn} be a family of graphs. The corona product graph G © H is defined as the graph obtained from G and H by taking one copy of G and joining by an edge each vertex of Hi with the iih-vertex of G. These graphs were defined by Frucht and Harary in [1]. Corollary 3.8. Let G be a graph of order n and let H = {H1, H2,..., Hn} be a family of empty graphs of order ni, respectively. Then for any positive integer t, dims(S(G © H, t)) = n>±n')t-1 (n + n' - 2) - n + 1 n + n' — 1 where n' = ^^ n References [1] R. Frucht and F. Harary, On the corona of two graphs, Aequationes Math. 4 (1970), 322-325. [2] S. Gravier, M. Kovse, M. Mollard, J. Moncel and A. Parreau, New results on variants of covering codes in Sierpinski graphs, Des. Codes Cryptogr. 69 (2013), 181-188, doi:10.1007/ s10623-012-9642-1, http://dx.doi.org/10.1007/s10623-012-9642-1. [3] S. Gravier, M. Kovse and A. Parreau, Generalized Sierpinski graphs, 2011, http://www. renyi.hu/conferences/ec11/posters/parreau.pdf. [4] A. M. Hinz and C. Holz auf der Heide, An efficient algorithm to determine all shortest paths in Sierpinski graphs, Discrete Appl. Math. 177 (2014), 111-120, doi:10.1016/j.dam.2014.05.049, http://dx.doi.org/10.1016/j-dam.2014.05.049. [5] A. M. Hinz and D. Parisse, The average eccentricity of Sierpinski graphs, Graphs Combin. 28 (2012), 671-686, doi:10.1007/s00373-011-1076-4, http://dx.doi.org/10.10 07/ s00373-011-1076-4. [6] S. Klavzar and U. Milutinovic, Graphs S(n, k) and a variant of the Tower of Hanoi problem, Czechoslovak Math. J. 47(122) (1997), 95-104, doi:10.1023/A:1022444205860, http:// dx.doi.org/10.1023/A:1022444205860. 134 Ars Math. Contemp. 12 (2017) 111-126 [7] S. Klavzar, U. MilutinoviC and C. Petr, 1-perfect codes in Sierpinski graphs, Bull. Austral. Math. Soc. 66 (2002), 369-384, doi:10.1017/S0004972700040235, http://dx.doi.org/ 10.1017/S0004972700040235. [8] S. KlavZar, I. Peterin and S. S. Zemljic, Hamming dimension of a graph—the case of Sierpinski graphs, European J. Combin. 34 (2013), 460-473, doi:10.1016/j.ejc.2012.09.006, http:// dx.doi.org/10.1016/j.ejc.2012.09.006. [9] S. KlavZar and S. S. Zemljic, On distances in Sierpinski graphs: almost-extreme vertices and metric dimension, Appl. Anal. Discrete Math. 7 (2013), 72-82, doi:10.2298/ AADM130109001K, http://dx.doi.org/10.22 98/AADM13010 9001K. [10] J. Kratica, V. Kovacevic-Vujcic, M. Cangalovic and N. Mladenovic, Strong metric dimension: a survey, Yugosl. J. Oper. Res. 24 (2014), 187-198, doi:10.2298/YJ0R130520042K, http: //dx.doi.org/10.22 98/YJOR130520 042K. [11] J. Kratica, V. Kovacevic-Vujcic, M. Cangalovic and M. Stojanovic, Minimal doubly resolving sets and the strong metric dimension of Hamming graphs, Appl. Anal. Discrete Math. 6 (2012), 63-71, doi:10.2298/AADM111116023K, http://dx.doi.org/10.22 98/ AADM111116023K. [12] D. Kuziak, Strong resolvability in product graphs, Ph.D. thesis, Universitat Rovira i Virgili, 2014. [13] O. R. Oellermann and J. Peters-Fransen, The strong metric dimension of graphs and digraphs, Discrete Appl. Math. 155 (2007), 356-364, doi:10.1016/j.dam.2006.06.009, http://dx. doi.org/10.1016/j.dam.2006.06.009. [14] J. A. Rodriguez-Velazquez and J. Tomas-Andreu, On the Randic index of polymeric networks modelled by generalized Sierpinski graphs, MATCH Commun. Math. Comput. Chem. 74 (2015), 145-160. [15] J. A. Rodriguez-Velazquez, I. G. Yero, D. Kuziak and O. R. Oellermann, On the strong metric dimension of Cartesian and direct products of graphs, Discrete Math. 335 (2014), 8-19, doi:10. 1016/j.disc.2014.06.023, http://dx.doi.org/10.1016/j.disc.2014.06.023. [16] A. Sebo and E. Tannier, On metric generators of graphs, Math. Oper. Res. 29 (2004), 383-393, doi:10.1287/moor.1030.0070, http://dx.doi.org/10.1287/moor.1030.0 07 0.