TOPICS
Search

Biggs-Smith Graph


BiggsSmithGraphEmbeddings

The Biggs-Smith graph is cubic symmetric graph F_(102)A on 102 vertices and 153 edges that is also distance-regular with intersection array {3,2,2,2,1,1,1;1,1,1,1,1,1,3} and distance-transitive.

It is known to be uniquely determined by its graph spectrum (van Dam and Haemers 2003). Its automorphism group is of order 2448 (Royle).

It is implemented in the Wolfram Language as GraphData["BiggsSmithGraph"].

The Biggs-Smith graph is an order-17 graph expansion of the H graph with step offsets 3, 5, 6, and 7 (where these are a different set of steps from those reported by Biggs 1993, p. 147). It is therefore one of only two cubic symmetric H graphs (the other being F_(204)A).

BiggsSmithGraphUnitDistance

The Biggs-Smith graph is a unit-distance graph, as are all cubic symmetric H-, I-, and Y-graphs (E. Gerbracht, pers. comm., Jan. 2010).

The Biggs-Smith graph has 2849472 distinct (directed) Hamiltonian cycles which correspond to 890 distinct LCF notations, all of which are of order 1 (E. Weisstein, May 30, 2008). One such LCF notation (of length 102) is given by [16, 24, -38, 17, 34, 48, -19, 41, -35, 47, -20, 34, -36, 21, 14, 48, -16, -36, -43, 28, -17, 21, 29, -43, 46, -24, 28, -38, -14, -50, -45, 21, 8, 27, -21, 20, -37, 39, -34, -44, -8, 38, -21, 25, 15, -34, 18, -28, -41, 36, 8, -29, -21, -48, -28, -20, -47, 14, -8, -15, -27, 38, 24, -48, -18, 25, 38, 31, -25, 24, -46, -14, 28, 11, 21, 35, -39, 43, 36, -38, 14, 50, 43, 36, -11, -36, -24, 45, 8, 19, -25, 38, 20, -24, -14, -21, -8, 44, -31, -38, -28, 37].

BiggsSmithGraphMatrices

The plots above show the adjacency, incidence, and distance matrices of the graph.

The bipartite double graph and double cover of the Biggs-Smith graph is the cubic symmetric graph F_(204)A.


See also

Cubic Symmetric Graph, Distance-Regular Graph, Graph Expansion

Explore with Wolfram|Alpha

References

Biggs, N. L. Algebraic Graph Theory, 2nd ed. Cambridge, England: Cambridge University Press, 1993.DistanceRegular.org. "Biggs-Smith Graph." http://www.distanceregular.org/graphs/biggssmith.html.Royle, G. "F102A." http://www.csse.uwa.edu.au/~gordon/foster/F102A.html.Royle, G. "Cubic Symmetric Graphs (The Foster Census): Distance-Regular Graphs." http://school.maths.uwa.edu.au/~gordon/remote/foster/#drgs.van Dam, E. R. and Haemers, W. H. "Spectral Characterizations of Some Distance-Regular Graphs." J. Algebraic Combin. 15, 189-202, 2003.Van Maldeghem, H. and Ver Gucht, V. "Some Properties of the Biggs-Smith Geometry." Bull. Belg. Math. Soc. Simon Stevin 12, 919-924, 2006.

Cite this as:

Weisstein, Eric W. "Biggs-Smith Graph." From MathWorld--A Wolfram Web Resource. https://mathworld.wolfram.com/Biggs-SmithGraph.html

Subject classifications