Hubbry Logo
Symmetric graphSymmetric graphMain
Open search
Symmetric graph
Community hub
Symmetric graph
logo
8 pages, 0 posts
0 subscribers
Be the first to start a discussion here.
Be the first to start a discussion here.
Symmetric graph
Symmetric graph
Symmetric graph
View on Wikipedia
from Wikipedia
The Petersen graph is a (cubic) symmetric graph. Any pair of adjacent vertices can be mapped to another by an automorphism, since any five-vertex ring can be mapped to any other.

In the mathematical field of graph theory, a graph G is symmetric or arc-transitive if, given any two ordered pairs of adjacent vertices and of G, there is an automorphism

such that

and [1]

In other words, a graph is symmetric if its automorphism group acts transitively on ordered pairs of adjacent vertices (that is, upon edges considered as having a direction).[2] Such a graph is sometimes also called 1-arc-transitive[2] or flag-transitive.[3]

By definition (ignoring u1 and u2), a symmetric graph without isolated vertices must also be vertex-transitive.[1] Since the definition above maps one edge to another, a symmetric graph must also be edge-transitive. However, an edge-transitive graph need not be symmetric, since a—b might map to c—d, but not to d—c. Star graphs are a simple example of being edge-transitive without being vertex-transitive or symmetric. As a further example, semi-symmetric graphs are edge-transitive and regular, but not vertex-transitive.

Graph families defined by their automorphisms
distance-transitive → distance-regular ← strongly regular
↓
symmetric (arc-transitive) ← t-transitive, t ≥ 2 skew-symmetric
↓
(if connected)
vertex- and edge-transitive 		→ edge-transitive and regular → edge-transitive
↓ ↓ ↓
vertex-transitive → regular → (if bipartite)
biregular
↑
Cayley graph ← zero-symmetric asymmetric

Every connected symmetric graph must thus be both vertex-transitive and edge-transitive, and the converse is true for graphs of odd degree.[3] However, for even degree, there exist connected graphs which are vertex-transitive and edge-transitive, but not symmetric.[4] Such graphs are called half-transitive.[5] The smallest connected half-transitive graph is Holt's graph, with degree 4 and 27 vertices.[1][6] Confusingly, some authors use the term "symmetric graph" to mean a graph which is vertex-transitive and edge-transitive, rather than an arc-transitive graph. Such a definition would include half-transitive graphs, which are excluded under the definition above.

A distance-transitive graph is one where instead of considering pairs of adjacent vertices (i.e. vertices a distance of 1 apart), the definition covers two pairs of vertices, each the same distance apart. Such graphs are automatically symmetric, by definition.[1]

A t-arc is defined to be a sequence of t + 1 vertices, such that any two consecutive vertices in the sequence are adjacent, and with any repeated vertices being more than 2 steps apart. A t-transitive graph is a graph such that the automorphism group acts transitively on t-arcs, but not on (t + 1)-arcs. Since 1-arcs are simply edges, every symmetric graph of degree 3 or more must be t-transitive for some t, and the value of t can be used to further classify symmetric graphs. The cube is 2-transitive, for example.[1]

Note that conventionally the term "symmetric graph" is not complementary to the term "asymmetric graph," as the latter refers to a graph that has no nontrivial symmetries at all.

Examples

[edit]

Two basic families of symmetric graphs for any number of vertices are the cycle graphs (of degree 2) and the complete graphs. Further symmetric graphs are formed by the vertices and edges of the regular and quasiregular polyhedra: the cube, octahedron, icosahedron, dodecahedron, cuboctahedron, and icosidodecahedron. Extension of the cube to n dimensions gives the hypercube graphs (with 2n vertices and degree n). Similarly extension of the octahedron to n dimensions gives the graphs of the cross-polytopes, this family of graphs (with 2n vertices and degree 2n − 2) are sometimes referred to as the cocktail party graphs - they are complete graphs with a set of edges making a perfect matching removed. Additional families of symmetric graphs with an even number of vertices 2n, are the evenly split complete bipartite graphs Kn,n and the crown graphs on 2n vertices. Many other symmetric graphs can be classified as circulant graphs (but not all).

The Rado graph forms an example of a symmetric graph with infinitely many vertices and infinite degree.

Cubic symmetric graphs

[edit]

