The n-ordered graphs: A new graph class
The n-ordered graphs: A new graph class
复制标题
DOI：
10.1002/jgt.v60:3
复制
发表时间：
2009-03
影响因子：
0.9
通讯作者：
A. Bonato;J. Janssen;Changping Wang
中科院分区：
文献类型：
--
作者：
A. Bonato;J. Janssen;Changping Wang
对于正整数n，我们引入了一个新的图类n-序图，它推广了部分n-树。给出了有限n阶图的几个刻画，其中一个刻画是通过组合对策刻画的。引入了新的可数无限图R（n），我们称之为无限随机n-序图。图R（n）在n-序图理论中起着重要的作用，它的研究受到了网图和无限随机图的启发。我们将R（n）刻画为随机过程的极限，并通过一个邻接性和一个折叠运算刻画了R（n）的极限。证明了R（n）的导出子图是可数n阶图。我们证明了所有可数群嵌入R（n）的自同构群。© 2008 Wiley Periodicals，Inc. J Graph Theory 60：204-218，2009
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