Arc-transitive (symmetric): automorphism group acts transitively on ordered pairs (arcs). Strongest standard symmetry: arc-transitive → vertex-transitive AND edge-transitive. K_n, Petersen, hypercube are arc-transitive. s-arc-transitive: transitivity on walks of length s.
How to Use
Select graph:
- Test: Arc-transitive?
- s-arc: Walk length
- Implies: VT + ET
s-Arc Transitivity
s-arc-transitive: transitive on walks (v₀,v₁,...,vₛ) of length s with vᵢ≠vᵢ₊₂. Tutte (1947): cubic arc-transitive graphs are at most 5-arc-transitive! Weiss (1981): for valency ≥3, at most 7-arc-transitive. Deep results.
Foster Census
Foster census: complete list of cubic arc-transitive graphs. Started by Ronald Foster (1932). Contains all cubic symmetric graphs up to large orders. Fundamental reference for algebraic graph theory.
Step-by-Step Instructions
- 1Select graph.
- 2Check arcs.
- 3Determine s-value.
- 4Compare VT/ET.
- 5Classify symmetry.