Combining the symmetry condition with the restriction that graphs be cubic (i.e. all vertices have degree 3) yields quite a strong condition, and such graphs are rare enough to be listed. They all have an even number of vertices. The Foster census and its extensions provide such lists.[7] The Foster census was begun in the 1930s by Ronald M. Foster while he was employed by Bell Labs,[8] and in 1988 (when Foster was 92[1]) the then current Foster census (listing all cubic symmetric graphs up to 512 vertices) was published in book form.[9] The first thirteen items in the list are cubic symmetric graphs with up to 30 vertices[10][11] (ten of these are also distance-transitive; the exceptions are as indicated):

Vertices Diameter Girth Graph Notes
4 1 3 The complete graph K4 distance-transitive, 2-arc-transitive
6 2 4 The complete bipartite graph K3,3 distance-transitive, 3-arc-transitive
8 3 4 The vertices and edges of the cube distance-transitive, 2-arc-transitive
10 2 5 The Petersen graph distance-transitive, 3-arc-transitive
14 3 6 The Heawood graph distance-transitive, 4-arc-transitive
16 4 6 The Möbius–Kantor graph 2-arc-transitive
18 4 6 The Pappus graph distance-transitive, 3-arc-transitive
20 5 5 The vertices and edges of the dodecahedron distance-transitive, 2-arc-transitive
20 5 6 The Desargues graph distance-transitive, 3-arc-transitive
24 4 6 The Nauru graph (the generalized Petersen graph G(12,5)) 2-arc-transitive
26 5 6 The F26A graph[11] 1-arc-transitive
28 4 7 The Coxeter graph distance-transitive, 3-arc-transitive
30 4 8 The Tutte–Coxeter graph distance-transitive, 5-arc-transitive

Other well known cubic symmetric graphs are the Dyck graph, the Foster graph and the Biggs–Smith graph. The ten distance-transitive graphs listed above, together with the Foster graph and the Biggs–Smith graph, are the only cubic distance-transitive graphs.

Properties

[edit]

The vertex-connectivity of a symmetric graph is always equal to the degree d.[3] In contrast, for vertex-transitive graphs in general, the vertex-connectivity is bounded below by 2(d + 1)/3.[2]

A t-transitive graph of degree 3 or more has girth at least 2(t − 1). However, there are no finite t-transitive graphs of degree 3 or more for t ≥ 8. In the case of the degree being exactly 3 (cubic symmetric graphs), there are none for t ≥ 6.

See also

[edit]

References

[edit]
[edit]
Revisions and contributorsEdit on WikipediaRead on Wikipedia

Symmetric graph

View on Grokipedia
from Grokipedia
In , a is defined as a whose acts transitively on both its vertices and edges, meaning any vertex can be mapped to any other vertex and any edge to any other edge via graph automorphisms. This high degree of implies that the graph is vertex-transitive (every pair of vertices is equivalent under automorphism) and edge-transitive (every pair of edges is equivalent), and the converse also holds, as vertex-transitivity implies regularity. Note that in some modern literature, "symmetric graph" specifically refers to arc-transitive graphs (transitive on directed edges), though the term has historically been used for vertex- and edge-transitive graphs, leading to terminological variation. Symmetric graphs exhibit several notable properties that stem from their transitive actions. They are always regular, with all vertices having the same degree, and if not arc-transitive (transitive on directed edges, or arcs), they must have even degree. A classic example is the KnK_n for n≥3n \geq 3, which is symmetric due to its full allowing any permutation of vertices. Other examples include cycle graphs CnC_n for n≥3n \geq 3, the octahedral graph, and the Doyle graph on 27 vertices, which is quartic, symmetric, but notably not arc-transitive. The study of symmetric graphs is intertwined with related concepts, such as semisymmetric graphs, which are regular and edge-transitive but not vertex-transitive, and arc-transitive graphs. These graphs play a key role in , , and the classification of highly symmetric structures, with ongoing research focusing on their quotients, extensions, and s-arc-transitive variants for s≥1s \geq 1.

Fundamentals

Definition

