REGULARIZING IRREGULAR GRAPHS

A graph is highly irregular if it is connected and the neighbors of each vertex have distinct degrees. The eccentricity of a vertex v is the distance to the vertex farthest from v, and the center of G is the set of vertices with minimum eccentricity. Graph G is self-centered if all the vertices of G are in the center. Except for two trivial cases, highly irregular graphs are never self-centered. In this paper, we study the problem of embedding a highly irregular graph G as an induced subgraph in a self-centered graph H so that H is regular with the same maximum degree as G and has the smallest possible order.