3_yi.dvi EUROPEAN JOURNAL OF PURE AND APPLIED MATHEMATICS Vol. 5, No. 3, 2012, 302-316 ISSN 1307-5543 – www.ejpam.com A Comparison on Metric Dimension of Graphs, Line Graphs, and Line Graphs of the Subdivision Graphs Douglas J. Klein, Eunjeong Yi∗ Texas A&M University at Galveston, Galveston, TX 77553, USA Abstract. The line graph L(G) of a simple graph G is the graph whose vertices are in one-to-one correspondence with the edges of G; two vertices of L(G) are adjacent if and only if the corresponding edges of G are adjacent. If S(G) is the subdivision graph of a graph G, then the para-line graph G∗ of G is L(S(G)). The metric dimension dim(G) of a graph G is the minimum cardinality of a set of vertices such that every vertex of G is uniquely determined by its vector of distances to the chosen vertices. In this paper, we study metric dimension of para-line graphs; we also compare metric dimension of graphs, line graphs, and para-line graphs. First, we show that ⌈log2∆(G)⌉ ≤ dim(G⋆) ≤ n− 1, for a simple and connected graph G of order n ≥ 2 with the maximum degree ∆(G), where both bounds are sharp. Second, we determine the metric dimension of para-line graphs for some classes of graphs; further, we give an example of a graph G such that max{dim(G), dim(L(G)), dim(G⋆)} equals dim(G), dim(L(G)), and dim(G⋆), respectively. We conclude this paper with some open problems. 2010 Mathematics Subject Classifications: 05C12 Key Words and Phrases: line graph, para-line graph, line graph of the subdivision graph, distance, resolving set, metric dimension 1. Introduction Let G = (V (G), E(G)) be a finite, simple, undirected, and connected graph of order |V (G)| = n ≥ 2. For a graph G and W ⊆ V (G), we denote by 〈W 〉 the subgraph induced by W . For a vertex v ∈ V (G), the open neighborhood of v is the set NG(v) = {u | uv ∈ E(G)}, and the closed neighborhood of v is the set NG[v] = NG(v) ∪ {v}; for S ⊆ V (G), the open neighborhood of S is the set NG(S) = ∪v∈SNG(v). The degree of a vertex v ∈ V (G), denoted by degG(v), is the the number of edges incident to the vertex v in G; an end-vertex is a vertex of degree one. We denote by ∆(G) the maximum degree of a graph G. The distance between two vertices u, v ∈ V (G), denoted by dG(u, v), is the length of the shortest path in G between u and v; we omit G when ambiguity is not a concern. The diameter, diam(G), of a graph G is given by max{d(u, v) | u, v ∈ V (G)}. We denote by Kn, Cn, and Pn the complete graph, the ∗Corresponding author. Email addresses: kleind�tamug.edu (D. Klein), yie�tamug.edu (E. Yi) http://www.ejpam.com 302 c© 2012 EJPAM All rights reserved. D. Klein, E. Yi / Eur. J. Pure Appl. Math, 5 (2012), 302-316 303 cycle, and the path on n vertices, respectively. For other terminologies in graph theory, refer to [6]. The subdivision graph S(G) of a graph G is obtained from G by deleting every edge uv of G and replacing it by a vertex w of degree 2 that is joined to u and v [see p.151 of 6]. The line graph L(G) of a simple graph G is the graph whose vertices are in one-to-one correspondence with the edges of G; two vertices of L(G) are adjacent if and only if the corresponding edges of G are adjacent [see 2, 18, 28, 29]. Following [25], we define the para-line graph of G to be L(S(G)), which we will denote by G⋆. Alternatively, we can construct G⋆ from G as follows: (i) Replace each vertex u ∈ V (G) by K(u), the complete graph on degG(u) vertices; (ii) There is an edge joining a vertex of K(u1) and a vertex of K(u2) in G⋆ if and only if there is an edge joining u1 and u2 in G; (iii) For each vertex v of K(u), degG⋆(v) = degG(u). A vertex x ∈ V (G) resolves a pair of vertices u, v ∈ V (G) if d(u, x) 6= d(v, x). A set of vertices S ⊆ V (G) resolves G if every pair of distinct vertices of G is resolved by some vertex in S; then S is called a resolving set of G. For an ordered set S = {w1, w2, . . . , wk} ⊆ V (G) of distinct vertices, the metric code (or code, for short) of v ∈ V (G) with respect to S, denoted by codeS(v), is the k-vector (d(v, w1), d(v, w2), . . . , d(v, wk)). The metric dimension of G, denoted by dim(G), is the minimum cardinality over all resolving sets of G. Slater [26, 27] introduced the concept of a resolving set for a connected graph under the term locating set. He referred to a minimum resolving set as a reference set, and the cardinality of a minimum resolving set as the location number of a graph. Independently, Harary and Melter [13] studied these concepts under the term metric dimension. Since metric dimension is suggestive of the dimen- sion of a vector space in linear algebra, sometimes a minimum resolving set of G is called a basis of G. Metric dimension as a graph parameter has numerous applications, among them are robot navigation [17], sonar [27], combinatorial optimization [23], and pharmaceutical chemistry [5]. It is noted in [12] that determining the metric dimension of a graph is an NP-hard problem. Metric dimension has been heavily studied; for surveys, see [1] and [7]. For more articles on metric dimension in graphs, see [3, 4, 8, 9, 14, 16, 19, 24]. In this paper, we study metric dimension of para-line graphs; we also compare metric dimension of graphs, line graphs, and para-line graphs. For a simple and connected graph G of order n ≥ 2, we show that ⌈log2∆(G)⌉ ≤ dim(G⋆) ≤ n− 1, and the bounds are sharp. We also determine the metric dimension of para-line graphs for some classes of graphs; further, we give an example of a graph G such that max{dim(G), dim(L(G)), dim(G⋆)} equals dim(G), dim(L(G)), and dim(G⋆), respectively. We conclude this paper with some open problems. 2. Para-Line Graphs: Applications and Basic Properties Para-line graphs are chemically relevant, though little considered in the surge of chemical graph theory of the last few decades. Often a (usually “organic”) molecule is represented by D. Klein, E. Yi / Eur. J. Pure Appl. Math, 5 (2012), 302-316 304 a graph whose vertices correspond to atoms other than hydrogen, and whose edges corre- spond to bonded pairs of such atoms. For example, for stable hydrocarbon molecules, it is understood that the carbon atoms have valence 4 counting connections to H atoms, so that this H-deleted graph determines the molecular structure (see Figure 1). But there are other ways to represent molecules in terms of graphs, say in terms of a minimal set of localized “orbitals” each taken as a vertex, with edges identified to stronger interactions between pairs of orbitals. Indeed such a graph was implicit in several early quantum chemical works pre- saging the first-principles quantum chemistry mediated by way of large computers. This now standard quantum chemical approach has been tremendously successful in treating molecules one by one. But the simpler orbital model offers a potential advantage of general meaningful theorems applying to whole classes of molecules. One can view para-line graphs with vertices corresponding to atomic “hybrid” orbitals, and edges corresponding to stronger interactions between pairs of such orbitals. Given a traditional molecular structural formula for a hydro- carbon without multiple bonds, there corresponds a graph G with one vertex corresponding to each atom (either C or H), and an edge corresponding to each bond. (a) Hydrocarbon C2H6 (b) Hydrocarbon graph G (c) its para-line graph G⋆ Figure 1 If we let E⋆in = ∪u∈V (G)E(K(u)), then the usual chemical bonds are manifested in E⋆ bond = E(G⋆)− E⋆in. For a hydrocarbon, each C atom is represented by a tetrahedral quartet of interconnected sites (a 4-vertex clique), each vertex corresponding to a different (so-called sp) hybrid orbital; each H atom by a single atomic (1s) orbital; each edge of E⋆ bond corre- sponding to an interatomic chemical molecular bond; and each edge of E⋆in by an intra-atomic interaction. Often, the vertices of the resulting para-line graph are assigned different weights corresponding to C or H atoms; also, it’s typically given different edge weights corresponding to the C−C and C−H bonds. There are also the intra-atomic interactions between different hybrid orbitals on the same atom, and then the intra-atomic edge weights would be somewhat less than the inter-atomic weights. For articles on chemical graphs, see [11, 20, 21, 22]. Next, we recall the following Theorem 1. [29] Let G1 and G2 be connected graphs with G1 6∼= G2. Then L(G1) ∼= L(G2) if and only if {G1, G2} = {C3, K1,3}, where K1,3 is the star on 4 vertices. In [15], it is shown that G⋆1 ∼= G⋆2 if and only if G1 ∼= G2. In order to be self-contained, we include a proof here. D. Klein, E. Yi / Eur. J. Pure Appl. Math, 5 (2012), 302-316 305 Theorem 2. [15] Let G1 and G2 be connected graphs. Then G⋆1 ∼= G⋆2 if and only if G1 ∼= G2. Proof. (⇐=) It is obvious. (=⇒) Let S(G) denote the subdivision graph of a graph G; notice that |E(S(G))|= 2|E(G)|, an even number. Then G⋆1 ∼= G⋆2 implies L(S(G1)) ∼= L(S(G2)). If S(G1) 6∼= S(G2), then S(G1) = C3 or S(G1) = K1,3 by Theorem 1; in each case, |E(S(G1)| = 3, an odd number, which is impossible. Thus, S(G1) ∼= S(G2). It remains to show that G1 ∼= G2. Notice that S(Gi) is a bi-partite graph with a unique bi-partition of the vertex set of S(Gi) by the connectedness of S(Gi), where i = 1,2. Let Vi,1 = V (Gi) and Vi,2 = V (S(Gi))− V (Gi) be the bi-partite sets of S(Gi), where i = 1,2. For each P3 of S(Gi), say uvu′, such that u,u′ ∈ Vi,1 and v ∈ Vi,2 (i = 1,2), we replace uvu′ by uu′. The resulting graph is G1 ∼= G2. 3. Bounds of Metric Dimension on para-Line Graphs In this section, we obtain general bounds of the metric dimension of para-line graphs. First, we recall the bounds of the metric dimension of graphs and its line graphs. Theorem 3. [5] If G is a connected graph of order n≥ 2 and diameter d, then f (n, d)≤ dim(G)≤ n− d , where f (n, d) is the least positive integer k for which k+ dk ≥ n. A generalization of Theorem 3 has been given in [14] by Hernando et al. Theorem 4. [14] Let G be a graph of order n, diameter d ≥ 2, and metric dimension k. Then n≤ �� 2d 3 � + 1 �k + k ⌈ d 3 ⌉ ∑ i=1 (2i− 1)k−1. Theorem 5. [10] If G is a connected graph of order n≥ 5, then ⌈log2∆(G)⌉ ≤ dim(L(G))≤ n− 2. Next, we recall the following definitions that are stated in [14]. Two distinct vertices u, v of a graph G are adjacent twins if NG[u] = NG[v], and non-adjacent twins if NG(u) = NG(v). Observe that if u, v are adjacent twins then uv ∈ E(G), and if u, v are non-adjacent twins then uv 6∈ E(G). If u, v are adjacent or non-adjacent twins, then u, v are twins; if S is a resolving set of G, then u ∈ S or v ∈ S. Theorem 6. Let G be a connected graph of order n≥ 2. Then ⌈log2∆(G)⌉ ≤ dim(G⋆)≤ n− 1, (1) and both bounds are sharp. D. Klein, E. Yi / Eur. J. Pure Appl. Math, 5 (2012), 302-316 306 Proof. First, we consider for 2≤ n≤ 4. If n= 2, then ∆(G) = 1 and dim(G⋆) = 1. If n= 3, then ∆(G) = 2 and 1 ≤ dim(G⋆) ≤ 2. If n = 4, then 2 ≤ ∆(G) ≤ 3 and 1 ≤ dim(G⋆) ≤ 3; here, dim(G⋆) = 1 if and only if G = P4, and dim(G⋆) = 3 if and only if G = K4. So, (1) holds for 2≤ n≤ 4. Next, we consider n≥ 5. The lower bound of (1) follows by Theorem 5, since ∆(G) = ∆(S(G)). For the sharpness of the lower bound, take G = Pn; then ∆(G) = 2 and dim(G⋆) = 1 (see (a) of Theorem 8). Next, we prove the upper bound of (1). Let V (G) = {v1, v2, . . . , vn}, and let degG(vi) = di (1 ≤ i ≤ n). Following the construction of G⋆ from G, let each vertex vi be replaced by K(vi) ∼= Kdi ; here, we denote by Ui the vertex set V (K(vi) ) = {ui,1,ui,2, . . . ,ui,di } ⊆ V (G⋆) for each i (1 ≤ i ≤ n). Let S = {u1,a1 ,u2,a2 , . . . ,un−1,an−1 } with |S| = n− 1 such that |S ∩Ui| = 1 for each i (1 ≤ i ≤ n− 1) and that no two vertices in S are adjacent in G⋆. We will show that S is a resolving set for G⋆. It suffices to show that, for any two vertices ux ,uy ∈ V (G⋆)− S, dG⋆(ux ,ui,ai ) 6= dG⋆(uy ,ui,ai ) for some ui,ai ∈ S. (2) We consider two cases. Case 1: ux ,uy ∈ Ui for some i (1≤ i ≤ n). We consider two subcases. Subcase 1.1: 1≤ i ≤ n−1. First, suppose that NG⋆(ux )∩Un = ;= NG⋆(uy)∩Un. Since at most one vertex of Ui − {ui,ai } is adjacent to at most one vertex of Uk for k 6= i (1 ≤ k ≤ n− 1), say NG⋆(ux) ∩ Uk 6= ;, we have dG⋆(ux ,uk,ak ) < dG⋆(uy ,uk,ak ). Second, suppose that NG⋆(ux) ∩ Un 6= ; or NG⋆(uy) ∩ Un 6= ;, say the former; notice that not both ux and uy can have a neighbor in Un by the construction of G⋆. Then dG⋆(ux ,uk,ak ) > dG⋆(uy ,uk,ak ) for some k 6= i (1 ≤ k ≤ n− 1) satisfying NG⋆(uy)∩Uk 6= ;. So, (2) holds for each case. Subcase 1.2: i = n. Since dG⋆(ux ,uk,ak ) < dG⋆(uy ,uk,ak ) for some k (1 ≤ k ≤ n− 1) satisfying NG⋆(ux )∩Uk 6= ;, (2) holds. Case 2: ux ∈ Ui and uy ∈ U j for i 6= j (1≤ i, j ≤ n). We consider two subcases. Subcase 2.1: 1≤ i, j ≤ n− 1. If ui,ai uy 6∈ E(G⋆), then dG⋆(ux ,ui,ai ) = 1 and dG⋆(uy ,ui,ai ) ≥ 2, and thus (2) holds. So, we consider ui,ai uy ∈ E(G⋆); notice that dG⋆(ux ,ui,ai ) = 1= dG⋆(uy ,ui,ai ). But dG⋆(uy ,u j,a j ) = 1 and dG⋆(ux ,u j,a j ) ≥ 2, and thus (2) holds. Subcase 2.2: 1 ≤ i ≤ n− 1 and j = n, or 1 ≤ j ≤ n − 1 and i = n, say the former. If NG⋆(uy) ∩ Ui = ;, then dG⋆(ux ,ui,ai ) = 1 < dG⋆(uy ,ui,ai ), and thus (2) holds. So, suppose that NG⋆(uy) ∩Ui 6= ;. If uyui,ai 6∈ E(G⋆), then dG⋆(ux ,ui,ai ) = 1 and dG⋆(uy ,ui,ai ) = 2, and thus (2) holds. If uyui,ai ∈ E(G⋆), then dG⋆(ux ,ui,ai ) = 1= dG⋆(uy ,ui,ai ); further, one can easily verify that codeS(ux) = codeS(uy) implies that vi and vn are adjacent twins in G. If every pair of vertices in G are twins in G, then G ∼= Kn, and dim(K⋆n) = n − 1 (see Theorem 12). D. Klein, E. Yi / Eur. J. Pure Appl. Math, 5 (2012), 302-316 307 In each case, S forms a resolving set for G⋆ with |S| = n−1. So, the upper bound of (1) follows. For the sharpness of the upper bound, take G = Kn; then dim(G⋆) = n−1 by Theorem 12. The authors of [5] characterized connected graphs of order n with metric dimension 1, n− 2, and n− 1, respectively. Theorem 7. [5] Let G be a connected graph of order n≥ 2. Then (a) dim(G) = 1 if and only if G = Pn, (b) dim(G) = n− 1 if and only if G = Kn, (c) for n≥ 4, dim(G) = n− 2 if and only if G = Ks,t (s, t ≥ 1), G = Ks+ K t (s ≥ 1, t ≥ 2), or G = Ks+(K1∪Kt) (s, t ≥ 1); here, A+B denotes the graph obtained from the disjoint union of graphs A and B by joining every vertex of A with every vertex of B, and H denotes the graph whose vertex set is V (H) and uv ∈ E(H) if and only if uv 6∈ E(H) for u, v ∈ V (H). Next, we characterize graphs G satisfying dim(G⋆) = 1 and dim(G⋆) = |V (G)| − 1, respec- tively. Theorem 8. Let G be a connected graph of order n≥ 2. Then (a) dim(G⋆) = 1 if and only if G = Pn, (b) for n≥ 4, dim(G⋆) = n− 1 if and only if G = Kn. Proof. Let G be a connected graph of order n≥ 2. (a) (⇐=) If G = Pn, then G⋆ = P2n−2, and thus dim(G⋆) = 1 by (a) of Theorem 7. (=⇒) Suppose dim(G⋆) = 1. Then ∆(G) ≤ 2; otherwise, G⋆ contains K3 as a subgraph, and thus dim(G⋆) ≥ 2 by (a) of Theorem 7. Since ∆(G) ≤ 2, G is either a path or a cycle. Since C⋆n ∼= C2n and dim(C⋆n) = 2, G ∼= Pn. (b) (⇐=) See Theorem 12. (=⇒) Suppose that G 6= Kn for n ≥ 4, and let V (G) = {v1, v2, . . . , vn} with degG(vi) = di (1 ≤ i ≤ n). Without loss of generality, assume that v1v2 6∈ E(G). Following the con- struction of G⋆ from G, let each vertex vi be replaced by K(vi) ∼= Kdi ; here, we denote by Ui the vertex set V (K(vi) ) = {ui,1,ui,2, . . . ,ui,di } ⊆ V (G⋆) for each i (1 ≤ i ≤ n). Let S = {u2,a2 ,u3,a3 , . . . ,un−1,an−1 } with |S|= n−2 such that |S∩Ui| = 1 for each i (2≤ i ≤ n−1) and that no two vertices in S are adjacent in G⋆. We will show that S is a resolving set for G⋆. It suffices to show that, for any two vertices ux ,uy ∈ V (G⋆)−S, dG⋆(ux ,ui,ai ) 6= dG⋆(uy ,ui,ai ) for some ui,ai ∈ S. As in the proof of Theorem 6, S forms a resolving set for 〈∪n−1 i=1 mathcalUi 〉 ⊆ G⋆ and 〈∪n i=2 Ui〉 ⊆ G⋆. So, it remains to show that, for ux ∈ U1 and uy ∈ Un, dG⋆(ux ,ui,ai ) 6= dG⋆(uy ,ui,ai ) for some ui,ai ∈ S. If uxui,ai ∈ E(G⋆) or uy ui,ai ∈ E(G⋆) for some i (2≤ i ≤ n− 1), say the former, then dG⋆(ux ,ui,ai ) = 1< dG⋆(uy ,ui,ai ). If uxui,ai 6∈ E(G⋆) and uyui,ai 6∈ E(G⋆) for each i (2≤ i ≤ n− 1), then codeS(ux) = codeS(uy) implies that v1 and vn are non-adjacent twins in G. If there exist a pair of vertices in G that are not non-adjacent twin D. Klein, E. Yi / Eur. J. Pure Appl. Math, 5 (2012), 302-316 308 in G, we are done. Otherwise, every pair of vertices must be non-adjacent twins in G, but this is impossible: if w1 and w2 are non-adjacent twins in G satisfying wk ∈ NG(w1)∩NG(w2), then w1wk ∈ E(G). So, S is a resolving set for G⋆ with |S| = n− 2, and hence dim(G⋆) ≤ n− 2. 4. Metric Dimension of para-Line Graphs for Trees, Complete Graphs, Complete Bi-partite Graphs, Wheel Graphs, and Bouquet of Circles In this section, we determine the metric dimension of some classes of para-line graphs. First, we determine the metric dimension of T ⋆ for a tree T that is not a path. The following definitions are stated in [5]. Fix a graph G. A vertex of degree at least three is called a major vertex. An end-vertex u is called a terminal vertex of a major vertex v if d(u, v) < d(u, w) for every other major vertex w. The terminal degree of a major vertex v is the number of terminal vertices of v. A major vertex v is an exterior major vertex if it has positive terminal degree. Let σ(G) denote the sum of terminal degrees of all major vertices of G, and let ex(G) denote the number of exterior major vertices of G. Theorem 9. [5, 17, 19] If T is a tree that is not a path, then dim(T ) = σ(T )− ex(T ). Theorem 10. [10] If T is a tree that is not a path, then dim(L(T )) = σ(T )− ex(T ). As an immediate consequence of Theorem 10, we have the following Corollary 1. If T is a tree that is not a path, then dim(T ⋆) = σ(T )− ex(T ). Second, we determine the metric dimension of K⋆n for the complete graph Kn of order n≥ 2. We first recall the metric dimension of L(Kn). Theorem 11. [1] For the complete graph Kn of order n≥ 6, dim(L(Kn)) = ⌈ 2n 3 ⌉. Theorem 12. If Kn is the complete graph of order n≥ 2, then dim(K⋆n) = n− 1. Proof. Let G = Kn for n ≥ 2. If n = 2, then G ∼= P2; thus dim(G⋆) = 1. If n = 3, then G ∼= C3; thus dim(G⋆) = 2. If n = 4, then dim(G⋆) ≥ 3 by Theorem 3, since diam(G⋆) = 3 and |V (G⋆)| = 12; thus dim(G⋆) = 3 by Theorem 6. So, let n ≥ 5. Let V (G) = {v1, v2, . . . , vn} with degG(vi) = n−1 (1≤ i ≤ n). Following the construction of G⋆ from G, let each vertex vi be replaced by K(vi ) ∼= Kn−1; here, we denote by Ui the vertex set V (K(vi) ) = {ui,1,ui,2, . . . ,ui,n} − {ui,i} ⊆ V (G⋆) for each i (1 ≤ i ≤ n). See Figure 2 for the labelings of Kn and K⋆n; here, the solid vertices form a minimum resolving set for K6 and K⋆ 6 , respectively. Let S be a resolving set for K⋆n. By Theorem 6, dim(K⋆n) ≤ n− 1†. It remains to show that dim(K⋆n) ≥ n− 1. Assume, to the contrary, that dim(K⋆n) ≤ n− 2; then |S| ≤ n− 2 and there are two or more Ui ’s satisfying S ∩Ui = ;. We may assume that |S ∩U1| ≥ |S ∩U2| ≥ . . . ≥ |S ∩Un−2| ≥ 0 and that S ∩Ui = ; for i ∈ {n− 1, n}, by relabeling if necessary. If |S ∩ U1| ≥ n − 3, then one can easily see that S fails to resolve K⋆n. So, †One can readily check that S = {ui,i+1 | 1 ≤ i l en− 1} is a resolving set for K⋆ n D. Klein, E. Yi / Eur. J. Pure Appl. Math, 5 (2012), 302-316 309 |S ∩Ui| ≤ n− 4 each i (1 ≤ i ≤ n), and we may assume that S ∩ {u1,n−2,u1,n−1,u1,n} = ; by relabeling if necessary. Then codeS(u1,n−1) = codeS(u1,n), contradicting the assumption that S is a resolving set for K⋆n. Thus, any resolving set S for K⋆n must satisfy |S| ≥ n−1. Therefore, dim(K⋆n) = n− 1. (a) K6 (b) K⋆ 6 Figure 2: Labeling of Kn and K⋆n Third, we consider the metric dimension of K⋆s,t for the complete bi-partite graph Ks,t of order s+ t ≥ 4, where s, t ≥ 2. We recall the metric dimension of L(Ks,t) first. Theorem 13. [4] Let Ks,t be the complete bi-partite graph, where t ≥ s ≥ 1. Then dim(L(Ks,t)) = ( ⌊2(s+t−1) 3 ⌋ if s ≤ t ≤ 2s− 1, t − 1 if t ≥ 2s. Since K2,2 ∼= C4 and C⋆4 ∼= C8, dim(K⋆2,2) = 2. So, we consider for s, t ≥ 2 excluding s = t = 2. Theorem 14. Let Ks,t be the complete bi-partite graph of order s+ t ≥ 4. For s, t ≥ 2, excluding s = t = 2, dim(K⋆s,t)≤ s+ t − 3. Proof. For t ≥ s ≥ 2 excluding s = t = 2, let G = Ks,t . Let V and W be the bi-partite sets of G, where V = {v1, v2, . . . , vs} and W = {w1, w2, . . . , wt}. Following the construction of G⋆ from G, let each vertex vi (w j , respectively) be replaced by K(vi) ∼= Kt (K(w j) ∼= Ks, respectively); here, we denote by Ui the vertex set V (K(vi) ) = {ui,1,ui,2, . . . ,ui,t} ⊆ V (G⋆) and we denote by U ′j the vertex set V (K(w j) ) = {u′j,1,u′j,2, . . . ,u′j,s} ⊆ V (G⋆) for each i, j (1 ≤ i ≤ s and 1≤ j ≤ t). Let ui,ku′ k,i ∈ E(G) for ui,k ∈ Ui and u′ k,i ∈ U ′ k , where 1≤ i ≤ s and 1≤ k ≤ t. See Figure 3 for the labelings of Ks,t and K⋆s,t; here, the solid vertices form a resolving set for K3,4 and K⋆3,4, respectively. We will show that S = {u1,a | 1 ≤ a ≤ t − 1} ∪ (∪s−1 b=2 {ub,1}) forms a resolving set for K⋆s,t with |S| = s+ t − 3, and thus dim(K⋆s,t) ≤ s+ t − 3. It suffices to show that, for any two vertices ux ,uy ∈ V (G⋆)− S, dG⋆(ux , z) 6= dG⋆(uy , z) for some z ∈ S. (3) D. Klein, E. Yi / Eur. J. Pure Appl. Math, 5 (2012), 302-316 310 (a) K3,4 (b) K⋆ 3,4 Figure 3: Labeling of Ks,t and K⋆s,t We consider three cases. Case 1: ux ∈ Ui and uy ∈ U j, where 1≤ i, j ≤ s. We consider two subcases. Subcase 1.1: i 6= j. If i = 1 or j = 1, say the former, then 1= dG⋆(ux ,u1,1)< dG⋆(uy ,u1,1). If i = s or j = s, say the former, then dG⋆(uy ,u j,1) = 1< dG⋆(ux ,u j,1). If 2≤ i, j ≤ s− 1, then 1= dG⋆(ux ,ui,1)< dG⋆(uy ,ui,1). So, (3) holds in each case. Subcase 1.2: i = j. Notice that 2 ≤ i ≤ s in this case. Write ux = ui,α and uy = ui,β for α 6= β (1 ≤ α,β ≤ t); then dG⋆(ui,α,u1,α) = 3 and dG⋆(ui,β ,u1,α) = 4 for each α (1≤ α ≤ t − 1), and thus (3) holds. Case 2: ux ∈ Ui and uy ∈ U ′ j , where 1≤ i ≤ s and 1≤ j ≤ t. If i = 1, then 1 = dG⋆(ux ,u1,1) < dG⋆(uy ,u1,1) or 1 = dG⋆(ux ,u1,2) < dG⋆(uy ,u1,2). If i = s, then 3 ≤ dG⋆(ux ,u1,1) ≤ 4 and 1 ≤ dG⋆(uy ,u1,1) ≤ 3; for dG⋆(ux ,u1,1) = 3 (i.e., ux = us,1), dG⋆(ux ,u1,2) = 4 > dG⋆(uy ,u1,2). If 2 ≤ i ≤ s − 1, then dG⋆(ux ,ui,1) = 1 < dG⋆(uy ,ui,1) for uy 6= u′1,i; dG⋆(ux ,u1,1) = 4> dG⋆(uy ,u1,1) for uy = u′1,i . So, (3) holds in each case. Case 3: ux ∈ U ′ i and uy ∈ U ′ j , where 1≤ i, j ≤ t. We consider two subcases. Subcase 3.1: i 6= j. If ux ∈ NG⋆(S) or uy ∈ NG⋆(S), say the former, then dG⋆(ux , z) = 1< dG⋆(ux , z) for z ∈ S. So, suppose that ux 6∈ NG⋆(S) and uy 6∈ NG⋆(S); we write ux = u′ i,α and uy = u′ j,β , where 2 ≤ α,β ≤ s. If i = 1 or j = 1, say the former, then ux = u′1,s: dG⋆(u ′ 1,s,u1,1) = 2 and dG⋆(u ′ j,β ,u1,1) = 3. So, we consider 2 ≤ i, j ≤ t. First, suppose dG⋆(u ′ i,α, z) = 2 for some z ∈ S. Then u′i,1 ∈ N(S) (i.e., z = u1,i for i 6= t) or z = uα,1, where 2 ≤ i,α ≤ s− 1: if z = u1,i , then dG⋆(u ′ j,β ,u1,i) = 3; if z = uα,1, then dG⋆(u ′ j,β ,uα,1) = 2 implies α = β , but dG⋆(u ′ i,α,u1,i) = 2 and dG⋆(u ′ j,α,u1,i) = 3. Second, suppose dG⋆(u ′ i, alpha , z) = 3 for all z ∈ S. Then u′i,α = u′t,s, the unique vertex of ∪t j=1 U ′j with 3 in each entry of its code. So, (3) holds in each case. D. Klein, E. Yi / Eur. J. Pure Appl. Math, 5 (2012), 302-316 311 Subcase 3.2: i = j. If ux ∈ NG⋆(S) or uy ∈ NG⋆(S), say the former, then dG⋆(ux , z) = 1< dG⋆(ux , z) for z ∈ S. So, suppose that ux 6∈ NG⋆(S) and uy 6∈ NG⋆(S); notice that 2 ≤ j ≤ t in this case. We write ux = u′j,α and uy = u′ j,β . Then dG⋆(u ′ j,α,uα,1) = 2 and dG⋆(u ′ j,β ,uα,1) = 3 and for α 6= β , where 1≤ α≤ s−1 and 1≤ β ≤ s. In each case, (3) holds. Next, we determine the metric dimension of W ⋆ 1,n for the wheel graph W1,n = K1 + Cn, where n≥ 3. We recall the metric dimension of the wheel graph and its line graph. Theorem 15. [3, 24] For n≥ 3, let W1,n = K1+ Cn be the wheel graph on n+ 1 vertices. Then dim(W1,n) = ( 3 if n= 3 or n= 6, ⌊2n+2 5 ⌋ otherwise. Theorem 16. [8] For n≥ 3, dim(L(W1,n)) =    3 if n= 3,4, 4 if n= 5, n− ⌈ n 3 ⌉ otherwise. Theorem 17. For n≥ 3, dim(W ⋆ 1,n) = ( 3 if n= 3, n− 1 if n≥ 4. Proof. For n ≥ 3, let G = W1,n, and let V (G) = {v0, v1, v2, . . . , vn} with degG(v0) = n. Following the construction of G⋆ from G, let the vertex v0 be replaced by K(v0) ∼= Kn and let each vertex vi (1 ≤ i ≤ n) be replaced by K(vi) ∼= K3; here, we denote by U0 the vertex set V (K(v0) ) = {u0,1,u0,2, . . . ,u0,n} ⊆ V (G⋆) and we denote by Ui (1 ≤ i ≤ n) the vertex set V (K(vi) ) = {ui,0,ui,i−1,ui,i+1} ⊆ V (G⋆), where the subscript of u is taken modulo n if the subscript is bigger than n except when i = 1 (we take u1,n in place of ui,i−1 if i = 1). See Figure 4 for the labelings of W1,n and W ⋆ 1,n; here, the solid vertices form a minimum resolving set for W1,6, L(W1,6), and W ⋆ 1,6 , respectively. If n = 3, noting that W1,3 ∼= K4, dim(W ⋆ 1,3) = 3 by Theorem 12. So, we consider n ≥ 4; let S be a resolving set for W ⋆ 1,n. We make the following Claim: For n≥ 4, there exists at most one i such that S∩(Ui∪{u0,i}) 6= ;, where 1≤ i ≤ n. Proof of Claim. Assume, to the contrary, that S ∩ (Ux ∪ {u0,x}) = ; = S ∩ (Uy ∪ {u0,y}) for two distinct x , y, where 1 ≤ x , y ≤ n. Then codeS(u0,x) = codeS(u0,y), contradicting the assumption that S is a resolving set for W ⋆ 1,n. So, there exists at most one i such that S ∩ (Ui ∪ {u0,i}) 6= ;. D. Klein, E. Yi / Eur. J. Pure Appl. Math, 5 (2012), 302-316 312 (a) W1,6 (b) L(W1,6) (c) W ⋆ 1,6 Figure 4: Labelings of W1,n and W ⋆ 1,n; dim(W1,6) = 3,dim(L(W1,6)) = 4,dim(W ⋆ 1,6 ) = 5 By Claim, |S| ≥ n − 1, and thus dim(W ⋆ 1,n) ≥ n − 1 for n ≥ 4. On the other hand, dim(W ⋆ 1,n)≤ n− 1 by (b) of Theorem 8‡. Therefore, dim(W ⋆ 1,n) = n− 1 for n≥ 4. It is well known that dim(Cn) = 2 for n≥ 3. Let Bn = (k1, k2, . . . , kn) be a bouquet of n≥ 2 circles C1, C2, . . ., Cn, with a cut-vertex, where ki is the number of vertices of C i (1≤ i ≤ n). See Figure 5 for B4 = (3,4,5,6) and its line graph. We recall the metric dimension of a bouquet of circles and its line graph. (a) B4 = (3, 4, 5, 6) (b) L(B4) Figure 5: A bouquet of four circles B4 = (3,4,5,6) and its line graph Theorem 18. [16] Let Bn = (k1, k2, . . . , kn) be a bouquet of n≥ 2 circles with a cut-vertex. If x is the number of even cycles of Bn, then dim(Bn) = ( n if x = 0 n+ x − 1 if x ≥ 1. Theorem 19. [8] Let Bn = (k1, k2, . . . , kn) be a bouquet of n≥ 2 circles with a cut-vertex. Then dim(L(Bn)) = 2n− 1. As an immediate consequence of Theorem 19, we have the following ‡One can readily check that S = {ui,i+1 | 1 ≤ i ≤ n− 1} forms a resolving set for W ⋆ 1,n . D. Klein, E. Yi / Eur. J. Pure Appl. Math, 5 (2012), 302-316 313 Corollary 2. Let Bn = (k1, k2, . . . , kn) be a bouquet of n≥ 2 circles with a cut-vertex. Then dim(B⋆n) = 2n− 1. 5. Metric Dimension of Graphs, Line Graphs, and para-Line Graphs In this section, we compare metric dimension of a connected graph G, its line graph L(G), and its para-line graph G⋆: we give an example of a graph G such that max{dim(G), dim(L(G)), dim(G⋆)} equals dim(G), dim(L(G)), and dim(G⋆), respectively. Remark 1. There exists a graph G with max{dim(G), dim(L(G)), dim(G⋆)} = dim(G). If G = Ks,2s for s ≥ 2, then dim(G) = 3s− 2, dim(L(G)) = 2s− 1, and dim(G⋆) ≤ 3s− 3; further, notice that dim(G)− dim(L(G)) can be arbitrarily large. Remark 2. There exists a graph G with max{dim(G), dim(L(G)), dim(G⋆)} = dim(L(G)). If G = Bn, a bouquet of n≥ 2 circles, containing no even cycles, then dim(G) = n and dim(L(G)) = 2n−1= dim(G⋆); further, notice that dim(L(G))−dim(G) and dim(G⋆)−dim(G) can be arbitrarily large. Remark 3. There exists a graph G with max{dim(G), dim(L(G)), dim(G⋆)} = dim(G⋆). If G = W1,n for n ≥ 7, then dim(G) = ⌊2n+2 5 ⌋ and dim(L(G)) = n− ⌈ n 3 ⌉, and dim(G⋆) = n− 1; further, notice that dim(G⋆)− dim(G) and dim(G⋆)− dim(L(G)) can be arbitrarily large. 6. Summary and Open Problems In Table 1, we summarize metric dimension of some graphs G, the line graphs L(G), and the para-line graphs G⋆. Here, x denotes the number of even cycles of a bouquet of circles Bn; for the complete bi-partite graphs Ks,t we consider s, t ≥ 2 excluding s = t = 2. We conclude this paper with some open problems. Problems. For a connected graph G, let L(G) be the line graph of G and let G⋆ be the para-line graph of G. Q1. [10] Can we characterize graphs G such that dim(G) = dim(L(G)) ? Q2. Can we characterize graphs G such that dim(G) = dim(G⋆) ? Q3. Can we characterize graphs G such that dim(L(G)) = dim(G⋆) ? REFERENCES 314 Table 1: Metric Dimension of Some Graphs G, Line Graphs L(G), and para-Line Graphs G⋆. G dim(G) dim(L(G)) dim(G⋆) Pn, n≥ 2 1 1 1 Cn, n≥ 3 2 2 2 T ( 6= Pn) σ(T )− ex(T ) σ(T )− ex(T ) σ(T )− ex(T ) Kn, n≥ 6 n− 1 ⌈2n 3 ⌉ n− 1 Ks,t s+ t − 2 ( ⌊2(s+t−1) 3 ⌋ if s ≤ t ≤ 2s t − 1 if t ≥ 2s ≤ s+ t − 3 W1,n, n≥ 3 ( 3 if n= 3,6 ⌊2n+2 5 ⌋ otherwise    3 if n= 3,4 4 if n= 5 n− ⌈ n 3 ⌉ if n≥ 6 ( 3 if n= 3 n− 1 if n≥ 4 Bn, n≥ 2 ( n if x = 0 n+ x − 1 if x ≥ 1 2n− 1 2n− 1 ACKNOWLEDGEMENTS The first author is supported by the Welch Foundation of Hous- ton, Texas, grant BD-0894. The authors thank Cong X. Kang for his helpful comments and suggestions, especially on Theorem 6. References [1] R.F. Bailey and P.J. Cameron. Base size, metric dimension and other invariants of groups and graphs. Bulletin of the London Mathematical Society. 43(2), 209-242. 2011. [2] L.W. Beineke. Characterizations of Derived Graphs. Journal of Combinatorial Theory. 9, 129-135. 1970. [3] P.S. Buczkowski, G. Chartrand, C. Poisson, and P. Zhang. On k-dimensional graphs and their bases. Periodica Mathematica Hungarica. 46(1), 9-15. 2003. [4] J. Cáceres, C. Hernado, M. Mora, I.M. Pelayo, M.L. Puertas, C. Seara, and D.R. Wood. On the Metric Dimension of Cartesian Products of Graphs. SIAM Journal on Discrete Mathematics. 21, Issue 2, 423-441. 2007. [5] G. Chartrand, L. Eroh, M.A. Johnson, O.R. Oellermann. Resolvability in graphs and the metric dimension of a graph. Discrete Applied Mathematics. 105, 99-113. 2000. [6] G. Chartrand and P. Zhang. Introduction to Graph Theory. McGraw-Hill, Kalamazoo, MI. 2004. [7] G. Chartrand and P. Zhang. The theory and applications of resolvability in graphs. A Survey. Congressus Numerantium. 160, 47-68. 2003. REFERENCES 315 [8] L. Eroh, C.X. Kang, and E. Yi. A Comparison between the Metric Dimension and Zero Forcing Number of Line Graphs. arXiv:1207.6127v1. [9] L. Eroh, C.X. Kang, and E. Yi. On Metric Dimension of Graphs and Their Complements. Journal of Combinatorial Mathematics and Combinatorial Computing. to appear. [10] M. Feng, M. Xu, and K. Wang. On the metric dimension of line graphs. arXiv:1107.4140v1. [11] K. Fukui, H. Kato, and T. Yonezawa. A New Quantum-mechanical Reactivity Index for Saturated Compounds. Bulletin of the Chemical Society of Japan. 34, 1111-1115. 1961. [12] M.R. Garey and D.S. Johnson. Computers and Intractability: A Guide to the Theory of NP-Completeness. Freeman, New York. 1979. [13] F. Harary and R.A. Melter. On the metric dimension of a graph. Ars Combinatoria. 2, 191-195. 1976. [14] C. Hernando, M. Mora, I.M. Pelayo, C. Seara, and D.R. Wood. Extremal Graph Theory for Metric Dimension and Diameter. Electronic Journal of Combinatorics. 17 (1), #R30. 2010. [15] Y. Higuchi and T. Shirai. Some Spectral and Geometric Properties for Infinite Graphs. Discrete geometric analysis, Contemporary Mathematics. 347, 29-56. American Mathe- matical Society, Providence, RI. 2004. [16] H. Iswadi, E.T. Baskoro, A.N.M. Salman, and R. Simanjuntak. The Metric Dimension of Amalgamation of Cycles. Far East Journal of Mathematical Sciences. 41, Number 1, 19-31. 2010. [17] S. Khuller, B. Raghavachari, and A. Rosenfeld. Landmarks in Graphs. Discrete Applied Mathematics. 70, 217-229. 1996. [18] J. Krausz. Demonstration nouvelle d’une Théorème de Whitney sur les Réseaux. Mat. Fiz. Lapok 50, 75-85. 1943. [19] C. Poisson and P. Zhang. The Metric Dimension of Unicyclic Graphs. Journal of Combi- natorial Mathematics and Combinatorial Computing. 40, 17-32. 2002. [20] J.A. Pople and D.P. Santry. A molecular orbital theory of hydrocarbons. Molecular Physics. 7 Issue 3, 269-286. 1964. [21] P.S. Ranjini, V. Lokesha, and I.N. Cangül. On the Zagreb indices of the line graphs of the subdivision graphs. Applied Mathematics and Computation. 218, Issue 3, 699-702. 2011. [22] C. Sandorfy. LCAO MO Calculations on Saturated Hydrocarbons and Their Substituted Derivatives. Canadian Journal of Chemistry. 33, 1337-1351. 1955. REFERENCES 316 [23] A. Sebö and E. Tannier. On metric generators of graphs. Mathematics of Operations Re- search. 29, 383-393. 2004. [24] B. Shanmukha, B. Sooryanarayana, and K.S. Harinath. Metric dimension of wheels. Far East Journal of Applied Mathematics. 8 (3), 217-229. 2002. [25] T. Shiraithe. Spectrum of Infinite Regular Line Graphs. Transactions of the American Mathematical Society. 352, Number 1, 115-132. 1999. [26] P.J. Slater. Dominating and reference sets in a graph. Journal of Mathematical and Phys- ical Sciences. 22, 445-455. 1998. [27] P.J. Slater. Leaves of trees. Congressus Numerantium. 14, 549-559. 1975. [28] A. van Rooij and H. Wilf. The Interchange Graph of a Finite Graph. Acta Mathematica Academiae Scientiarum Hungaricae. 16, 263-269. 1965. [29] H. Whitney. Congruent Graphs and the Connectivity of Graphs. American Journal of Mathematics. 54, 150-168. 1932.