Please use this identifier to cite or link to this item:

http://hdl.handle.net/10609/93187
Title: On the k-partition dimension of graphs
Author: Estrada Moreno, Alejandro
Others: Universitat Oberta de Catalunya (UOC)
Keywords: k-partition dimension
k-metric dimension
partition dimension
metric dimension
Issue Date: 16-Sep-2018
Publisher: Theoretical Computer Science
Citation: Estrada-Moreno, A. (2018). On the k-partition dimension of graphs. Theoretical Computer Science. doi: 10.1016/j.tcs.2018.09.022
Also see: http://arxiv.org/pdf/1805.04966
Abstract: 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 II of V is said to be a k-partition generator of G if any pair of different vertices u,v E V is distinguished by at least k vertex sets of II i.e., there exist at least k vertex sets S1,...,Sk E II such that d(u,Si) /= d(v,Si) for every i E {1,...,k}. A k-partition generator of 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 E {1,...,r}.
Language: English
URI: http://hdl.handle.net/10609/93187
ISSN: 0304-3975MIAR
Appears in Collections:Articles
Articles

Share:
Export:
Files in This Item:
File SizeFormat 
kpartition.pdf392.84 kBAdobe PDFView/Open

Items in repository are protected by copyright, with all rights reserved, unless otherwise indicated.