REGULARIZING IRREGULAR GRAPHS

A graph is highly irregular if it is connected and the neighbors of ea ch 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 se t of vertices with minimum eccentricity. Graph G is self-centered if a ll the vertices of G are in the center. Except for two trivial cases, highly irregular graphs are never self-centered. In this paper, we stu dy the problem of embedding a highly irregular graph G as an induced s ubgraph in a self-centered graph H so that H is regular with the same maximum degree as G and has the smallest possible order.