Chartrand, Gary; Lesniak, Linda; Mynhardt, Christina M.; Oellermann, Ortrud R. Degree uniform graphs. (English) Zbl 0708.05059 Combinatorial mathematics, Proc. 3rd Int. Conf., New York/ NY (USA) 1985, Ann. N. Y. Acad. Sci. 555, 122-132 (1989). [For the entire collection see Zbl 0699.00014.] A graph is called n-degree uniform iff for each integer \(r\geq 0\) there are either n or 0 vertices with degree r. P. Erdős and J. C. Kelly [Am. Math. Mon. 70, 1074-1075 (1963)] determined the minimum order of such a graph. The authors show that if H is any graph, then there exists a degree uniform graph G such that H is an induced subgraph of G and G and H have the same degree set. The minimum order of such a graph G is investigated when H is a complete bipartite graph; solving this problem in the general case is left open. Reviewer: R.C.Entringer Cited in 1 Document MSC: 05C99 Graph theory Keywords:n-degree uniform; degree uniform graph Citations:Zbl 0699.00014 PDFBibTeX XML