Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
4657151 | Journal of Combinatorial Theory, Series B | 2009 | 21 Pages |
A graph Γ is k-CS-transitive, for a positive integer k, if for any two connected isomorphic induced subgraphs A and B of Γ, each of size k, there is an automorphism of Γ taking A to B. The graph is called k-CS-homogeneous if any isomorphism between two connected induced subgraphs of size k extends to an automorphism. We consider locally-finite infinite k-CS-homogeneous and k-CS-transitive graphs. We classify those that are 3-CS-transitive (respectively homogeneous) and have more than one end. In particular, the 3-CS-homogeneous graphs with more than one end are precisely Macpherson's locally finite distance transitive graphs. The 3-CS-transitive but non-homogeneous graphs come in two classes. The first are line graphs of semiregular trees with valencies 2 and m, while the second is a class of graphs built up from copies of the complete graph K4, which we describe.