Some family of distance pattern distinguishing graphs and realization results

Abstract

Let G = (V, E) be a connected graph and let M ⊆ V. For each u ∊ V the set f_M(u) = {d(u, v) : v ∊ M} is called the distance pattern of u with respect to the set M. If f_M is injective, then the set M is called a distance pattern distinguishing set (DPD-set) of G. If G admits a DPD-set, then G is called a DPD-graph. The minimum cardinality of a DPD-set in a DPD-graph G is the DPD-number of G and it is denoted by ρ(G). In this paper we present several fundamental results on these concepts and some family of graphs which admits DPD-set. We also investigate the relation between the DPD-number and the metric dimension of graphs and other graph theoretic parameters.

Subject Classification: (2015):

• 05C12

Keywords:

• Distance pattern distinguishing set
• DPD-graph and metric basis