Graphs which are locally a cube

DOI10.1016/0012-365X(83)90116-4MaRDI QIDQ788748zbMATH OpenFDO

Authors Dominique Buset

Publication date 1983

Published in Discrete Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/0012-365X(83)90116-4

zbMATH Keywords

(\(p\times q)\)-grid1-skeleton of the 3-dimensional cubeneighborhood

Mathematics Subject Classification ID

Structural characterization of families of graphs (05C75) Graph theory (05C99)

Review text

A graph G is said to be locally a cube iff each vertex of G has a neighborhood isomorphic to the 1-skeleton of the 3-dimensional cube. It is shown that the only graphs that are locally cubes are the 24-cell and the complement of the (3\(\times 5)\)-grid. The vertices of the 24-cell are the vectors \(+e_ i\pm e_ j(i\neq j) of{\mathbb{R}}^ 4\) where \(\{e_ i,e_ 2,e_ 3,e_ 4\}\) is the standard basis. Two vertices are adjacent if the angle between corresponding vectors is 60\(\circ\). Th\(e(p\times q)\)-grid is the graph whose vertices are the pq ordered pairs (i,j) with \(i=1,...,p\) and \(j=1,...,q\), two vertices being adjacent iff they have one coordinate in common. The author reports that A. Brouwer also had obtained this result (unpublished) and has characterized those graphs which are locally the complement of a (\(p\times q)\)-grid.

Recommendations

• scientific article; zbMATH DE number 6890355
• Cubical graphs and cubical dimensions
• Locally 4-by-4 grid graphs
• scientific article; zbMATH DE number 3941600
• Graphs which locally mirror the hypercube structure

Cites work

• scientific article; zbMATH DE number 3407710 (Why is no real title available?)
• Locally petersen graphs

Cited in

(20)

• A finite graph which is locally a dodecahedron
• Locally \(K_{3,3}\) or Petersen graphs
• Covering spaces of locally homogeneous graphs
• Covering projections of graphs preserving links of vertices and edges
• Graphs which locally mirror the hypercube structure
• Locally grid graphs: Classification and Tutte uniqueness
• On the local recognition of finite metasymplectic spaces
• Characterizing the platonic solids and Petersen graph as k-levels locally homogeneous graphs
• scientific article; zbMATH DE number 3865340 (Why is no real title available?)
• Locally 4-by-4 grid graphs
• scientific article; zbMATH DE number 3941599 (Why is no real title available?)
• scientific article; zbMATH DE number 3941600 (Why is no real title available?)
• scientific article; zbMATH DE number 64359 (Why is no real title available?)
• Pseudo-geometric graphs of the partial geometries pG 2 (4, t)
• scientific article; zbMATH DE number 6890355 (Why is no real title available?)
• An infinite family of incidence geometries whose incidence graphs are locally \(X^\ast\)
• 4-cycle properties for characterizing rectagraphs and hypercubes.
• Some locally Kneser graphs
• Locally triangular graphs and normal quotients of the n-cube
• The clique operator on matching and chessboard graphs

This page was built for publication: Graphs which are locally a cube

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