Locally-finite connected-homogeneous digraphs

DOI10.1016/J.DISC.2010.12.017MaRDI QIDQ2275381zbMATH OpenOpenAlexFDO

Authors Rögnvaldur G. Möller, R. Gray

Publication date 8 August 2011

Published in Discrete Mathematics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1011.6208

zbMATH Keywords

highly arc-transitive digraphshomogeneityinfinite digraphs

Mathematics Subject Classification ID

Directed graphs (digraphs), tournaments (05C20) Infinite graphs (05C63)

Abstract: 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.

Recommendations

• The classification of finite and locally finite connected-homogeneous digraphs
• Set-homogeneous directed graphs
• Descendant-homogeneous digraphs
• Highly-arc-transitive and descendant-homogeneous digraphs with finite out-valency
• Transitive digraphs with more than one end

Cites work

• \(k\)-CS-transitive infinite graphs
• Accessibility and Groups of Cohomological Dimension One
• An infinite highly arc-transitive digraph
• Combinatorially homogeneous graphs
• Countable connected-homogeneous graphs
• Countable Homogeneous Tournaments
• Cutting up graphs
• Descendants in highly arc transitive digraphs
• Distance-transitivity in infinite graphs
• Highly arc transitive digraphs
• Highly arc transitive digraphs: reachability, topological groups
• Highly arc-transitive digraphs with no homomorphism onto \(\mathbb Z\)
• Homogeneity conditions in graphs
• scientific article; zbMATH DE number 3819758 (Why is no real title available?)
• scientific article; zbMATH DE number 43547 (Why is no real title available?)
• scientific article; zbMATH DE number 41228 (Why is no real title available?)
• scientific article; zbMATH DE number 663783 (Why is no real title available?)
• scientific article; zbMATH DE number 923850 (Why is no real title available?)
• Infinite distance transitive graphs of finite valency
• Infinite highly arc transitive digraphs and universal covering digraphs
• Infinite homogeneous bipartite graphs with unequal sides
• On vertex transitive graphs of infinite degree
• The classification of countable homogeneous directed graphs and countable homogeneous 𝑛-tournaments
• Transitive digraphs with more than one end
• Vertex cuts
• Vertex-transitive graphs and accessibility

Cited in

(11)

• The classification of finite and locally finite connected-homogeneous digraphs
• Infinite arc-transitive and highly-arc-transitive digraphs
• The connectivities of locally finite primitive graphs
• The structure of locally finite two-connected graphs
• Homogeneous 2-partite digraphs
• Connected-homomorphism-homogeneous graphs
• A Construction of Locally Homogeneous Graphs
• scientific article; zbMATH DE number 804599 (Why is no real title available?)
• The classification of connected-homogeneous digraphs with more than one end
• Characterizing homogenous digraphs
• Descendant-homogeneous digraphs

This page was built for publication: Locally-finite connected-homogeneous digraphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2275381)