A characterization of the Doob graphs (Q1898733)

Connected graphs fulfilling some homogeneity conditions are studied. Such conditions may be: (i) the graph is regular, (ii) any edge lies in exactly two triangles, (iii) any nonadjacent vertex pair has exactly two common neighbours, etc. A vertex-to-vertex mapping between graphs is called a local isomorphism if it preserves the adjacency in both directions. By an \(n\)-clique we mean a complete graph with \(n\) vertices. A special graph (having sixteen vertices) is called the Shrikhande graph. By a Doob graph a cartesian product of copies of the 4-clique and copies of the Shrikhande graph is understood. The main results (Theorems 21 and 23) are the following assertions. If a graph \(\Gamma\) has no induced pentagon and no induced \(K_{1,2,1}\), and satisfies (i), (iii), and an additional homogeneity condition, then it can be obtained as the image of a cartesian product of cliques under a local isomorphism. If \(\Gamma\) satisfies (i), (ii), (iii), and two additional homogeneity conditions, then it can be obtained as the image of a Doob graph (with the same valency as \(\Gamma)\) under a local isomorphism.