In , a is a connected, undirected graph whose acts transitively on the set of arcs, where an arc is an of adjacent vertices (u,v)(u, v) with uv∈E(G)uv \in E(G). This transitivity condition implies that for any two arcs (u,v)(u, v) and (x,y)(x, y), there exists an ϕ∈\Aut(G)\phi \in \Aut(G) such that ϕ(u)=x\phi(u) = x and ϕ(v)=y\phi(v) = y, ensuring a high degree of in the graph's structure. Arc-transitivity implies both vertex-transitivity and edge-transitivity, and thus that the graph is regular (all vertices have the same degree). The requirement for connectedness distinguishes from potentially disconnected structures, as arc transitivity presupposes a unified component to enable such mappings. The term "symmetric" reflects the balanced and equitable action of the , mirroring the graph's structural uniformity across directed adjacencies. This definition is stronger than vertex-transitivity, in which the acts only on the vertices themselves.

Terminology Variations

The term "symmetric graph" has experienced variations in usage across the literature, leading to potential ambiguities in interpretation. In historical contexts, particularly in works from the mid-20th century and into the early , "symmetric" was often applied to graphs that are both vertex-transitive and edge-transitive, without necessitating full arc-transitivity. For instance, this broader sense appears in early contributions such as Sabidussi's paper on graph multiplication, where symmetry emphasizes transitivity on vertices and edges but not necessarily on directed edges (arcs). Such definitions aligned with foundational studies on groups and transitivity properties, reflecting a time when higher-order transitivity concepts were less standardized. In modern conventions, however, the term "symmetric graph" has converged on a more precise meaning: a graph whose automorphism group acts transitively on its arcs (ordered pairs of adjacent vertices), also known as 1-arc-transitive. This standard is explicitly adopted in influential texts like Biggs' Algebraic Graph Theory (1993), which defines a symmetric graph as one where the automorphism group is transitive on the set of arcs. Similarly, Godsil and Royle (2001) equate symmetric graphs with 1-arc-transitive graphs, reinforcing this as the primary definition in contemporary algebraic graph theory. This shift underscores arc-transitivity as essential for capturing the full symmetry of edge orientations, distinguishing it from mere vertex- and edge-transitivity. An equivalent formulation emphasizes "flag-transitivity," where the automorphism group acts transitively on flags—incident triples consisting of a vertex, an adjacent edge, and the other endpoint. This terminology highlights the structural uniformity on vertex-edge incidences and is used interchangeably with arc-transitivity in discussions of symmetric graphs. The flag-transitive perspective is particularly useful in geometric and incidence structure contexts, but it aligns precisely with the arc-transitive definition for simple undirected graphs. These terminological differences, especially in pre-1990s sources, can introduce ambiguity when reviewing older literature; for example, a graph described as symmetric in a 1970s paper might lack arc-transitivity by today's standards. To mitigate confusion, researchers recommend explicitly stating the transitivity level (e.g., vertex-, edge-, or arc-transitive) alongside the term "symmetric," ensuring clarity in applications ranging from algebraic constructions to computational enumerations.

Transitivity Hierarchy

Vertex and Edge Transitivity

A is one whose acts transitively on the set of vertices, meaning that for any pair of vertices, there exists an mapping one to the other. This property ensures that all vertices are indistinguishable in terms of their structural roles within the graph. Similarly, an edge-transitive graph is defined by the acting transitively on the set of edges, allowing any edge to be mapped to any other via an . These transitivity conditions form the foundational levels of symmetry in , capturing uniformity at the level of vertices or edges without considering directionality. Arc-transitive graphs are necessarily both vertex-transitive and edge-transitive for connected graphs, as the stronger action on directed edges () implies transitivity on the underlying undirected elements. In the context of symmetric graphs, defined as regular vertex- and edge-transitive graphs, arc-transitivity represents a stricter condition. Conversely, for regular graphs of odd degree, the properties of being vertex-transitive and edge-transitive together imply arc-transitivity, establishing a direct equivalence in this case. This converse result highlights a key distinction, as even-degree graphs can exhibit vertex and edge transitivity without achieving the higher symmetry of arc transitivity. A classic illustration is the C5C_5, the 5-cycle forming a , which serves as a connected of odd order. This graph is vertex-transitive, as rotations and reflections of the map any vertex to any other; edge-transitive, since any edge can be mapped to any other under these symmetries; and arc-transitive, demonstrating all three properties simultaneously as a symmetric graph. Arc transitivity represents a stricter condition that builds upon vertex and edge transitivity by requiring transitivity on ordered pairs of adjacent vertices.

Arc Transitivity and Flags

