On the metric dimension of line graphs

Details On the metric dimension of line graphs On the metric dimension of line graphs

2011-07-20

arxiv.org/abs/1107.4140v1

Mathematics

Combinatorics

7 pages

Scientific paper

Let $G$ be a (di)graph. A set $W$ of vertices in $G$ is a \emph{resolving set} of $G$ if every vertex $u$ of $G$ is uniquely determined by its vector of distances to all the vertices in $W$. The \emph{metric dimension} $\mu (G)$ of $G$ is the minimum cardinality of all the resolving sets of $G$. C\'aceres et al. \cite{Ca2} computed the metric dimension of the line graphs of complete bipartite graphs. Recently, Bailey and Cameron \cite{Ba} computed the metric dimension of the line graphs of complete graphs. In this paper we study the metric dimension of the line graph $L(G)$ of $G$. In particular, we show that $\mu(L(G))=|E(G)|-|V(G)|$ for a strongly connected digraph $G$ except for directed cycles, where $V(G)$ is the vertex set and $E(G)$ is the edge set of $G$. As a corollary, the metric dimension of de Brujin digraphs and Kautz digraphs is given. Moreover, we prove that $\lceil\log_2\Delta(G)\rceil\leq\mu(L(G))\leq |V(G)|-2$ for a simple connected graph $G$ with at least five vertices, where $\Delta(G)$ is the maximum degree of $G$. Finally, we obtain the metric dimension of the line graph of a tree in terms of its parameters.

Affiliated with

Also associated with

No associations

Rating

On the metric dimension of line graphs does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with On the metric dimension of line graphs, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and On the metric dimension of line graphs will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-687220