Name
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 |
Year | DOI | Venue |
|---|---|---|
2009 | 10.1002/jgt.v60:3 | Journal of Graph Theory |
Keywords | Field | DocType |
. n-tree,inflnite random graph,n-e.c.,web graph,n- ordered graph,automorphism group. the flrst and second authors gratefully acknowledge support from nserc and mitacs grants. 1 | Discrete mathematics,Topology,Random regular graph,Combinatorics,Partial k-tree,Cograph,Graph product,Symmetric graph,Pathwidth,Universal graph,Mathematics,Split graph | Journal |
Volume | Issue | ISSN |
60 | 3 | 0364-9024 |
Citations | PageRank | References |
1 | 0.43 | 4 |
Authors | ||
3 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Anthony Bonato | 1 | 156 | 18.57 |
| Jeannette Janssen | 2 | 295 | 32.23 |
| Changping Wang | 3 | 49 | 7.45 |