Zentralblatt MATH
Publications of (and about) Paul Erdös
Zbl.No: 397.05019
Autor: Erdös, Paul; Hechler, Stephen H.; Kainen, Paul
Title: On finite superuniversal graphs. (In English)
Source: Discrete Math. 24, 235-249 (1978).
Review: The author's abstract: ''Define a simple graph G to be k-superuniversal if for any k-element simple graph K and for any full subgraph H of K every full embedding of H into G can be extended to a full embedding of K into G. We prove that for each positive integer k there exist finite k-superuniversalgraphs, and we find upper and lower bounds on the smallest such graphs. We also find various bounds on the number of edges as well as the maximal and minimal valence of a k-superuniversal graph. We then generalize the notion of k-superuniversality to cover graphs with colorings and prove similar and related theorems.'' Note: The g(u) in Definition 3.1. should be f(v).
Reviewer: R.L.Hemminger
Classif.: * 05C10 Topological graph theory
05C15 Chromatic theory of graphs and maps
Keywords: finite superuniversal graphs
© European Mathematical Society & FIZ Karlsruhe & Springer-Verlag