Arc transitivity extends the concepts of vertex and edge transitivity by considering directed edges, known as . An arc in a graph is an ordered pair of adjacent vertices (u, v), where u and v are distinct and connected by an edge. A graph is arc-transitive if its acts transitively on the set of arcs, meaning that for any two arcs, there exists an mapping one to the other. This property ensures that the graph's structure is highly symmetric with respect to oriented edges. A in a graph is defined as an incident triple consisting of a vertex u, an edge e incident to u, and another vertex v incident to e, effectively representing an oriented incidence (u, e, v) where e = {u, v}. For connected graphs, arc transitivity is equivalent to transitivity, as the acting transitively on implies transitivity on such incident triples, and vice versa. To generalize this symmetry, the notion of t- is introduced. A t-arc is a sequence of t+1 distinct vertices (v_0, v_1, \dots, v_t) such that v_i is adjacent to v_{i+1} for each i from 0 to t-1, with no repetitions in the sequence. A graph is 1-arc-transitive if its acts transitively on the set of 1-, which are simply the arcs. By definition, 1-arc-transitive graphs are symmetric, as this transitivity on arcs, combined with the connectedness of the graph, implies both vertex transitivity and edge transitivity.

Core Properties

Automorphism Group Actions

In , the Γ(G)\Gamma(G) of a graph GG consists of all permutations of the vertex set that preserve adjacency relations, forming a of the on the vertices. For a GG, defined as a whose acts transitively on both vertices and edges, Γ(G)\Gamma(G) acts transitively on the vertex set V(G)V(G), meaning any vertex can be mapped to any other by some , and transitively on the edge set E(G)E(G), meaning any edge can be mapped to any other. This dual transitivity, combined with regularity, distinguishes from merely vertex-transitive or edge-transitive ones. The transitive action on vertices implies, by the orbit-stabilizer theorem, that the order of the satisfies ∣Γ(G)∣=n⋅∣Γv∣|\Gamma(G)| = n \cdot |\Gamma_v|, where n=∣V(G)∣n = |V(G)| and Γv\Gamma_v is the stabilizer of a fixed vertex vv. Similarly, for the action on edges, ∣Γ(G)∣=m⋅∣Γe∣|\Gamma(G)| = m \cdot |\Gamma_e|, where m=∣E(G)∣m = |E(G)| and Γe\Gamma_e is the stabilizer of a fixed edge ee. Since GG is regular of degree dd, m=nd/2m = n d / 2, providing a relation between the stabilizers. In general, the vertex stabilizer Γv\Gamma_v does not necessarily act transitively on the neighbors of vv; such transitivity would make the graph arc-transitive, a stronger property not required for symmetry.

Connectivity and Diameter

In a connected symmetric graph GG of degree dd, the vertex-connectivity κ(G)\kappa(G) equals dd. This equality holds because symmetric graphs are edge-transitive, and connected edge-transitive graphs have vertex-connectivity equal to their degree. The edge-connectivity of such a graph also equals dd, a consequence of Mader's theorem establishing maximal edge-connectivity for connected vertex-transitive graphs. Symmetric graphs frequently exhibit small , which contribute to their utility in network designs requiring efficient paths; however, no universal bound on the exists without additional structural assumptions, as evidenced by ongoing efforts to maximize order for fixed degree and in the degree-diameter problem. For example, the KnK_n, a symmetric graph of degree n−1n-1, has vertex-connectivity n−1n-1, aligning precisely with its degree.

Geometric and Structural Constraints

Girth Bounds

The girth of a graph is defined as the length of its shortest cycle. Symmetric graphs, being regular of degree at least 2, have girth at least 3. For arc-transitive symmetric graphs, which are 1-arc-transitive, the acts transitively on arcs, imposing structural constraints on cycle lengths. A fundamental result states that a t-arc-transitive graph of degree at least 3 has girth g≥2t+1g \geq 2t + 1. This bound arises because transitivity on t-arcs prevents short cycles of length at most 2t2t, as such cycles would allow extensions to (t+1)-arcs, contradicting the assumption unless the graph is complete or has multiple edges. For arc-transitive symmetric graphs (t=1t=1), this yields g≥3g \geq 3, achieved by complete graphs KnK_n for n≥3n \geq 3; non-complete examples typically exhibit higher girth. The Weiss conjecture, resolved affirmatively, states that there are only finitely many cubic s-arc-transitive graphs for each fixed s≥7s \geq 7. This has implications for cubic symmetric graphs (in the arc-transitive sense). The Foster census enumerates all connected cubic symmetric graphs up to 512 vertices, including those of girth 7 such as the McGee graph (24 vertices). Extended computational enumerations, such as Conder's list up to 10,080 vertices, identify additional larger examples of girth 7, confirming ongoing existence beyond initial limits. These results highlight how high transitivity restricts but does not eliminate large symmetric graphs with specific girth values.

