In the

mathematical Mathematics is a field of study that discovers and organizes methods, Mathematical theory, theories and theorems that are developed and Mathematical proof, proved for the needs of empirical sciences and mathematics itself. There are many ar ...

field of

graph theory In mathematics and computer science, graph theory is the study of ''graph (discrete mathematics), graphs'', which are mathematical structures used to model pairwise relations between objects. A graph in this context is made up of ''Vertex (graph ...

, the Foster graph is a bipartite 3-

regular graph In graph theory, a regular graph is a Graph (discrete mathematics), graph where each Vertex (graph theory), vertex has the same number of neighbors; i.e. every vertex has the same Degree (graph theory), degree or valency. A regular directed graph ...

with 90 vertices and 135 edges. The Foster graph is

Hamiltonian Hamiltonian may refer to: * Hamiltonian mechanics, a function that represents the total energy of a system * Hamiltonian (quantum mechanics), an operator corresponding to the total energy of that system ** Dyall Hamiltonian, a modified Hamiltonian ...

and has

chromatic number In graph theory, graph coloring is a methodic assignment of labels traditionally called "colors" to elements of a graph. The assignment is subject to certain constraints, such as that no two adjacent elements have the same color. Graph coloring i ...

chromatic index In graph theory, a proper edge coloring of a Graph (discrete mathematics), graph is an assignment of "colors" to the edges of the graph so that no two incident edges have the same color. For example, the figure to the right shows an edge colorin ...

3, radius 8, diameter 8 and

girth Girth may refer to: Mathematics * Girth (functional analysis), the length of the shortest centrally symmetric simple closed curve on the unit sphere of a Banach space * Girth (geometry), the perimeter of a parallel projection of a shape * Girth ...

10. It is also a 3- vertex-connected and 3- edge-connected graph. It has

queue number In the mathematical field of graph theory, the queue number of a Graph (discrete mathematics), graph is a graph invariant defined analogously to book thickness, stack number (book thickness) using Queue (abstract data type), first-in first-out (q ...

2 and the upper bound on the

book thickness In graph theory, a book embedding is a generalization of planar embedding of a graph to embeddings in a ''book'', a collection of half-planes all having the same line as their boundary. Usually, the vertices of the graph are required to lie on ...

is 4. All the

cubic Cubic may refer to: Science and mathematics * Cube (algebra), "cubic" measurement * Cube, a three-dimensional solid object bounded by six square faces, facets or sides, with three meeting at each vertex ** Cubic crystal system, a crystal system w ...

distance-regular graph In the mathematical field of graph theory, a distance-regular graph is a regular graph such that for any two vertices and , the number of vertices at distance from and at distance from depends only upon , , and the distance between and . ...

s are known. The Foster graph is one of the 13 such graphs. It is the unique distance-transitive graph with

intersection array In the mathematical field of graph theory, a distance-regular graph is a regular graph such that for any two Vertex (graph theory), vertices and , the number of vertices at distance (graph theory), distance from and at distance from depends ...

. It can be constructed as the incidence graph of the

partial linear space A partial linear space (also semilinear or near-linear space) is a basic incidence structure in the field of incidence geometry, that carries slightly less structure than a linear space. The notion is equivalent to that of a linear hypergraph. Def ...

which is the unique triple

cover Cover or covers may refer to: Packaging * Another name for a lid * Cover (philately), generic term for envelope or package * Album cover, the front of the packaging * Book cover or magazine cover ** Book design ** Back cover copy, part of c ...

with no 8-gons of the

generalized quadrangle In geometry, a generalized quadrangle is an incidence structure whose main feature is the lack of any triangles yet containing many quadrangles. A generalized quadrangle is by definition a polar space of rank two. They are the with ''n'' = 4 a ...

''GQ''(2,2). It is named after

R. M. Foster Ronald Martin Foster (3 October 1896 – 2 February 1998), was an American mathematician at Bell Labs whose work was of significance regarding electronic filters for use on telephone lines. He published an important paper, ''A Reactance Theorem' ...

, whose ''

Foster census In the mathematical field of graph theory, a graph is symmetric or arc-transitive if, given any two ordered pairs of adjacent vertices (u_1,v_1) and (u_2,v_2) of , there is an automorphism :f : V(G) \rightarrow V(G) such that :f(u_1) = u_2 a ...

'' of

symmetric graph In the mathematical field of graph theory, a graph is symmetric or arc-transitive if, given any two ordered pairs of adjacent vertices (u_1,v_1) and (u_2,v_2) of , there is an automorphism :f : V(G) \rightarrow V(G) such that :f(u_1) = u_2 a ...

s included this graph. The

bipartite half In graph theory, the bipartite half or half-square of a bipartite graph is a graph whose vertex set is one of the two sides of the bipartition (without loss of generality, ) and in which there is an edge for each pair of vertices in that ar ...

of the Foster graph is a

and a

locally linear graph In graph theory, a locally linear graph is an undirected graph in which every edge belongs to exactly one triangle. Equivalently, for each vertex of the graph, its neighborhood (graph theory), neighbors are each adjacent to exactly one other neigh ...

. It is one of a finite number of such graphs with degree six.

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

. 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 In linear algebra, the characteristic polynomial of a square matrix is a polynomial which is invariant under matrix similarity and has the eigenvalues as roots. It has the determinant and the trace of the matrix among its coefficients. The ...

of the Foster graph is equal to

(x-3) (x-2)^9 (x-1)^ x^ (x+1)^ (x+2)^9 (x+3) (x^2-6)^

Gallery

Image:Foster graph colored.svg, Foster graph colored to highlight various cycles. Image:Foster graph 2COL.svg, The

of the Foster graph is 2. Image:Foster_graph_3color_edge.svg, The

of the Foster graph is 3.

References

*. *. *{{citation , last = Van Maldeghem , first = Hendrik , title = Ten exceptional geometries from trivalent distance regular graphs , journal =

Annals of Combinatorics ''Annals of Combinatorics'' is a quarterly peer-reviewed scientific journal covering research in combinatorics. It was established in 1997 by William Chen and is published by Birkhäuser. The journal publishes articles in combinatorics and relate ...

, volume = 6 , issue = 2 , year = 2002 , pages = 209–228 , mr = 1955521 , doi = 10.1007/PL00012587, s2cid = 195315348 . Individual graphs Regular graphs