Foster graph

Foster graph
The Foster graph
Named afterRonald Martin Foster
Vertices90
Edges135
Radius8
Diameter8
Girth10
Automorphisms4320
Chromatic number2
Chromatic index3
Queue number2
PropertiesCubic
Bipartite
Symmetric
Hamiltonian
Distance-transitive
Table of graphs and parameters

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

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.[2]

All the cubic distance-regular graphs are known.[3] 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}.[4] 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.[5]

  1. ^ Weisstein, Eric W. "Foster Graph". MathWorld.
  2. ^ Wolz, Jessica; Engineering Linear Layouts with SAT. Master Thesis, University of Tübingen, 2018
  3. ^ Brouwer, A. E.; Cohen, A. M.; and Neumaier, A. Distance-Regular Graphs. New York: Springer-Verlag, 1989.
  4. ^ Cubic distance-regular graphs, A. Brouwer.
  5. ^ Hiraki, Akira; Nomura, Kazumasa; Suzuki, Hiroshi (2000), "Distance-regular graphs of valency 6 and ", Journal of Algebraic Combinatorics, 11 (2): 101–134, doi:10.1023/A:1008776031839, MR 1761910