Search

Let G = (V, E) be a connected simple graph and let M be a nonempty subset of V. The M-distance pattern of a vertex u in G is the set of all distances from u to the vertices in M. If the distance patterns of all vertices in V are distinct, then the set Mis a distance pattern distinguishing set of G. A graph G with 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. [ABSTRACT FROM AUTHOR]

Graceful labeling is one of the best known labeling methods of graphs. Despite the large number of papers published on the subject of graph labeling, there are few particular techniques to be used by researchers to gracefully label graphs. In this paper, first a new approach based on the mathematical programming technique is presented to model the graceful labeling problem. Then a "branching method" is developed to solve the problem for special classes of graphs. Computational results show the efficiency of the proposed algorithm for different classes of graphs. One of the interesting results of our model is in the class of trees. The largest tree known to be graceful has at most 27 vertices but our model can easily solve the graceful labeling for trees with 40 vertices. [ABSTRACT FROM AUTHOR]