Abstract

A graph G on n vertices is a tight distance graph if there exists a set D ⊆ {1, 2, ..., n - 1} such that V (G) = {0, 1, ..., n - 1} and i j ∈ E (G) if and only if | i - j | ∈ D. A characterization of the degree sequences of tight distance graphs is given. This characterization yields a fast method for recognizing and realizing degree sequences of tight distance graphs. © 2009 Elsevier B.V. All rights reserved.