Half-transitive graph¶
A finite undirected graph whose full automorphism group is transitive on vertices and edges but not on ordered adjacent pairs.
Core Idea¶
A half-transitive graph is a finite undirected graph that is equally symmetric at its vertices and undirected edges but not at its directed edges. More exactly, its full automorphism group can map any vertex to any other and any undirected edge to any other, but it cannot map every ordered adjacent pair, or arc, to every other arc.[ref-1758e5cc8695][ref-e8fc1427c370]
Every edge has two possible directions. In this graph type the arcs form two complementary symmetry orbits: no automorphism reverses an edge. Either orbit can be chosen as a consistent invariant orientation, but the bare graph does not choose one as forward.[^ref-5d275782389a]
What It Is Not¶
One vertex orbit alone is not enough; one undirected-edge orbit is also required. A graph with only one arc orbit has more symmetry and is arc-transitive, so it is outside this class. A proper subgroup with the three conditions does not settle the result: the full automorphism group must be checked. A degree-four drawing or a visually uniform layout is not a substitute for an automorphism proof.[^ref-e8fc1427c370]
Scope of Application¶
Graph theorists use the concept to classify and construct highly symmetric finite graphs. A construction can yield different classifications for different parameter choices; the half-transitive label applies only where vertex and edge transitivity and failure of arc transitivity are established. Bouwer proves a specified even-degree family, while later work studies another parameter-restricted family.[ref-1758e5cc8695][ref-e8fc1427c370]
Clarity¶
Ask three questions of the same full automorphism group: Are all vertices in one orbit? Are all undirected edges in one orbit? Are ordered adjacent pairs in more than one orbit? The answers must be yes, yes, yes. Under the first two conditions, the last answer means exactly two arc orbits.[ref-1758e5cc8695][ref-5d275782389a]
Manages Complexity¶
The classification reduces many possible vertex, edge, and arc comparisons to three orbit tests. Proofs can establish those orbit counts from a graph construction rather than checking every possible mapping separately. Even degree follows for connected instances from the orbit conditions and the odd-degree obstruction; even degree alone does not prove membership.[^ref-1758e5cc8695]
Abstract Reasoning¶
If an automorphism reversed one edge while all undirected edges lay in one orbit, the group could also relate the two directions throughout the graph; the arcs would form one orbit. Thus a half-transitive graph cannot have such a reversal. Conversely, losing vertex or edge transitivity also takes a graph out of the class. The name picks out a narrow boundary of symmetry rather than a general property of regular graphs.[^ref-5d275782389a]
Knowledge Transfer¶
The same three-orbit test applies to graphs built in different ways. Use the full automorphism action, not a familiar graph name or similar appearance, to recognize a new case. This is why Holt/Doyle and Bouwer's X(2,6,9) qualify by the same definition despite having different numbers of vertices.[ref-5d275782389a][ref-1758e5cc8695]
Example¶
The Holt graph, also described by Doyle, has 27 vertices and degree four. Its full automorphism group is vertex- and edge-transitive but not arc-transitive; Holt and Doyle name the same graph here.[^ref-5d275782389a] Bouwer's X(2,6,9) has 54 vertices and degree four. His Proposition 1 proves vertex and edge transitivity, and Proposition 2 proves failure of 1-transitivity for this parameter choice.[^ref-1758e5cc8695] Both fill the same three-orbit pattern, though they are distinct graphs. Later work concludes that 27 is the smallest possible number of vertices; Doyle's original manuscript only called that likely.[ref-e8fc1427c370][ref-5d275782389a]
Relationships to Other Abstractions¶
Current abstraction Half-transitive graph Domain-specific
Parents (1) — more general patterns this builds on
-
Half-transitive graph presupposes Symmetry Prime
The graph's orbit conditions require adjacency-preserving symmetry action, but the graph is not a kind of symmetry.
Hierarchy path (1) — routes to 1 parentless root
- Half-transitive graph → Symmetry
Neighborhood in Abstraction Space¶
Half-transitive graph sits in a sparse region of the domain-specific corpus (65th percentile for distinctiveness): few abstractions share its structure, so a faithful description tends to retrieve it precisely.
Family — Graph Classes & Invariants (39 abstractions)
Nearest neighbors
- Zero-symmetric graph — 0.86
- Asymmetric graph — 0.86
- Semi-symmetric graph — 0.86
- Skew-symmetric graph — 0.85
- Block Graph — 0.82
Computed from structural-signature embeddings · 2026-10-17
Not to Be Confused With¶
A semi-symmetric graph has edge transitivity but lacks vertex transitivity. A zero-symmetric graph has a different edge-orbit pattern. A symmetric or arc-transitive graph has one arc orbit. The classification concerns full graph automorphisms, not a chosen subgroup or an arrow assignment added to a drawing.
References¶
[^ref-1758e5cc8695]: I. Z. Bouwer, “Vertex and Edge Transitive, but not 1-Transitive, Graphs”, Canadian Mathematical Bulletin 13(2) (1970), 231–237, DOI 10.4153/CMB-1970-047-8. Publisher-hosted original PDF inspected, especially pp. 231–232 and 236–237. [^ref-5d275782389a]: Peter G. Doyle, “A 27-vertex graph that is vertex-transitive and edge-transitive but not 1-transitive”, manuscript based on a June 1976 Harvard thesis, revised 1985 and posted as arXiv:math/0703861. Author manuscript inspected, pp. 1–5. [^ref-e8fc1427c370]: Brian Alspach, Dragan Marušič and Lewis Nowitz, “Constructing graphs which are ½-transitive”, Journal of the Australian Mathematical Society 56(3) (1994), 391–402, DOI 10.1017/S1446788700035564. Publisher-hosted original PDF inspected, especially pp. 391–393.