TOPICS
Search

Foster Graph


Cubic symmetric graphs are sometimes called Foster graphs and denoted F_(nnn)X, where nnn is the vertex count and X 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.

FosterGraph

"The" Foster graph is the cubic symmetric graph F_(090)A on 90 vertices illustrated above that has 135 edges and is also distance-regular with intersection array {3,2,2,2,2,1,1,1;1,1,1,1,2,2,2,3}. It has girth 10, radius 8, and diameter 8. The Foster graph is also Hamiltonian. It has a unique order-15 LCF notations ([17,-9,37,-37,9,-17]^(15)), 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

 (-3)^1(-sqrt(6))^(12)(-2)^9(-1)^(18)0^(10)1^(18)2^9(sqrt(6))^(12)3^1,

so it is not quite an integral graph.

It has chromatic number 2.

The halved Foster graph is distance-regular with intersection array {6,4,2,1;1,1,4,6}.


See also

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

Explore with Wolfram|Alpha

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.

Referenced on Wolfram|Alpha

Foster Graph

Cite this as:

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

Subject classifications