Cycle and Path Properties

In arc-transitive symmetric graphs, the acts transitively on the set of all cycles of a given length greater than or equal to the girth, ensuring that all such cycles are equivalent under the group's action. This property follows from arc-transitivity, which allows mapping any directed segment of a cycle to that of another via automorphisms, preserving the overall structure. The of an arc-transitive symmetric graph also exhibits path transitivity for paths up to certain s, mapping any path of fixed between vertices at a fixed to any other such path. This transitivity extends arc-transitivity to longer paths, with the action determined by the s-arc-transitivity level of the graph, where s indicates the maximum path for which directed paths are transitive. Many symmetric graphs are Hamiltonian, containing a cycle that visits each vertex exactly once, a property bolstered by their vertex-transitivity. The Lovász posits that every connected contains a Hamilton cycle, with partial results confirming this for infinite families of symmetric graphs, such as certain cubic arc-transitive graphs. In arc-transitive symmetric graphs, the number of cycles of length kk can be enumerated using the orbit-stabilizer theorem applied to the group's action, yielding ∣\Aut(G)∣2k∣\Stabv∣\frac{|\Aut(G)|}{2k |\Stab_v|} under conditions where the stabilizer of a cycle consists of the of order 2k2k acting faithfully alongside the vertex stabilizer \Stabv\Stab_v. Notable exceptions to Hamiltonicity exist among symmetric graphs, such as the , which is cubic symmetric and 3-arc-transitive yet non-Hamiltonian; proofs leverage the arc-transitivity to show that assuming a Hamilton cycle leads to a contradiction with the graph's girth and diameter properties. Non-arc-transitive symmetric graphs, which exist only for even degree at least 4, do not necessarily satisfy the above cycle and path transitivity properties, though they remain regular and transitive on vertices and edges.

Examples

Infinite Families

Cycle graphs CnC_n for n≥3n \geq 3 form an infinite family of 2-regular symmetric graphs, where each graph consists of nn vertices connected in a single cycle. These graphs are constructed as the 1-skeleton of a regular nn-gon, and their is the DnD_n of order 2n2n, which acts arc-transitively on the vertices and edges. Complete graphs KnK_n for n≥2n \geq 2 constitute another fundamental infinite family of symmetric graphs, with every pair of distinct vertices adjacent, resulting in (n−1)(n-1)-regular graphs of order nn. The of KnK_n is the SnS_n, which acts fully transitively on vertices, edges, and arcs, making these graphs arc-transitive for all nn. Hypercube graphs QdQ_d for dimensions d≥1d \geq 1 provide an infinite family of dd-regular bipartite symmetric graphs with 2d2^d vertices, where vertices correspond to binary strings of length dd and edges connect strings differing in exactly one bit. The of QdQ_d is the hyperoctahedral group of order d!⋅2dd! \cdot 2^d, acting vertex-transitively, edge-transitively, and arc-transitively on the graph. The odd graphs OkO_k for k≥2k \geq 2 form an infinite family of symmetric graphs generalizing the (O3O_3), with vertices representing the (k−1)(k-1)-subsets of a 2k−12k-1-element set and edges between disjoint subsets. These graphs are distance-transitive with automorphism group isomorphic to S2k−1S_{2k-1}, ensuring arc-transitivity, and they exhibit high symmetry with girth 5 and diameter kk. The , also known as the countable infinite , is the unique (up to ) countable infinite symmetric graph satisfying the extension property: for any two disjoint finite subsets UU and VV of vertices, there exists a vertex adjacent to all in UU and none in VV. Its is simple and has 2ℵ02^{\aleph_0}, acting homogeneously and thus arc-transitively on the graph. A broad construction method for infinite families of symmetric graphs involves Cayley graphs of infinite groups with symmetric generating sets, where the left regular action of the group on itself induces vertex-transitivity, and suitable choices of generators ensure edge- and arc-transitivity. For finite-degree examples, Cayley graphs of symmetric groups or dihedral groups with generators often yield arc-transitive graphs.

