(untitled) (European Journal of Pure and Applied Mathematics, 2012)
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 (G) of a graph G is the minimum number of vertices such that all vertices are uniquely determined by their 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 _2 Δ(G) ceil Â (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 {(G), (L(G)), (G^)} equals (G), (L(G)), and (G^), respectively. We conclude this paper with some open problems.