The Foster graph is a bipartite 3- regular graph with 90 vertices and 135 edges [1] . The Foster graph is Hamiltonian , has a chromatic number 2, a chromatic index 3, a radius of 8, a diameter of 8, and a girth of 10. It is also vertex 3-connected and edge-3-connected .
| Count Foster | |
|---|---|
 | |
| Named after | Ronald Foster |
| Top | 90 |
| Riber | 135 |
| Radius | eight |
| Diameter | eight |
| Girth | ten |
| Automorphisms | 4320 |
| Chromatic number | 2 |
| Chromatic Index | 3 |
| The properties | cubic remote transitive |
All cubic distance-regular graphs are known [2] , the Foster graph is one of 13 such graphs. The graph is the only distance-transitive graph with an intersection array {3,2,2,2,2,1,1,1,1; 1,1,1,1,2,2,2,3} [3] . The graph can be constructed as an incident graph of a , which is the only triple covering without octagons of generalized quadrangles GQ (2,2) . The graph is named after Ronald Foster , who compiled a list of cubic symmetric graphs ( the Foster list ), which includes the Foster graph.
Content
Algebraic properties
The group of automorphisms of the Foster graph is a group of order 4320 [4] . It acts transitively on the vertices and edges of the graph; therefore, the Foster graph is symmetric . The graph has automorphisms that translate any vertex to any other and any edge to any other edge. In the Foster list, the Foster graph, indicated as F90A, is the only cubic symmetric graph with 90 vertices [5] .
The characteristic polynomial of the Foster graph is .
Gallery
Foster graph, painted in such a way as to highlight various cycles.
The chromatic number of Count Foster is 2.
The chromatic index of the Foster graph is 3.
Notes
- ↑ Weisstein, Eric W. Foster Graph on the Wolfram MathWorld website.
- ↑ AE Brouwer, AM Cohen, A. Neumaier. Distance - Regular Graphs. - New York: Springer — Verlag, 1989.
- ↑ Cubic distance-regular graphs , A. Brouwer.
- ↑ Royle, G. F090A data (link not available)
- ↑ M. Conder, P. Dobcsányi, “Trivalent Symmetric Graphs Up to 768 Vertices.” J. Combin. Math. Combin. Comput. 40, 41–63, 2002.
Literature
- NL Biggs, AG Boshier, J. Shawe — Taylor. Cubic distance - regular graphs // Journal of the London Mathematical Society. - 1986. - T. 33 , no. 3 . - S. 385-394 . - DOI : 10.1112 / jlms / s2-33.3.385 .
- Edwin R. Van Dam, Willem H. Haemers. Spectral characterizations of some distance - regular graphs // Journal of Algebraic Combinatorics. - 2002. - T. 15 , no. 2 . - S. 189-202 . - DOI : 10.1023 / A: 1013847004932 .
- Hendrik Van Maldeghem. Ten exceptional geometries from trivalent distance regular graphs // Annals of Combinatorics. - 2002. - T. 6 , no. 2 . - S. 209-228 . - DOI : 10.1007 / PL00012587 .