×

The \(n\)-ordered graphs: A new graph class. (English) Zbl 1177.05107

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
PDFBibTeX XMLCite
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.