Embedding of graphs in two-irregular graphs

A graph G on n vertices is called two-irregular if there are at most two ve rtices having the same degree for all possible degrees. We show that every graph with maximal degree at most n/8 - O(n(3/4)) can be embedded into a tw o-irregular graph. We obtain it as a corollary of an algorithmic proof of a result about packing the graphs. This improves the bound of O(n(1/4)) give n by Faudree et al. (C) 2001 John Wiley & Sons,Inc.