Small Finite Examples

The K4K_4 is the smallest non-trivial symmetric graph, consisting of 4 vertices each connected to the other three, yielding 6 edges and a girth of 3. Its is the S4S_4 of order 24, acting transitively on vertices, edges, and arcs. This graph can be visualized as a , with vertices at the corners and edges along the faces. The is an iconic cubic symmetric graph with 10 vertices, 15 edges, and girth 5, serving as the (3,5)-cage. Its vertices correspond to the 2-element subsets of a 5-element set, with edges connecting disjoint subsets. The is the S5S_5 of order 120, acting distance-transitively. It is often depicted as an outer with an inner connected by spokes, highlighting its non-planar and symmetric structure. The cubical graph Q3Q_3, or 3-dimensional hypercube, has 8 vertices, 12 edges, degree 3, and girth 4. It represents the graph of a cube, where vertices correspond to binary strings of length 3 and edges connect strings differing in one bit. The automorphism group has order 48 and acts distance-transitively. A standard embedding shows two squares connected by matching edges, highlighting its bipartite nature. The Heawood graph is a cubic symmetric graph with 14 vertices, 21 edges, and girth 6, serving as the (3,6)-cage. It is the point-line incidence graph of the Fano plane, the projective plane of order 2, with vertices partitioned into points and lines, and edges between incident pairs. Its automorphism group is PGL(2,7)PGL(2,7) of order 336, acting distance-transitively. The graph embeds on a torus as the seven-color map, with a hexagonal embedding revealing its symmetry. The Möbius-Kantor graph is the unique cubic symmetric graph on 16 vertices, with 24 edges and girth 6. It arises as the generalized Petersen graph GP(8,3)GP(8,3), with vertices divided into an outer 8-cycle and an inner structure connected by spokes. The has order 96 and acts flag-transitively. Visualizations often depict it as a twisted prism or with emphasizing its non-planar, bipartite properties. | Graph | Vertices | Edges | Degree | Girth | |Aut| | |----------------|----------|-------|--------|-------|----------| | K4K_4 | 4 | 6 | 3 | 3 | 24 | | | 10 | 15 | 3 | 5 | 120 | | Q3Q_3 | 8 | 12 | 3 | 4 | 48 | | Heawood | 14 | 21 | 3 | 6 | 336 | | Möbius-Kantor | 16 | 24 | 3 | 6 | 96 |

Classifications of Symmetric Graphs

Cubic Symmetric Graphs

A cubic symmetric graph is a of degree 3 whose acts transitively on its vertices, edges, and directed edges (). These graphs represent a fundamental class of symmetric graphs, combining regularity with high , and have been cataloged systematically to understand their structural properties and distribution by order. The Foster census, initiated by Ronald M. Foster in the early and formally published in 1988, provides a complete of all connected cubic symmetric graphs on up to 512 vertices, totaling 207 such graphs. This census was extended by computational methods in , yielding a complete list of all connected cubic symmetric graphs on up to 768 vertices, and further to 2048 vertices by Conder in 2006. All known cubic symmetric graphs have an even number of vertices, a consequence of the for regular graphs of odd degree. Key examples include the on 10 vertices with girth 5 and 2, the Heawood graph on 14 vertices with girth 6 and 3, the McGee graph on 24 vertices with girth 7 and 4, and the Tutte-Coxeter graph (also known as the 8-cage) on 30 vertices with girth 8 and 4. The girths of cubic symmetric graphs in the are typically 3, 4, 5, 6, 7, 8, 9, 10, or 12, reflecting constraints from their symmetry and degree. The following table lists all cubic symmetric graphs up to 100 vertices from the , including their vertex count, girth, and (references are to the complete enumeration in Conder and Dobcsányi (2002)).
Vertex countGirthDiameter
431
642
843
1052
1463
1664
1864
2055
2065
2464
2665
2874
3084
3265
3865
4086
4266
4886
5067
5466
5667
5676
5687
6095
6267
6486
7268
7467
7868
80108
8477
8669
90108
9668
9687
9869
9869

Higher-Degree Classifications

