TOPICS

# Foster Graph

Cubic symmetric graphs are sometimes called Foster graphs and denoted , where is the vertex count and is a letter A, B, C, ... indicating the particular such cubic symmetric graph in the standard Foster census enumeration an its extensions (Foster 1932, Bouwer et al. 1988, Conder and Dobcsányi 2002, Royle). Many (if not all) Foster graphs can be constructed as honeycomb toroidal graphs.

"The" Foster graph is the cubic symmetric graph on 90 vertices illustrated above that has 135 edges and is also distance-regular with intersection array . It has girth 10, radius 8, and diameter 8. The Foster graph is also Hamiltonian. It has a unique order-15 LCF notations (), 4 order-5 notations, and 2 order-2 notations (illustrated above), as well as 397 order-1 notations.

The Foster graph is not uniquely determined by its graph spectrum (van Dam and Haemers 2003). It has graph spectrum

so it is not quite an integral graph.

It has chromatic number 2.

The halved Foster graph is distance-regular with intersection array .

Cubic Graph, Cubic Symmetric Graph, Distance-Regular Graph, Honeycomb Toroidal Graph, Symmetric Graph

## Explore with Wolfram|Alpha

More things to try:

## References

Bouwer, I. Z.; Chernoff, W. W.; Monson, B.; and Star, Z. The Foster Census. Charles Babbage Research Centre, 1988.Brouwer, A. E.; Cohen, A. M.; and Neumaier, A. Distance Regular Graphs. New York: Springer-Verlag, p. 398, 1989.Conder, M. and Dobcsányi, P. "Trivalent Symmetric Graphs Up to 768 Vertices." J. Combin. Math. Combin. Comput. 40, 41-63, 2002.DistanceRegular.org. "Foster Graph." http://www.distanceregular.org/graphs/foster.html.DistanceRegular.org. "Halved Foster Graph." http://www.distanceregular.org/graphs/halved-foster.html.Foster, R. M. "Geometrical Circuits of Electrical Networks." Trans. Amer. Inst. Elec. Engin. 51, 309-317, 1932.Royle, G. "F090A." http://www.csse.uwa.edu.au/~gordon/foster/F090A.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.

Foster Graph

## Cite this as:

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