From Surf Wiki (app.surf) — the open knowledge base

Foster graph

Bipartite 3-regular graph with 90 vertices and 135 edges

Field	Value
name	Foster graph
image	[[Image:Foster graph.svg	240px]]
image_caption	The Foster graph
namesake	Ronald Martin Foster
vertices	90
edges	135
chromatic_number	2
chromatic_index	3
automorphisms	4320
girth	10
diameter	8
radius	8
properties	Cubic
Bipartite
Symmetric
Hamiltonian
Distance-transitive
queue number	2

Bipartite Symmetric Hamiltonian Distance-transitive

In the mathematical field of graph theory, the Foster graph is a bipartite 3-regular graph with 90 vertices and 135 edges.

The Foster graph is Hamiltonian and has chromatic number 2, chromatic index 3, radius 8, diameter 8 and girth 10. It is also a 3-vertex-connected and 3-edge-connected graph. It has queue number 2 and the upper bound on the book thickness is 4.

All the cubic distance-regular graphs are known. The Foster graph is one of the 13 such graphs. It is the unique distance-transitive graph with intersection array {3,2,2,2,2,1,1,1;1,1,1,1,2,2,2,3}. It can be constructed as the incidence graph of the partial linear space which is the unique triple cover with no 8-gons of the generalized quadrangle GQ(2,2). It is named after R. M. Foster, whose Foster census of cubic symmetric graphs included this graph.

The bipartite half of the Foster graph is a distance-regular graph and a locally linear graph. It is one of a finite number of such graphs with degree six.{{citation

Algebraic properties

The automorphism group of the Foster graph is a group of order 4320. It acts transitively on the vertices, on the edges and on the arcs of the graph. Therefore, the Foster graph is a symmetric graph. It has automorphisms that take any vertex to any other vertex and any edge to any other edge. According to the Foster census, the Foster graph, referenced as F90A, is the only cubic symmetric graph on 90 vertices.

The characteristic polynomial of the Foster graph is equal to (x-3) (x-2)^9 (x-1)^{18} x^{10} (x+1)^{18} (x+2)^9 (x+3) (x^2-6)^{12}.

Gallery

Image:Foster graph colored.svg|Foster graph colored to highlight various cycles. Image:Foster graph 2COL.svg|The chromatic number of the Foster graph is 2. Image:Foster_graph_3color_edge.svg|The chromatic index of the Foster graph is 3.

References

{{citation
{{citation
{{citation

References

"Foster Graph".
Wolz, Jessica; ''Engineering Linear Layouts with SAT.'' Master Thesis, University of Tübingen, 2018
Brouwer, A. E.; Cohen, A. M.; and Neumaier, A. Distance-Regular Graphs. New York: Springer-Verlag, 1989.
[http://www.win.tue.nl/~aeb/graphs/cubic_drg.html Cubic distance-regular graphs], A. Brouwer.
"G-12 Foster graph".
[[Marston Conder. Conder, M.]] and Dobcsányi, P. "Trivalent Symmetric Graphs Up to 768 Vertices." J. Combin. Math. Combin. Comput. 40, 41-63, 2002.

Info: Wikipedia Source

This article was imported from Wikipedia and is available under the Creative Commons Attribution-ShareAlike 4.0 License. Content has been adapted to SurfDoc format. Original contributors can be found on the article history page.

individual-graphs regular-graphs

Want to explore this topic further?

Ask Mako anything about Foster graph — get instant answers, deeper analysis, and related topics.

Research with Mako

Free with your Surf account

Content sourced from Wikipedia, available under CC BY-SA 4.0.

This content may have been generated or modified by AI. CloudSurf Software LLC is not responsible for the accuracy, completeness, or reliability of AI-generated content. Always verify important information from primary sources.

Report