Symmetric graphs of degree greater than 3 exhibit greater rarity compared to cubic symmetric graphs, where comprehensive censuses enumerate thousands up to thousands of vertices; for higher degrees, classifications remain incomplete beyond modest sizes due to escalating computational demands. Databases such as the C4 census identify edge-transitive 4-regular graphs up to 512 vertices, with a subset of approximately 20-50 vertex-transitive (symmetric) examples up to 100 vertices, reflecting targeted searches using automorphism group actions. A complete enumeration of 4-valent arc-transitive graphs (a special case of symmetric) up to 640 vertices lists 4820 such graphs as of 2014. Classifying these graphs encounters significant hurdles from the exponential expansion of the search space with increasing vertex order, often exceeding feasible computational limits without specialized algorithms. Approaches depend on group-theoretic techniques, such as coset enumeration and identification, to systematically generate vertex-transitive graphs and verify edge-transitivity, though full enumerations for degrees above 4 lag behind even for orders under 100 vertices. Notable examples highlight unique structural features. For degree 4, the K4,4K_{4,4} provides a fundamental case with 8 vertices and girth 4, arising as the line graph of the K5K_5. The cuboctahedral graph, with 12 vertices and girth 4, represents an skeleton that is 4-regular and arc-transitive. For degree 7, the Hoffman-Singleton graph stands out as the sole known Moore graph of diameter 2, possessing 50 vertices and girth 5, constructed via a specific incidence structure with automorphism group of order 244800. Higher degrees yield even scarcer instances, such as the icosahedral graph of degree 5 with 12 vertices and girth 3, and the Gewirtz graph of degree 10 with 56 vertices and girth 4, the latter being a strongly regular graph embedded in the Higman-Sims graph.
DegreeGraphVerticesGirth
4K4,4K_{4,4}84
4Cuboctahedral graph124
5Icosahedral graph123
7Hoffman-Singleton505
10Gewirtz graph564

Extensions and Variations

s-Arc-Transitive Graphs

A graph is defined to be s-arc-transitive if its automorphism group acts transitively on the set of all s-arcs, where an s-arc is a sequence of s+1 distinct vertices (v_0, v_1, \dots, v_s) such that v_i is adjacent to v_{i+1} for each i = 0, \dots, s-1, and v_i \neq v_{i+2} for each i = 0, \dots, s-2 to avoid immediate reversals. This generalizes the notion of arc-transitivity (s=1), a property stronger than mere vertex- and edge-transitivity; higher values of s impose increasingly stringent symmetry requirements on the graph's structure, with 1-arc-transitive graphs forming a subclass of symmetric graphs. The study of s-arc-transitive graphs reveals sharp limitations on their existence for large s. In a seminal result, Weiss proved that no finite s-arc-transitive graph of valency at least 3 exists for s \geq 8. For s=7, such graphs are possible but restricted to specific valencies greater than 3, including examples arising as point-line incidence graphs of certain finite geometries with high symmetry. Examples abound for smaller s. For s=2, numerous cubic symmetric graphs exhibit 2-arc-transitivity, such as the utility graph K_{3,3} with 6 vertices and degree 3. For s=3, the Biggs-Smith graph provides a notable instance: this 3-regular graph on 102 vertices is 3-arc-transitive (and in fact 4-arc-transitive), constructed as an order-17 voltage graph expansion and recognized as the unique cubic distance-transitive graph of girth 7 beyond the known smaller cases. These examples illustrate how increasing s correlates with rarer, more symmetric configurations. Structural constraints further bound s in terms of the graph's girth g. For an s-arc-transitive graph of valency at least 3, the girth satisfies g \geq 2s - 2, equivalently s \leq (g + 2)/2; this follows from the fact that shorter cycles would force non-transitivity among s-arcs due to unavoidable repetitions or reversals. A half-transitive graph, also known as a half-arc-transitive graph, is a symmetric graph whose automorphism group acts transitively on its vertices and edges but not on its arcs, resulting in exactly two orbits on the set of arcs. Half-transitive graphs are thus the symmetric graphs that lack arc-transitivity. They necessarily have even degree, a result proved by using group-theoretic arguments on the stabilizer actions. The smallest known half-transitive graph is the Holt graph, a 4-regular graph on 27 vertices discovered by Derek F. Holt in 1981. This graph exemplifies the core property of half-transitive graphs: while undirected edges are transitive, the two arc orbits allow for two distinct, non-isomorphic arc-transitive orientations of the graph, each selecting one orbit as the directed edges. Such orientations highlight the "almost symmetric" nature of these graphs, where the failure of arc-transitivity manifests in this duality of directed structures. Numerous half-transitive graphs are known, including infinite families constructed for every even valency greater than 2, as shown by I. Z. Bouwer in via iterative voltage graph constructions. A related class consists of those half-transitive graphs where the two arc orbits have equal ; these are sometimes termed quasi-symmetric in the literature on transitive group actions, emphasizing balanced orbit sizes that often lead to additional structural symmetries, such as in certain Cayley graphs. Comprehensive censuses exist for specific degrees, such as all connected 4-valent half-transitive graphs up to 1000 vertices, revealing dozens of sporadic examples alongside the infinite families.

