  In 2006 Qian [J. Qian, Degree complete graphs; Discrete Mathematics 306
(2006), 533--537] introduced the concept of degree complete graphs for labeled
graphs. He also gave a characterization of these graphs in terms of two
forbidden subgraphs. Furthermore, he mentioned that the property of being
degree complete depends on the labeling of the graph. Related to this he stated
the problem to find a characterization of those (unlabeled) graphs for which
every labeled version is not degree complete. We say that a (unlabeled) graph
has a degree complete labeling, if there is a labeled version of the graph that
is degree complete. In this paper we give three characterizations of graphs
with degree complete labeling. These characterizations give us polynomial-time
procedures to recognize these graphs and find a degree complete labeling, if it
exists.
