ON THE METRIC DIMENSION AND FRACTIONAL METRIC DIMENSION OF THE HIERARCHICAL PRODUCT OF GRAPHS

Applicable Analysis and Discrete Mathematics

article

Min Feng¹  Kaishun Wang¹ 

[1] School of Mathematical Sciences, Laboratory of Mathematics and Complex Systems, Beijing Normal University

关键词: Resolving set;    metric dimension;    resolving function;    fractional metric dimension;    hierarchical product;    binomial tree;   

DOI  :  10.2298/AADM130521009F

学科分类：社会科学、人文和艺术（综合）

来源: Univerzitet u Beogradu * Elektrotehnicki Fakultet / University of Belgrade, Faculty of Electrical Engineering

【 摘 要 】

A set of vertices W resolves a graph G if every vertex of G is uniquely determined by its vector of distances to the vertices in W. The metric dimensionfor G, denoted by dim(G), is the minimum cardinality of a resolving set of G.In order to study the metric dimension for the hierarchical product Gu22 ⊓Gu11of two rooted graphs Gu22 and Gu11, we first introduce a new parameter, therooted metric dimension rdim(Gu11) for a rooted graph Gu11. If G1 is not a pathwith an end-vertex u1, we show that dim(Gu22 ⊓ Gu11) = |V (G2)| · rdim(Gu11),where |V (G2)| is the order of G2. If G1 is a path with an end-vertex u1,we obtain some tight inequalities for dim(Gu22 ⊓ Gu11). Finally, we show thatsimilar results hold for the fractional metric dimension.

【 授权许可】

Unknown