References

  1. https://www.sciencedirect.com/science/article/pii/S0166218X07005069
  2. https://mathworld.wolfram.com/SymmetricGraph.html
  3. https://arxiv.org/pdf/1306.4798
  4. https://www.cambridge.org/core/books/algebraic-graph-theory/symmetric-graphs/27034120BBC8ED838E52A9630F85BE17
  5. https://arxiv.org/pdf/2210.02679
  6. https://www.cmat.edu.uy/~marclan/TAG/Algebraic%20Graph%20theory%20Norman%20Biggs.pdf
  7. https://mathworld.wolfram.com/Arc-TransitiveGraph.html
  8. https://mathworld.wolfram.com/Vertex-TransitiveGraph.html
  9. https://mathworld.wolfram.com/Edge-TransitiveGraph.html
  10. https://www.cambridge.org/core/services/aop-cambridge-core/content/view/8BEB8A6C63409E285AF227508426CF40/S1446788700035564a.pdf/constructing_graphs_which_are_12_transitive.pdf
  11. https://arxiv.org/pdf/2105.03880
  12. https://www.maths.usyd.edu.au/u/athomas/papers/GiudiciLiSeressThomas_revised.pdf
  13. https://link.springer.com/article/10.1007/s11227-022-04557-6
  14. https://www.sfu.ca/~mdevos/notes/comb_numb/notes9.pdf
  15. http://combinatoricswiki.org/wiki/The_Degree_Diameter_Problem_for_Arc_Transitive_Graphs
  16. https://onlinelibrary.wiley.com/doi/full/10.1002/jgt.23041
  17. https://www.cambridge.org/core/journals/journal-of-the-australian-mathematical-society/article/symmetric-graphs-with-2arc-transitive-quotients/2D68ACE162CB2B6AB71025065109C2AF
  18. https://link.springer.com/article/10.1007/s10801-018-0825-3
  19. https://ceur-ws.org/Vol-2113/invited3.pdf
  20. https://people.cs.uchicago.edu/~laci/handbook/handbookchapter27.pdf
  21. https://mathworld.wolfram.com/PetersenGraph.html
  22. https://www.cambridge.org/core/services/aop-cambridge-core/content/view/04E061D619546C7D1940016EB05FF2B5/S0004972700012995a.pdf/distance-transitive-graphs-with-symmetric-or-alternating-automorphism-group.pdf
  23. https://webspace.maths.qmul.ac.uk/p.j.cameron/preprints/stpbg.pdf
  24. https://www.math.auckland.ac.nz/~conder/preprints/CayleySymmetries.pdf
  25. https://mathworld.wolfram.com/CompleteGraph.html
  26. https://mathworld.wolfram.com/CubicalGraph.html
  27. https://mathworld.wolfram.com/HeawoodGraph.html
  28. https://aeb.win.tue.nl/graphs/Heawood.html
  29. https://mathworld.wolfram.com/Moebius-KantorGraph.html
  30. http://www.math.auckland.ac.nz/~conder/symmcubic2048list.txt
  31. https://jan.ucc.nau.edu/swilson/C4FullSite/index.html
  32. https://www.sciencedirect.com/science/article/pii/S0095895615000623
  33. https://doi.org/10.1007/978-1-4471-0900-75-5
  34. https://link.springer.com/article/10.1007/BF02579337
  35. https://projecteuclid.org/journals/bulletin-of-the-london-mathematical-society/volume-3/issue-2/On-trivalent-graphs/10.1112/blms/3.2.155.full
  36. https://arxiv.org/pdf/2506.05803
  37. https://arxiv.org/abs/1505.02299
  38. https://arxiv.org/abs/1310.6543
Add your contribution
Related Hubs
User Avatar
No comments yet.