Locally \(K_{3,3}\) or Petersen graphs (Q1199580)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Locally \(K_{3,3}\) or Petersen graphs |
scientific article |
Statements
Locally \(K_{3,3}\) or Petersen graphs (English)
0 references
16 January 1993
0 references
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.
0 references
locally complete multipartite graphs
0 references
locally Petersen graphs
0 references
locally cotriangular graphs
0 references