On metric dimension of permutation graphs Academic Article uri icon

abstract

  • 2012, Springer Science+Business Media New York. The metric dimension(Formula presented.) of a graph (Formula presented.) is the minimum number of vertices such that every vertex of (Formula presented.) is uniquely determined by its vector of distances to the set of chosen vertices. Let (Formula presented.) and (Formula presented.) be disjoint copies of a graph (Formula presented.), and let (Formula presented.) be a permutation. Then, a permutation graph(Formula presented.) has the vertex set (Formula presented.) and the edge set (Formula presented.). We show that (Formula presented.) for any connected graph (Formula presented.) of order (Formula presented.) at least (Formula presented.). We give examples showing that neither is there a function (Formula presented.) such that (Formula presented.) for all pairs (Formula presented.), nor is there a function (Formula presented.) such that (Formula presented.) for all pairs (Formula presented.). Further, we characterize permutation graphs (Formula presented.) satisfying (Formula presented.) when (Formula presented.) is a complete (Formula presented.)-partite graph, a cycle, or a path on (Formula presented.) vertices.

published proceedings

  • JOURNAL OF COMBINATORIAL OPTIMIZATION

author list (cited authors)

  • Hallaway, M., Kang, C. X., & Yi, E.

citation count

  • 6

complete list of authors

  • Hallaway, Michael||Kang, Cong X||Yi, Eunjeong

publication date

  • November 2014