|
|||||
|
|
Some remarks on universal graphs |
|
| Authors: | Reinhard Diestel Rudolf Halin Walter Vogler |
| Affiliation: | 1. Department of Pure Mathematics, University of Cambridge, 16 Mill Lane, CB2 1SB, Cambridge, England 2. Mathematisches Seminar, Universit?t Hamburg, Bundesstra?e 55, 2000, Hamburg 13, Germany 3. Fachbereich Informatik, Universit?t Hamburg, Rothenbaumchaussee 67/69, Germany |
| Abstract: | LetΓ be a class of countable graphs, and let ℱ(Γ) denote the class of all countable graphs that do not contain any subgraph isomorphic to a member ofΓ. Furthermore, letTΓ andHΓ denote the class of all subdivisions of graphs inΓ and the class of all graphs contracting to a member ofΓ, respectively. As the main result of this paper it is decided which of the classes ℱ(TK n ) and ℱ(HK n ),n≦ℵ0, contain a universal element. In fact, for ℱ(TK 4)=ℱ(HK 4) a strongly universal graph is constructed, whereas for 5≦n≦ℵ0 the classes ℱ(TK n ) and ℱ(HK n ) have no universal elements. Dedicated to Klaus Wagner on his 75th birthday |
| Keywords: | 05 C 75 |
| 本文献已被 SpringerLink 等数据库收录！ | |