The classification of connected-homogeneous digraphs with more than one end

Hamann, Matthias; Hundertmark, Fabian

doi:10.1090/S0002-9947-2012-05666-2

The classification of connected-homogeneous digraphs with more than one end
HTML articles powered by AMS MathViewer

by Matthias Hamann and Fabian Hundertmark PDF

Trans. Amer. Math. Soc. 365 (2013), 531-553

Abstract:

We classify the connected-homogeneous digraphs with more than one end. We further show that if their underlying undirected graph is not connected-homogeneous, they are highly-arc-transitive.

References

Peter J. Cameron, Cheryl E. Praeger, and Nicholas C. Wormald, Infinite highly arc transitive digraphs and universal covering digraphs, Combinatorica 13 (1993), no. 4, 377–396. MR 1262915, DOI 10.1007/BF01303511
Gregory Cherlin, Homogeneous tournaments revisited, Geom. Dedicata 26 (1988), no. 2, 231–239. MR 939465, DOI 10.1007/BF00151671
Gregory L. Cherlin, The classification of countable homogeneous directed graphs and countable homogeneous $n$-tournaments, Mem. Amer. Math. Soc. 131 (1998), no. 621, xiv+161. MR 1434988, DOI 10.1090/memo/0621
Warren Dicks and M. J. Dunwoody, Groups acting on graphs, Cambridge Studies in Advanced Mathematics, vol. 17, Cambridge University Press, Cambridge, 1989. MR 1001965
Reinhard Diestel, Graph theory, 4th ed., Graduate Texts in Mathematics, vol. 173, Springer, Heidelberg, 2010. MR 2744811, DOI 10.1007/978-3-642-14279-6
R. Diestel, H. A. Jung, and R. G. Möller, On vertex transitive graphs of infinite degree, Arch. Math. (Basel) 60 (1993), no. 6, 591–600. MR 1216705, DOI 10.1007/BF01236086
M. J. Dunwoody, Cutting up graphs, Combinatorica 2 (1982), no. 1, 15–23. MR 671142, DOI 10.1007/BF02579278
M.J. Dunwoody, B. Krön, Vertex cuts, preprint, arXiv:0905.0064v2
Hikoe Enomoto, Combinatorially homogeneous graphs, J. Combin. Theory Ser. B 30 (1981), no. 2, 215–223. MR 615315, DOI 10.1016/0095-8956(81)90065-4
Paul Erdős and Joel Spencer, Probabilistic methods in combinatorics, Probability and Mathematical Statistics, Vol. 17, Academic Press [Harcourt Brace Jovanovich, Publishers], New York-London, 1974. MR 0382007
A. Gardiner, Homogeneous graphs, J. Combinatorial Theory Ser. B 20 (1976), no. 1, 94–102. MR 419293, DOI 10.1016/0095-8956(76)90072-1
A. Gardiner, Homogeneity conditions in graphs, J. Combin. Theory Ser. B 24 (1978), no. 3, 301–310. MR 496449, DOI 10.1016/0095-8956(78)90048-5
R. Gray and D. Macpherson, Countable connected-homogeneous graphs, J. Combin. Theory Ser. B 100 (2010), no. 2, 97–118. MR 2595694, DOI 10.1016/j.jctb.2009.04.002
Robert Gray and Rögnvaldur G. Möller, Locally-finite connected-homogeneous digraphs, Discrete Math. 311 (2011), no. 15, 1497–1517. MR 2800974, DOI 10.1016/j.disc.2010.12.017
Martin Goldstern, Rami Grossberg, and Menachem Kojman, Infinite homogeneous bipartite graphs with unequal sides, Discrete Math. 149 (1996), no. 1-3, 69–82. MR 1375099, DOI 10.1016/0012-365X(94)00339-K
M. Hamann, End-transitive graphs, to appear in Israel J. Math.
M. Hamann, J. Pott, Transitivity conditions in infinite graphs, preprint, arXiv:0910.5651
Shawn Hedman and Wai Yan Pong, Locally finite homogeneous graphs, Combinatorica 30 (2010), no. 4, 419–434. MR 2728496, DOI 10.1007/s00493-010-2472-8
Bernhard Krön, Cutting up graphs revisited—a short proof of Stallings’ structure theorem, Groups Complex. Cryptol. 2 (2010), no. 2, 213–221. MR 2747150, DOI 10.1515/GCC.2010.013
A. H. Lachlan, Finite homogeneous simple digraphs, Proceedings of the Herbrand symposium (Marseilles, 1981) Stud. Logic Found. Math., vol. 107, North-Holland, Amsterdam, 1982, pp. 189–208. MR 757029, DOI 10.1016/S0049-237X(08)71884-6
A. H. Lachlan, Countable homogeneous tournaments, Trans. Amer. Math. Soc. 284 (1984), no. 2, 431–461. MR 743728, DOI 10.1090/S0002-9947-1984-0743728-1
A. H. Lachlan and Robert E. Woodrow, Countable ultrahomogeneous undirected graphs, Trans. Amer. Math. Soc. 262 (1980), no. 1, 51–94. MR 583847, DOI 10.1090/S0002-9947-1980-0583847-2
H. D. Macpherson, Infinite distance transitive graphs of finite valency, Combinatorica 2 (1982), no. 1, 63–69. MR 671146, DOI 10.1007/BF02579282
Aleksander Malnič, Dragan Marušič, Rögnvaldur G. Möller, Norbert Seifter, Vladimir Trofimov, and Boris Zgrablič, Highly arc transitive digraphs: reachability, topological groups, European J. Combin. 26 (2005), no. 1, 19–28. MR 2101032, DOI 10.1016/j.ejc.2004.02.006
Aleksander Malnič, Dragan Marušič, Norbert Seifter, and Boris Zgrablić, Highly arc-transitive digraphs with no homomorphism onto $\Bbb Z$, Combinatorica 22 (2002), no. 3, 435–443. MR 1932063, DOI 10.1007/s004930200022
Rögnvaldur G. Möller, Accessibility and ends of graphs, J. Combin. Theory Ser. B 66 (1996), no. 2, 303–309. MR 1376053, DOI 10.1006/jctb.1996.0023
Rögnvaldur G. Möller, Distance-transitivity in infinite graphs, J. Combin. Theory Ser. B 60 (1994), no. 1, 36–39. MR 1256581, DOI 10.1006/jctb.1994.1003
Rögnvaldur G. Möller, Groups acting on locally finite graphs—a survey of the infinitely ended case, Groups ’93 Galway/St. Andrews, Vol. 2, London Math. Soc. Lecture Note Ser., vol. 212, Cambridge Univ. Press, Cambridge, 1995, pp. 426–456. MR 1337287, DOI 10.1017/CBO9780511629297.011
Christian Ronse, On homogeneous graphs, J. London Math. Soc. (2) 17 (1978), no. 3, 375–379. MR 500619, DOI 10.1112/jlms/s2-17.3.375
Norbert Seifter, Transitive digraphs with more than one end, Discrete Math. 308 (2008), no. 9, 1531–1537. MR 2392594, DOI 10.1016/j.disc.2007.04.011
Carsten Thomassen and Wolfgang Woess, Vertex-transitive graphs and accessibility, J. Combin. Theory Ser. B 58 (1993), no. 2, 248–268. MR 1223698, DOI 10.1006/jctb.1993.1042