Bonato, Anthony; Janssen, Jeannette; Wang, Changping The \(n\)-ordered graphs: A new graph class. (English) Zbl 1177.05107 J. Graph Theory 60, No. 3, 204-218 (2009). Summary: 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)}\). MSC: 05C80 Random graphs (graph-theoretic aspects) 05C75 Structural characterization of families of graphs 91A43 Games involving graphs 91A46 Combinatorial games 05C25 Graphs and abstract algebra (groups, rings, fields, etc.) 20B25 Finite automorphism groups of algebraic, geometric, or combinatorial structures Keywords:\(n\)-tree; infinite random graph; web graph; \(n\)-ordered graph; automorphism group; countably infinite graphs; random process; folfing operation; automorphism group PDFBibTeX XMLCite \textit{A. Bonato} et al., J. Graph Theory 60, No. 3, 204--218 (2009; Zbl 1177.05107) Full Text: DOI References: [1] Bollobás, Random graphs (2001) · doi:10.1017/CBO9780511814068 [2] Bonato, A Course on the Web Graph (2008) · Zbl 1142.05072 · doi:10.1090/gsm/089 [3] Bonato, Infinite limits of copying models of the web graph, Internet Math 1 pp 193– (2004) · Zbl 1080.05084 · doi:10.1080/15427951.2004.10129087 [4] A. Brandstädt, V. B. Le, and J. P. Spinrad, Graph Classes, a Survey, SIAM Monographs on Discrete Mathematics and Applications, 1999. · Zbl 0919.05001 [5] Cameron, Algorithms and combinatorics 14 pp 333– (1997) [6] Cameron, European Congress of Mathematics I pp 267– (2001) · doi:10.1007/978-3-0348-8268-2_15 [7] Erdös, Asymmetric graphs, Acta Mathematica Academiae Scientiarum Hungaricae 14 pp 295– (1963) [8] Henson, A family of countable homogeneous graphs, Pacific J Math 38 pp 69– (1971) · Zbl 0204.24103 · doi:10.2140/pjm.1971.38.69 [9] J. Kleinberg and R. Kleinberg, Isomorphism and embedding problems for infinite limits of scale-free graphs. In: Proceedings of ACM-SIAM Symposium on Discrete Algorithms, 2005. · Zbl 1297.05170 [10] Nowakowski, Vertex-to-vertex pursuit in a graph, Discrete Math 43 pp 235– (1983) · Zbl 0508.05058 [11] Seidman, Network structure and minimum degree, Social Networks 5 pp 269– (1983) This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.