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 1, S 2, …, 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.
2010 AMS Subject Classification :
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).