Premium
The n ‐ordered graphs: A new graph class
Author(s) -
Bonato Anthony,
Janssen Jeannette,
Wang Changping
Publication year - 2009
Publication title -
journal of graph theory
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.164
H-Index - 54
eISSN - 1097-0118
pISSN - 0364-9024
DOI - 10.1002/jgt.20352
Subject(s) - combinatorics , mathematics , discrete mathematics , countable set , indifference graph , chordal graph , pathwidth , 1 planar graph , line graph , graph
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