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

Books Problems Set Theory Combinatorics Extremal Probl/Ramsey Th.
Graph Theory Add.Number Theory Mult.Number Theory Analysis Geometry
Probabability Personalia About Paul Erdös Publication Year Home Page