2018/05/13 by Alejandro Estrada-Moreno, Estrada-Moreno, Alejandro
Mathematics · #Combinatorics (math.CO) #FOS: Mathematics #math.CO
paper · pdf · doi:10.48550/arxiv.1805.04966
19 pages, 3 figures
arxiv created 2018/09/16 · arxiv updated 2018/09/18
As a generalization of the concept of the partition dimension of a graph, this article introduces the notion of the k-partition dimension. Given a nontrivial connected graph G=(V,E), a partition Π of V is said to be a k-partition generator for G if any pair of different vertices u,v∈ V is distinguished by at least k vertex sets of Π, i.e., there exist at least k vertex sets S1,…,Sk∈Π such that d(u,Si)≠ d(v,Si) for every i∈\1,…,k\. A k-partition generator for G with minimum cardinality among all their k-partition generators is called a k-partition basis of G and its cardinality the k-partition dimension of G. A nontrivial connected graph G is k-partition dimensional if k is the largest integer such that G has a k-partition basis. We give a necessary and sufficient condition for a graph to be r-partition dimensional and we obtain several results on the k-partition dimension for k∈\1,…,r\.