On the Distance Pattern Distinguishing Number of a Graph

[摘要] LetG=(V,E)be a connected simple graph and letMbe a nonempty subset ofV. TheM-distance pattern of a vertexuinGis the set of all distances fromuto the vertices inM. If the distance patterns of all vertices inVare distinct, then the setMis a distance pattern distinguishing set ofG. A graphGwith a distance pattern distinguishing set is called a distance pattern distinguishing graph. Minimum number of vertices in a distance pattern distinguishing set is called distance pattern distinguishing number of a graph. This paper initiates a study on the problem of finding distance pattern distinguishing number of a graph and gives bounds for distance pattern distinguishing number. Further, this paper provides an algorithm to determine whether a graph is a distance pattern distinguishing graph or not and hence to determine the distance pattern distinguishing number of that graph.

[学科分类] 应用数学