1-homogeneous graphs (Q1072564)

Denote by \(VG\) the set of vertices of an arbitrary graph \(G\). Let \(X\) and \(Y\) be induced subgraphs of \(G\). A bijection \(f: VX\to VY\) is called a 1-isomorphism of \(G\) if for every \(x\in VG\) there exists \(y\in VG\) and for every \(y\in VG\) there exists \(x\in VG\) such that the extended map \(f: VX\cup \{x\}\to VY\cup \{y\}\), \(f(x)=y\), is an isomorphism of the corresponding induced subgraphs. \(G\) is called 1-homogeneous if each its 1-isomorphism can be extended to an automorphism of \(G\). It is proved that the classification of 1-homogeneous graphs is completely reduced to the analog problem for 1-homogeneous connected regular graphs. The diameters of the latter \(\leq 3\). The trivalent 1-homogeneous graphs are completely classified. A number of facts on the structure of 1-homogeneous connected regular graphs of diameter 2 is found.