Constructing universal graphs for induced-hereditary graph properties |
| |
Authors: | Izak Broere Johannes Heidema Peter Mihók |
| |
Affiliation: | 192. Department of Mathematics and Applied Mathematics, University of Pretoria, 0028, Pretoria, South Africa 292. Department of Mathematical Sciences, University of South Africa, Pretoria, South Africa 392. Mathematical Institute, Slovak Academy of Science, Gre?ákova 6, SK-040 01, Ko?ice, Slovakia
|
| |
Abstract: | Rado constructed a (simple) denumerable graph R with the positive integers as vertex set with the following edges: For given m and n with m < n, m is adjacent to n if n has a 1 in the m’th position of its binary expansion. It is well known that R is a universal graph in the set I of all countable graphs (since every graph in I is isomorphic to an induced subgraph of R). In this paper we describe a general recursive construction which proves the existence of a countable universal graph for any induced-hereditary property of countable general graphs. A general construction of a universal graph for the set of finite graphs in a product of properties of graphs is also presented. The paper is concluded by a comparison between the two types of construction of universal graphs. |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|