HIGHLY ARC-TRANSITIVE DIGRAPHS - STRUCTURE AND COUNTEREXAMPLES

被引：3

作者：

Devos, Matt ^{[1
]}

Mohar, Bojan ^{[1
]}

Samal, Robert ^{[2
]}

机构：

[1] Simon Fraser Univ, Dept Math, Burnaby, BC V5A 1S6, Canada

[2] Charles Univ Prague, Inst Comp Sci, Prague, Czech Republic

来源：

COMBINATORICA | 2015年 / 35卷 / 05期

基金：

加拿大自然科学与工程研究理事会;

关键词：

GRAPHS;

D O I：

10.1007/s00493-014-3040-4

中图分类号：

O1 [数学];

学科分类号：

0701 ; 070101 ;

摘要：

Two problems of Cameron, Praeger, and Wormald [Infinite highly arc transitive digraphs and universal covering digraphs, Combinatorica (1993)] are resolved. First, locally finite highly arc-transitive digraphs with universal reachability relation are presented. Second, constructions of two-ended highly arc-transitive digraphs are provided, where each 'building block' is a finite bipartite digraph that is not a disjoint union of complete bipartite digraphs. Both of these were conjectured impossible in the above-mentioned paper. We also describe the structure of two-ended highly arc-transitive digraphs in more generality, heading towards a characterization of such digraphs. However, the complete characterization remains elusive.

引用

页码：553 / 571

页数：19

共 14 条

[1] Horocyclic products of trees
Bartholdi, Laurent
Neuhauser, Markus
Woess, Wolfgang
[J]. JOURNAL OF THE EUROPEAN MATHEMATICAL SOCIETY, 2008, 10 (03) : 771 - 816
[2] Bondy J.A., 2008, GTM 244
[3] INFINITE HIGHLY ARC TRANSITIVE DIGRAPHS AND UNIVERSAL COVERING DIGRAPHS
CAMERON, PJ
PRAEGER, CE
WORMALD, NC
[J]. COMBINATORICA, 1993, 13 (04) : 377 - 396
[4] DlESTEL R., 2005, GRADUATE TEXTS MATH, V173
[5] CUTTING UP GRAPHS
DUNWOODY, MJ
[J]. COMBINATORICA, 1982, 2 (01) : 15 - 23
[6] Highly arc transitive digraphs:: reachability, topological groups
Malnic, A
Marusic, D
Möller, RG
Seifter, N
Trofimov, V
Zgrablic, B
[J]. EUROPEAN JOURNAL OF COMBINATORICS, 2005, 26 (01) : 19 - 28
[7] Highly arc-transitive digraphs with no homomorphism onto Z
Malnic, A
Marusic, D
Seifter, N
Zgrablic, B
[J]. COMBINATORICA, 2002, 22 (03) : 435 - 443
[8] Structure theory of totally disconnected locally compact groups via graphs and permutations
Möller, RG
[J]. CANADIAN JOURNAL OF MATHEMATICS-JOURNAL CANADIEN DE MATHEMATIQUES, 2002, 54 (04): : 795 - 827
[9] Descendants in highly arc transitive digraphs
Möller, RG
[J]. DISCRETE MATHEMATICS, 2002, 247 (1-3) : 147 - 157
[10] Constructing highly arc transitive digraphs using a direct fibre product
Neumann, Christoph
[J]. DISCRETE MATHEMATICS, 2013, 313 (23) : 2816 - 2829

← 1 2 →