Foster graph
{{Short description|Bipartite 3-regular graph with 90 vertices and 135 edges}}
{{infobox graph
| name = Foster graph
| image = 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}}
In the mathematical field of graph theory, the Foster graph is a bipartite 3-regular graph with 90 vertices and 135 edges.{{MathWorld|urlname=FosterGraph|title=Foster Graph}}
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.Wolz, Jessica; Engineering Linear Layouts with SAT. Master Thesis, University of Tübingen, 2018
All the cubic distance-regular graphs are known.Brouwer, A. E.; Cohen, A. M.; and Neumaier, A. Distance-Regular Graphs. New York: Springer-Verlag, 1989. 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}.[http://www.win.tue.nl/~aeb/graphs/cubic_drg.html Cubic distance-regular graphs], A. Brouwer. 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
| last1 = Hiraki | first1 = Akira
| last2 = Nomura | first2 = Kazumasa
| last3 = Suzuki | first3 = Hiroshi
| doi = 10.1023/A:1008776031839
| issue = 2
| journal = Journal of Algebraic Combinatorics
| mr = 1761910
| pages = 101–134
| title = Distance-regular graphs of valency 6 and
| volume = 11
| year = 2000| doi-access = free
}}
Algebraic properties
The automorphism group of the Foster graph is a group of order 4320.{{citation|title=G-12 Foster graph|url=http://atlas.gregas.eu/graphs/33|work=Encyclopedia of Graphs|access-date=2024-02-26}} 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.Conder, M. and Dobcsányi, P. "Trivalent Symmetric Graphs Up to 768 Vertices." J. Combin. Math. Combin. Comput. 40, 41-63, 2002.
The characteristic polynomial of the Foster graph is equal to .
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
{{reflist}}
- {{citation
| last1 = Biggs | first1 = N. L. | last2 = Boshier | first2 = A. G. | last3 = Shawe-Taylor | first3 = J.
| title = Cubic distance-regular graphs
| journal = Journal of the London Mathematical Society
| volume = 33 | issue = 3 | year = 1986 | pages = 385–394
| doi = 10.1112/jlms/s2-33.3.385
| mr = 0850954 }}.
- {{citation
| last1 = Van Dam | first1 = Edwin R. | last2 = Haemers | first2 = Willem H.
| title = Spectral characterizations of some distance-regular graphs
| journal = Journal of Algebraic Combinatorics
| volume = 15 | issue = 2 | year = 2002 | pages = 189–202
| mr = 1887234
| doi = 10.1023/A:1013847004932| doi-access = free}}.
- {{citation
| last = Van Maldeghem | first = Hendrik
| title = Ten exceptional geometries from trivalent distance regular graphs
| journal = Annals of Combinatorics
| volume = 6 | issue = 2 | year = 2002 | pages = 209–228
| mr = 1955521
| doi = 10.1007/PL00012587| s2cid = 195315348
}}.