Grafo semissimétrico
No campo da matemática da teoria dos grafos, um grafo semissimétrico é um grafo não-direcionado que é aresta-transitivo e regular, mas não é vértice transitivo.
Em outras palavras, um grafo é semissimétrico se cada vértice tem o mesmo número de arestas incidentes, e há uma simetria tomando qualquer das suas arestas para quaisquer outras de suas arestas, mas há algum par de vértices que não podem ser mapeados entre si por uma simetria. Um grafo semissimétrico deve ser bipartido e seu grupo de automorfismo deve agir transitivamente em cada um dos dois conjuntos de vértices da bipartição. No diagrama da direita, os vértices verdes não podem ser mapeados para os vermelhos por qualquer automorfismo.
Grafos semissimétricos foram primeiramente estudados por Jon Folkman em 1967, que descobriu o menor grafo semissimétrico, o grafo de Folkman em 20 vértices[1].
O menor grafo cúbico semissimétrico é o grafo de Gray em 54 vértices. Foi observado pela primeira vez que era semissimétrico por Bouwer em 1968.[2] Foi provado ser o menor grafo cúbico semissimétrico por Dragan Marušič e Aleksander Malnič[2] .
Todos os grafos cúbicos semissimétricos de até 768 vértices são conhecidos. Segundo Malnič, Marušič e Potočnik, os quatro menores grafos cúbicos semissimétricos possíveis, após o grafo de Gray são o grafo de Iofinova-Ivanov em 110 vértices, o grafo de Ljubljana em 112 vértices,[3] um grafo de 120 vértices com cintura 8 e a gaiola-12 de Tutte.[4]
Referências
- ↑ FOLKMAN, J (1967). «Regular line-symmetric graphs». Journal of Combinatorial Theory. 3. pp. 215–232. doi:10.1016/S0021-9800(67)80069-3
- ↑ a b BOUWER, I. Z. (1968). «An edge but not vertex transitive cubic graph». Bulletin of the Canadian Mathematical Society. 11. pp. 533–535
- ↑ Conder, M.; Malnič, A.; Marušič, D.; Pisanski, T.; Potočnik, P. (2002), «The Ljubljana Graph» (PDF), Ljubljana: Institute of Mathematics, Physics and Mechanics, IMFM Preprints, 40 (845)
- ↑ Conder, Marston; Malnič, Aleksander; Marušič, Dragan; Potočnik, Primož (2006). «A census of semisymmetric cubic graphs on up to 768 vertices». Journal of Algebraic Combinatorics. 23. pp. 255–294. doi:10.1007/s10801-006-7397-3.