On the k-index of graphs

Given a graph, join every two vertices which are at a distance greater than a fixed integer k (>1)by a new path of length k. Thus a graph transformation is defined. The least number of iterations of this transformation such that the last iteration does not change the graph, is called the k-index of the original graph. In the present paper the graphs are classified according to their k-indices. The results are applied in the study of so-called tied graphs.