Grafo de Biggs-Smith

No campo da matemática da teoria dos grafos o grafo de Biggs–Smith é um grafo não-orientado 3-regular com 102 vértices e 153 arestas.[1]

Grafo de Biggs–Smith


O grafo de Biggs–Smith
vértices 102
arestas 153
Raio 7
Diâmetro 7
Cintura 9
Automorfismos 2448 (PGL(2,17))
Número cromático 3
Índice cromático 3
Propriedades Cúbico
Hamiltoniano
simétrico
distância-regular

Ele tem número cromático 3, índice cromático 3, raio 7, diâmetro 7 e cintura 9. É tanto 3-vértice-conectado quanto 3-aresta-conectado.

Todos os grafos distância-regular cúbicos são conhecidos.[2] O grafo Biggs–Smith é um destes 13 grafos.

Propriedades algébricas

O grupo de automorfismo do grafo de Biggs–Smith é um grupo de ordem 2448[3] isomórfico ao PGL(2,17). Ele age transitivamente sobre os vértices, nas arestas e nos arcos do grafo. Portanto, o grafo de Biggs–Smith é im grafo simétrico. Ele tem automorfismos que levam qualquer vértice para qualquer outro vértice e qualquer aresta para qualquer outra aresta. De acordo com o censo de Foster, o grafo de Biggs-Smith, referenciado como F102A, é o único grafo cúbico simétrico em 102 vértices.[4]

O grafo de Biggs–Smith é também singularmente determinado por seu espectro de grafo, o conjunto de autovalores do grafo de sua matriz de adjacência.[5]

O polinômio característico do grafo de Biggs–Smith é: .

Galeria

Referências
  1. Weisstein, Eric W. «Biggs–Smith Graph» (em inglês). MathWorld
  2. Brouwer, A. E.; Cohen, A. M.; and Neumaier, A. Distance-Regular Graphs. New York: Springer-Verlag, 1989.
  3. Royle, G. F102A data[ligação inativa]
  4. Conder, M. and Dobcsányi, P. "Trivalent Symmetric Graphs Up to 768 Vertices." J. Combin. Math. Combin. Comput. 40, 41–63, 2002
  5. E. R. van Dam and W. H. Haemers, Spectral Characterizations of Some Distance-Regular Graphs. J. Algebraic Combin. 15, pages 189–202, 2003
This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.