Locally K₃,3 or Petersen graphs

DOI10.1016/0012-365X(92)90529-OMaRDI QIDQ1199580zbMATH OpenOpenAlexFDO

Authors Aart Blokhuis, Andries E. Brouwer

Publication date 16 January 1993

Published in Discrete Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/0012-365x(92)90529-o

zbMATH Keywords

locally complete multipartite graphslocally cotriangular graphslocally Petersen graphs

Mathematics Subject Classification ID

Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60)

Review text

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.

Recommendations

• Finite locally-GQ (3,3) graphs
• scientific article; zbMATH DE number 97635
• Locally cotriangular graphs
• scientific article; zbMATH DE number 6107241
• On graphs the neighbourhoods of whose vertices are pseudo-geometric graphs for \(\mathrm{GQ}(3,3)\)

Cites work

• A finite graph which is locally a dodecahedron
• A local characterization of the Johnson scheme
• Graphs which are locally a cube
• Graphs with constant link and small degree or order
• scientific article; zbMATH DE number 3812380 (Why is no real title available?)
• scientific article; zbMATH DE number 3941599 (Why is no real title available?)
• scientific article; zbMATH DE number 43547 (Why is no real title available?)
• scientific article; zbMATH DE number 3407695 (Why is no real title available?)
• Local characterizations of polar spaces
• Locally 4‐by‐4 grid graphs
• Locally cotriangular graphs
• Locally homogeneous graphs from groups
• Locally petersen graphs
• Locally polar spaces and related rank 3 groups
• On graphs with a constant link. II
• Which trees are link graphs?

Cited in

(6)

• Locally cotriangular graphs
• A root graph that is locally the line graph of the Petersen graph
• Characterizing the platonic solids and Petersen graph as k-levels locally homogeneous graphs
• scientific article; zbMATH DE number 493033 (Why is no real title available?)
• Some locally Kneser graphs
• Local recognition of the point graphs of some Lie incidence geometries

This page was built for publication: Locally \(K_{3,3}\) or Petersen graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1199580)