Locally-finite connected-homogeneous digraphs
Locally-finite connected-homogeneous digraphs
复制标题
局部有限连通齐次有向图
DOI：
10.1016/j.disc.2010.12.017
复制
发表时间：
2011
影响因子：
0.8
通讯作者：
Gray R
中科院分区：
文献类型：
--
作者：
Gray R
如果有限连通导出子图之间的任何同构扩展到有向图的自同构，则有向图是连通齐次的。我们考虑一端以上的局部有限连通齐次有向图。在有向图嵌入三角形的情况下，我们给出了一个完全的分类，得到了一族由有向三角形粘合而成的树状图。在无三角形的情况下，我们证明了这些有向图是高度弧传递的。在两端情形下，我们给出了一个分类，表明所有的例子都是通过沿着一条有向线粘合某个固定的有限完全有向二部图的副本而给出的一个简单结构。当有向图有无限多个末端时，我们证明了一个顶点的子孙形成了一棵树，而可达图(这是有向图的基本构件之一)是：偶圈、完全二部图、完美匹配的补图或无限半正则树。我们给出的例子表明，每一种可能性都被实现为某个连通齐次有向图的可达图，在这个过程中，我们得到了一族新的没有性质Z的高度弧传递有向图。
A digraph is connected-homogeneous if any isomorphism between finite connected induced subdigraphs extends to an automorphism of the digraph. We consider locally-finite connected-homogeneous digraphs with more than one end. In the case that the digraph embeds a triangle we give a complete classification, obtaining a family of tree-like graphs constructed by gluing together directed triangles. In the triangle-free case we show that these digraphs are highly arc-transitive. We give a classification in the two-ended case, showing that all examples arise from a simple construction given by gluing along a directed line copies of some fixed finite directed complete bipartite graph. When the digraph has infinitely many ends we show that the descendants of a vertex form a tree, and the reachability graph (which is one of the basic building blocks of the digraph) is one of: an even cycle, a complete bipartite graph, the complement of a perfect matching, or an infinite semiregular tree. We give examples showing that each of these possibilities is realised as the reachability graph of some connected-homogeneous digraph, and in the process we obtain a new family of highly arc-transitive digraphs without property Z.
登录
查看更多内容
高度弧传递有向图：可达性、拓扑群
DOI：
--
发表时间：
2005
期刊：
European journal of combinatorics (Print)
影响因子：
--
作者：
A. Malnic;D. Marušič;R. G. Möller;N. Seifter;V. Trofimov;B. Zgrablic
通讯作者：
B. Zgrablic
DOI：
--
发表时间：
1993
期刊：
影响因子：
--
作者：
R. Diestel;H. A. Jung;R. G. Möller
通讯作者：
R. G. Möller
可数的同质锦标赛
DOI：
10.1090/s0002-9947-1984-0743728-1
发表时间：
1984
影响因子：
1.3
作者：
A. Lachlan;Ron Morrow;Robert E. Woodrow
通讯作者：
Robert E. Woodrow
DOI：
--
发表时间：
1982
期刊：
Comb.
影响因子：
--
作者：
H. D. Macpherson
通讯作者：
H. D. Macpherson
DOI：
--
发表时间：
2010
期刊：
影响因子：
--
作者：
M. Hamann;F. Hundertmark
通讯作者：
F. Hundertmark