Graph Dilation

Let the vertices of a graph G be numbered with distinct integers 1 to |G|. Then the dilation of G is the maximum (absolute) difference between integers assigned to adjacent vertices. Equivalently, it is the maximum value of |i-j| over all nonzero elements of the adjacency matrix (a_(ij)).

See also

Graph Bandwidth

Explore with Wolfram|Alpha


West, D. B. Introduction to Graph Theory, 2nd ed. Englewood Cliffs, NJ: Prentice-Hall, p. 390, 2000.

Cite this as:

Weisstein, Eric W. "Graph Dilation." From MathWorld--A Wolfram Web Resource.