On the locatic number of graphs

Abstract

A vertex v of a connected graph G distinguishes a pair u, w of vertices of G if d(v, u)≠d(v, w), where d(·,·) denotes the length of a shortest path between two vertices in G. A k-partition Π={S ₁, S ₂, …, S _k } of the vertex set of G is said to be a locatic partition if for every pair of distinct vertices v and w of G, there exists a vertex s∈S _i for all 1≤i≤k that distinguishes v and w. The cardinality of a largest locatic partition is called the locatic number of G. In this paper, we study the locatic number of paths, cycles and characterize all the connected graphs of order n having locatic number n, n−1 and n−2. Some realizable results are also given in this paper.

Keywords:

• locating set
• location number
• locatic number
• diameter

2010 AMS Subject Classification :

• 05C12

Acknowledgements

This research of the authors was partially supported by the Higher Education Commission of Pakistan (Grant No. 17-5-3(Ps3-257) HEC/Sch/2006).