Publications Meetings The Profession Membership Programs Math Samplings Policy & Advocacy In the News About the AMS

   
Mobile Device Pairing
Green Open Access
Transactions of the American Mathematical Society
Transactions of the American Mathematical Society
ISSN 1088-6850(online) ISSN 0002-9947(print)

   

 

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


Authors: Matthias Hamann and Fabian Hundertmark
Journal: Trans. Amer. Math. Soc. 365 (2013), 531-553
MSC (2010): Primary 05C20, 05C63
Published electronically: June 29, 2012
MathSciNet review: 2984067
Full-text PDF

Abstract | References | Similar Articles | Additional Information

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 [Enhancements On Off] (What's this?)

  • 1. P.J. Cameron, C.E. Praeger, N.C. Wormald, Infinite highly arc transitive digraphs and universal covering digraphs, Combinatorica 13 (4) (1993), 377-396 MR 1262915 (95b:05084)
  • 2. G.L. Cherlin, Homogeneous tournaments revisited, Geom.Dedicata 26 (2) (1988), 231-239 MR 939465 (89k:05039)
  • 3. G.L. Cherlin, The classification of countable homogeneous directed graphs and countable homogeneous $ n$-tournaments, Mem. Amer. Math. Soc., 131 (621) xiv+161 pp., 1998 MR 1434988 (98k:03080)
  • 4. W. Dicks, M.J. Dunwoody, Groups Acting on Graphs, Cambridge Stud. Adv. Math., vol. 17, Cambridge Univ. Press, Cambridge, 1989 MR 1001965 (91b:20001)
  • 5. R. Diestel, Graph Theory, 4th ed., Springer-Verlag, 2010 MR 2744811
  • 6. R. Diestel, H.A. Jung, R.G. Möller, On vertex transitive graphs of infinite degree, Arch. Math. 60 (1993), 591-600 MR 1216705 (95e:05056)
  • 7. M.J. Dunwoody, Cutting up graphs, Combinatorica 2 (1) (1982), 15-23 MR 671142 (84k:05050)
  • 8. M.J. Dunwoody, B. Krön, Vertex cuts, preprint, arXiv:0905.0064v2
  • 9. H. Enomoto, Combinatorially homogeneous graphs, J.Combin. Theory Ser. B 30 (2) (1981), 215-223 MR 615315 (83h:05070)
  • 10. P. Erdős, J. Spencer, Probabilistic Methods in Combinatorics, Academic Press, New York, 1974 MR 0382007 (52:2895)
  • 11. A. Gardiner, Homogeneous graphs, J. Combin. Theory Ser. B 20 (1) (1976), 94-102 MR 0419293 (54:7316)
  • 12. A. Gardiner, Homogeneity conditions in graphs, J.Combin. Theory Ser. B 24 (3) (1978), 301-310 MR 496449 (80b:05034)
  • 13. R. Gray, D. Macpherson, Countable connected-homogeneous graphs, J. Combin. Theory Ser. B 100 (2) (2010), 97-118 MR 2595694
  • 14. R. Gray, R.G. Möller, Locally-finite connected-homogeneous digraphs, Discrete Math. 311 (15) (2011), 1497-1517 MR 2800974
  • 15. M. Goldstern, R. Grossberg, M. Kojman, Infinite homogeneous bipartite graphs with unequal sides, Discrete Math., 149 (1-3) (1996), 69-82 MR 1375099 (97a:05102)
  • 16. M. Hamann, End-transitive graphs, to appear in Israel J. Math.
  • 17. M. Hamann, J. Pott, Transitivity conditions in infinite graphs, preprint, arXiv:0910.5651
  • 18. S. Hedman, W.Y. Pong, Locally finite homogeneous graphs, Combinatorica 30 (4) (2010), 419-434 MR 2728496
  • 19. B. Krön, Cutting up graphs revisited - a short proof of Stallings' structure theorem, Groups Complex. Cryptol. 2 (2) (2010), 213-221 MR 2747150
  • 20. A.H. Lachlan, Finite homogeneous simple digraphs, in Proceedings of the Herbrand symposium (Marseilles, 1981), volume 107 of Stud. Logic Found. Math., 189-208, Amsterdam, 1982, North-Holland MR 757029 (85h:05049)
  • 21. A.H. Lachlan, Countable homogeneous tournaments, Trans.Amer. Math. Soc. 284 (2) (1984), 431-461 MR 743728 (85i:05118)
  • 22. A.H. Lachlan, R. Woodrow, Countable ultrahomogeneous undirected graphs, Trans. Amer. Math. Soc. 262 (1) (1980), 51-94 MR 583847 (82c:05083)
  • 23. H.D. Macpherson, Infinite distance transitive graphs of finite valency, Combinatorica 2 (1) (1982), 63-69 MR 671146 (84g:05075)
  • 24. A. Malnič, D. Marušič, R.G. Möller, N. Seifter, V. Trofimov, B. Zgrablič, Highly arc transitive digraphs: reachability, topological groups, European J. Combin. 26 (1) (2005), 19-28 MR 2101032 (2005i:05081)
  • 25. A. Malnič, D. Marušič, N. Seifter, B.Zgrablić, Highly arc-transitive digraphs with no homomorphism onto $ \mathbb{Z}$, Combinatorica 22 (3) (2002), 435-443 MR 1932063 (2003h:05093)
  • 26. R.G. Möller, Accessibility and ends of graphs, J.Combin. Theory Ser. B 66 (2) (1996), 303-309 MR 1376053 (97b:20056)
  • 27. R.G. Möller, Distance-transitivity in infinite graphs, J. Combin. Theory Ser. B 60 (1) (1994), 36-39 MR 1256581 (95b:05099)
  • 28. R.G. Möller, Groups acting on locally finite graphs--a survey of the infinitely ended case. In Groups '93 Galway/St. Andrews, Vol. 2, 426-456. Cambridge Univ. Press, Cambridge, 1995 MR 1337287 (96h:05099)
  • 29. C. Ronse, On homogeneous graphs, J. London Math. Soc.(2) 17 (3) (1978), 375-379 MR 500619 (80e:05066)
  • 30. N. Seifter, Transitive digraphs with more than one end, Discrete Math. 308 (9) (2008), 1531-1537 MR 2392594 (2008m:05139)
  • 31. C. Thomassen, W. Woess, Vertex-transitive graphs and accessibility, J. Combin. Theory Ser. B 58 (2) (1993), 248-268 MR 1223698 (94f:05070)

Similar Articles

Retrieve articles in Transactions of the American Mathematical Society with MSC (2010): 05C20, 05C63

Retrieve articles in all journals with MSC (2010): 05C20, 05C63


Additional Information

Matthias Hamann
Affiliation: Fachbereich Mathematik, Universität Hamburg, Bundesstraße 55, 20146 Hamburg, Germany
Email: matthias.hamann@math.uni-hamburg.de

Fabian Hundertmark
Affiliation: Fachbereich Mathematik, Universität Hamburg, Bundesstraße 55, 20146 Hamburg, Germany
Email: fabian.hundertmark@math.uni-hamburg.de

DOI: http://dx.doi.org/10.1090/S0002-9947-2012-05666-2
Received by editor(s): April 30, 2010
Received by editor(s) in revised form: March 13, 2011, and June 9, 2011
Published electronically: June 29, 2012
Article copyright: © Copyright 2012 by the authors