The n‐ordered graphs: A new graph class |
| |
Authors: | Anthony Bonato Jeannette Janssen Changping Wang |
| |
Institution: | 1. Department of Mathematics Ryerson University, Toronto, Ontario, Canada M5B 2K3;2. Department of Mathematics and Statistics Dalhousie University, Halifax, Nova Scotia, Canada B3H 3J5 |
| |
Abstract: | 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 |
| |
Keywords: | n‐tree infinite random graph n‐e c web graph n‐ordered graph automorphism group |
|
|