Grafo de Folkman

Origem: Wikipédia, a enciclopédia livre.
Ir para: navegação, pesquisa
Grafo de Folkman
Folkman graph alt.svg

O grafo de Folkman
Nomeado em honra a J. Folkman
vértices 20
arestas 40
Raio 3
Diâmetro 4
Cintura 4
Número cromático 2
Índice cromático 4
Propriedades Perfeito
Hamiltoniano
Semi-simétrico
Bipartido
Regular
Euleriano

No campo da matemática da teoria dos grafos o grafo de Folkman, nomeado em honra a Jon Folkman, é um grafo bipartido 4-regular com 20 vértices e 40 arestas.1

O grafo de Folkman é Hamiltoniano e tem número cromático 2, índice cromático 4, raio 3, diâmetro 4 e cintura 4. e é um grafo perfeito tanto 4-vértice-conectado quanto 4-aresta-conectado.

Propriedades algébricas[editar | editar código-fonte]

O grupo de automorfismo do grafo de Folkman age transitivamente em suas arestas, mas não em seus vértices. É o menor grafo não direcionado, que é aresta-transitivo e regular, mas não é vértice-transitivo.2 Esses grafos são chamados semi-simétricos e foram estudados pela primeira vez por Folkman em 1967 que descobriu o grafo de 20 vértices, que agora é nomeado em sua honra.3

Como um grafo semi-simétrico, o gráfico de Folkman é bipartido, e seu grupo de automorfismo age transitivamente em cada um dos dois conjuntos de vértices da bipartição. No diagrama abaixo, indicando o número cromático do grafo, os vértices verdes não podem ser mapeados para os vermelhos por qualquer automorfismo, mas qualquer vértice vermelho pode ser mapeado em qualquer outro vértice vermelho e qualquer vértice verde pode ser mapeado em qualquer outro vértice verde.

O polinômio característico do grafo de Folkman é (x-4) x^{10} (x+4) (x^2-6)^4.

Galeria[editar | editar código-fonte]

Referências

  1. Eric W. Weisstein, Folkman graph em MathWorld
  2. Skiena, S. Implementing Discrete Mathematics: Combinatorics and Graph Theory with Mathematica. Reading, MA: Addison-Wesley, pp. 186-187, 1990
  3. FOLKMAN, J.. (1967). "Regular line-symmetric graphs". Journal of Combinatorial Theory 3: 215–232. DOI:10.1016/S0021-9800(67)80069-3.