Grafo de Biggs-Smith

Origem: Wikipédia, a enciclopédia livre.
Ir para: navegação, pesquisa
Grafo de Biggs–Smith
Biggs-Smith graph.svg

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

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]

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[editar | editar código-fonte]

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 é: (x-3) (x-2)^{18} x^{17} (x^2-x-4)^9 (x^3+3 x^2-3)^{16}.

Galeria[editar | editar código-fonte]

Referências

  1. Eric W. Weisstein, Biggs–Smith Graph em MathWorld
  2. Brouwer, A. E.; Cohen, A. M.; and Neumaier, A. Distance-Regular Graphs. New York: Springer-Verlag, 1989.
  3. Royle, G. F102A data
  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