×

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

MSC:

05C99 Graph theory

Citations:

Zbl 0699.00014