Jarl af Foster

Jarl af Foster
Opkaldt efter Ronald Foster
Toppe 90
ribben 135
Radius otte
Diameter otte
Omkreds ti
Automorfismer 4320
Kromatisk tal 2
Kromatisk indeks 3
Ejendomme

kubisk
todelt
symmetrisk
Hamiltonian


distance-transitiv
 Mediefiler på Wikimedia Commons

Foster-grafen  er en todelt 3 - regulær graf med 90 hjørner og 135 kanter [1] . Foster-grafen er Hamiltonsk , har kromatisk nummer 2, kromatisk indeks 3, radius 8, diameter 8 og omkreds 10. Den er også vertex-3-forbundet og kant-3-forbundet .

Alle kubiske afstand-regulære grafer er kendte [2] , Foster-grafen er en af ​​13 sådanne grafer. Grafen er den eneste afstandstransitive graf med skæringsarray {3,2,2,2,2,1,1,1;1,1,1,1,2,2,2,3} [3] . Grafen kan konstrueres som incidensgrafen for et delvist lineært rum , som er det eneste ottekantfrie tredobbelte dække af de generaliserede firkanter GQ (2,2) . Grafen er opkaldt efter Ronald Foster , som kompilerede en liste over kubiske symmetriske grafer ( Foster's list ), som inkluderer Foster-grafen.

Algebraiske egenskaber

Automorfigruppen i Foster-grafen er en gruppe af orden 4320 [4] . Den virker transitivt på grafens spidser og kanter, så Foster-grafen er symmetrisk . Grafen har automorfier, der kortlægger ethvert toppunkt til en hvilken som helst anden og enhver kant til enhver anden kant. I Foster-listen er Foster -grafen, angivet som F90A, den eneste kubiske symmetriske graf med 90 hjørner [5] .

Det karakteristiske polynomium i Foster-grafen er .

Galleri

Noter

  1. ↑ Weisstein, Eric W. Foster Graph  på Wolfram MathWorld- webstedet .
  2. ↑ A.E. Brouwer, A.M. Cohen, A. Neumaier. Afstand—Regulære grafer. - New York: Springer-Verlag, 1989.
  3. ↑ Kubikafstand-regulære grafer Arkiveret 1. juli 2014 på Wayback Machine , A. Brouwer.
  4. ↑ Royle, G. F090A data  (downlink)
  5. ↑ M. Conder, P. Dobcsányi, "Trivalente symmetriske grafer op til 768 hjørner." J. Combin. Matematik. Forene. Comput. 40, 41-63, 2002.

Litteratur