The n ‐ordered graphs: A new graph class

For a positive integer n , we introduce the new graph class of n ‐ordered graphs, which generalize partial n ‐trees. Several characterizations are given for the finite n ‐ordered graphs, including one via a combinatorial game. We introduce new countably infinite graphs R (n) , which we name the infinite random n ‐ordered graphs. The graphs R (n) play a crucial role in the theory of n ‐ordered graphs, and are inspired by recent research on the web graph and the infinite random graph. We characterize R (n) as a limit of a random process, and via an adjacency property and a certain folding operation. We prove that the induced subgraphs of R (n) are exactly the countable n ‐ordered graphs. We show that all countable groups embed in the automorphism group of R (n) . © 2008 Wiley Periodicals, Inc. J Graph Theory 60: 204–218, 2009