Some universal directed labelled graphs
Abstract
Rado constructed an (undirected, unlabelled) 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 discuss universality for countable graphs which are at the same time directed and ¿-labelled for some positive integer k. We construct a universal directed k-labelled graph Lk which is characterised (up to isomorphism) by having the k-extension property, an analogue of the well-known extension property of the graph R. Lk is also characterised by the properties of being universal for directed k-labelled graphs and at the same time homogeneous.
