Finite 3-set-homogeneous graphs

Abstract In this paper, all graphs are assumed to be finite. Let s ≥ 1 be an integer. A graph is called s -CSH ( s -connected-set-homogeneous) if for every pair of isomorphic connected induced subgraphs on at most s vertices, there exists an automorphism mapping the first to the second. A graph is called s -SH ( s -set-homogeneous) if for every pair of isomorphic induced subgraphs (not necessarily connected) on at most s vertices, there exists an automorphism mapping the first to the second. A graph is called s -homogeneous (respectively s -CH, that is, s -connected-homogeneous) if every isomorphism between two induced subgraphs (respectively, connected induced subgraphs) on at most s vertices extends to an automorphism of the whole graph. The first main result, Theorem 1.1, proves that each connected 3-CSH graph is arc-transitive. A consequence of this result is that each 3-CSH graph is 2-CH. Note that 2-CSH but not 2-CH graphs are just half-arc-transitive graphs which have been extensively studied in the literature. Motivated by this, it is natural to consider 3-CSH but not 3-CH graphs. In this paper, we first prove that there exist infinitely many 3-CSH but not 3-CH graphs, and then prove that every prime valent 3-CSH graph is 3-CH. Finally, using these two results, we classify all arc-regular 3-CSH but not 3-CH graphs of girth 3.