In the mathematical

Mathematics

Mathematics is the study of quantity, space, structure, and change. Mathematicians seek out patterns and formulate new conjectures. Mathematicians resolve the truth or falsity of conjectures by mathematical proofs, which are arguments sufficient to convince other mathematicians of their validity...

 field of graph theory

Graph theory

In mathematics and computer science, graph theory is the study of graphs, mathematical structures used to model pairwise relations between objects from a certain collection. A "graph" in this context refers to a collection of vertices or 'nodes' and a collection of edges that connect pairs of...

, the Foster graph is a 3-regular graph

Regular graph

In graph theory, a regular graph is a graph where each vertex has the same number of neighbors; i.e. every vertex has the same degree or valency. A regular directed graph must also satisfy the stronger condition that the indegree and outdegree of each vertex are equal to each other...

 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

K-vertex-connected graph

In graph theory, a graph G with vertex set V is said to be k-vertex-connected if the graph remains connected when you delete fewer than k vertices from the graph...

 and 3-edge-connected

K-edge-connected graph

In graph theory, a graph is k-edge-connected if it remains connected whenever fewer than k edges are removed.-Formal definition:Let G =  be an arbitrary graph....

 graph.

All the cubic

Cubic graph

In the mathematical field of graph theory, a cubic graph is a graph in which all vertices have degree three. In other words a cubic graph is a 3-regular graph. Cubic graphs are also called trivalent graphs....

 distance-regular graph

Distance-regular graph

In mathematics, a distance-regular graph is a regular graph such that for any two vertices v and w at distance i the number of vertices adjacent to w and at distance j from v is the same. Every distance-transitive graph is distance-regular...

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

Distance-transitive graph

In the mathematical field of graph theory, a distance-transitive graph is a graph such that, given any two vertices v and w at any distance i, and any other two vertices x and y at the same distance, there is an automorphism of the graph that carries v to x and w to y.A distance transitive...

 graph with intersection array

Intersection array

In the mathematical field of graph theory, given a distance-regular graph G of diameter d, by definition there are integers bi and ci such that given any two vertices x and y in G at distance i, y has bi neighbours at distance i + 1 from x and ci neighbours at distance...

 {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

Partial linear space

A partial linear space is a basic incidence structure in the field of incidence geometry, that carries slightly less structure than a linear space.-Definition:...

 which is the unique triple cover with no 8-gons of the generalized quadrangle

Generalized quadrangle

A generalized quadrangle is an incidence structure. A generalized quadrangle is by definition a polar space of rank two. They are the generalized n-gons with n=4...

 GQ(2,2). It is named after R. M. Foster

R. M. Foster

Ronald Martin Foster , was a Bell Labs mathematician whose work was of significance regarding electronic filters for use on telephone lines...

, whose Foster census of cubic

Cubic graph

In the mathematical field of graph theory, a cubic graph is a graph in which all vertices have degree three. In other words a cubic graph is a 3-regular graph. Cubic graphs are also called trivalent graphs....

 symmetric graph

Symmetric graph

In the mathematical field of graph theory, a graph G is symmetric if, given any two pairs of adjacent vertices u1—v1 and u2—v2 of G, there is an automorphismsuch that...

s included this graph.

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

Symmetric graph

In the mathematical field of graph theory, a graph G is symmetric if, given any two pairs of adjacent vertices u1—v1 and u2—v2 of G, there is an automorphismsuch that...

. 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

Characteristic polynomial

In linear algebra, one associates a polynomial to every square matrix: its characteristic polynomial. This polynomial encodes several important properties of the matrix, most notably its eigenvalues, its determinant and its trace....

of the Foster graph is equal to .