Induced-Hereditary Graph Properties, Homogeneity, Extensibility and Universality

Izak Broere1, Johannes Heidema2
1Department of Mathematics and Applied Mathematics, University of Pretoria, Private Bag X20, Hatfield, Pretoria, 0028 South Africa
2Department of Mathematical Sciences, University of South Africa, P.O. Box 392, UNISA, Pretoria, 0003 South Africa

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 \( \mathcal{I} \) of all countable graphs (since every graph in \( \mathcal{I} \) is isomorphic to an induced subgraph of \( R \)) and that \( R \) can be characterized using this notion and that of being homogeneous and having the extension property. In this paper, we extend these notions to arbitrary induced-hereditary properties (of graphs), relate them to the construction of a universal graph for any such property, and obtain results which remind one of some characterizations of \( R \).