Locally \(K_{3,3}\) or Petersen graphs (Q1199580): Difference between revisions

For a graph \(G\) the subgraph \(G_{x}\) induced on the set of neighbors of a vertex \(x\) is called a point neighborhood or a local graph. Let \(S\) be a set of graphs. A graph \(G\) is said to be locally \(S\), if all its local graphs are isomorphic to that of the set \(S\). Let \(S\) consist of two graphs, namely, the complete bipartite graph \(K_{3,3}\) and the Petersen graph \(P\). In the article the graphs having local graphs of both types \(K_{3,3}\) and \(P\) are determined. There exist only two such graphs on 13 and 25 vertices. Thus locally \(S\) graphs are completely classified. Indeed, the graphs which are locally \(\{K_{3,3}\}\) (one graph on 9 vertices) and locally \(\{P\}\) (three graphs on 21, 63, 65 vertices) were classified before. As noted it was the last open case in the classification of locally cotriangular graphs. This answers a question of J. I. Hall.