En el campo matemático de la teoría de grafos , un grafo semitransitivo es un grafo que es tanto transitivo de vértice como de borde transitivo , pero no simétrico . [1] En otras palabras, un grafo es semitransitivo si su grupo de automorfismo actúa transitivamente tanto en sus vértices como en sus aristas, pero no sobre pares ordenados de vértices enlazados.
Familias de gráficos definidas por sus automorfismos | ||||
---|---|---|---|---|
distancia-transitiva | → | distancia regular | ← | muy regular |
↓ | ||||
simétrico (arco-transitivo) | ← | t -transitivo, t ≥ 2 | simétrico sesgado | |
↓ | ||||
(si está conectado) vértice y borde transitivo | → | edge-transititive y regular | → | borde transitivo |
↓ | ↓ | ↓ | ||
vértice-transitivo | → | regular | → | (si es bipartito) birregular |
↑ | ||||
Gráfico de Cayley | ← | simétrico cero | asimétrico |
Cada conectado grafo simétrico debe ser vértice-transitivo y borde-transitivo , y lo contrario es cierto para los gráficos de grado impar, [2] por lo que no existen que gráficos medio-transitivo de grado impar. Sin embargo, existen gráficos semitransitivos de grado par. [3] El gráfico semitransitivo más pequeño es el gráfico de Holt , con vértices de grado 4 y 27. [4] [5]
Referencias
- ^ Bruto, JL; Yellen, J. (2004). Manual de teoría de grafos . Prensa CRC. pag. 491. ISBN 1-58488-090-2.
- ^ Babai, L. (1996). "Grupos de automorfismo, isomorfismo, reconstrucción" . En Graham, R; Grötschel, M ; Lovász, L (eds.). Manual de combinatoria . Elsevier.
- ^ Bouwer, Z. "Gráficos transitivos de vértice y borde, pero no 1-transitivos". Canad. Matemáticas. Toro. 13, 231-237, 1970.
- ^ Biggs, Norman (1993). Teoría de grafos algebraicos (2ª ed.). Cambridge: Cambridge University Press. ISBN 0-521-45897-8.
- ^ Holt, Derek F. (1981). "Un gráfico que es transitivo de borde pero no transitivo de arco". Revista de teoría de grafos . 5 (2): 201–204. doi : 10.1002 / jgt.3190050210 ..