Fact-checked by Grok 2 weeks ago

Vertex-transitive graph

A vertex-transitive graph is an undirected graph in which the automorphism group acts transitively on the set of vertices, meaning that for any pair of vertices, there exists an automorphism mapping one to the other, so that all vertices are indistinguishable in terms of their structural roles.^[1] Such graphs are always regular, with every vertex having the same degree, though the converse does not hold—not all regular graphs are vertex-transitive.^[1] The automorphism group of a vertex-transitive graph is transitive on the vertices, ensuring a high degree of symmetry that "looks the same" from every vertex's perspective.^[2] Vertex-transitive graphs form a fundamental class in algebraic graph theory, bridging graph theory and group theory, particularly through their connection to Cayley graphs, which are vertex-transitive by construction and defined using a group and a generating set.^[2] All Cayley graphs are vertex-transitive, with the group acting regularly on the vertices, and they serve as models for symmetric structures in combinatorics.^[3] Notable properties include the Lovász conjecture, which posits that every connected vertex-transitive graph contains a Hamilton path (traceable), though this remains unproven but verified for many cases, including a 2024 proof for all such graphs of odd order.^[1]^[4] Additionally, Thomassen conjectured that nearly all connected vertex-transitive graphs are Hamiltonian, with only five known counterexamples.^[1] Classic examples of vertex-transitive graphs include the complete graphs K_n, cycle graphs C_n, the Petersen graph, the hypercube Q_k, and the Coxeter graph.^[1] For instance, the cycle graph C_5 arises as the Cayley graph of the cyclic group \mathbb{Z}_5 with connection set \{1,4\}.^[3] These graphs exhibit single orbits under their automorphism groups, and enumerations show that the number of connected vertex-transitive graphs on n vertices grows modestly, such as 1 for n=1, 1 for n=2, up to 7 for n=9.^[1] The study of vertex-transitive graphs has significant applications in computer science and networks, where their symmetry models communication networks, data organization, and computational devices due to uniform vertex properties.^[5] In combinatorial group theory, they provide tools for analyzing group actions and expander graphs, with implications for network analysis, graph partitioning, and efficient algorithms in physics and communication systems.^[6] Their role in random walks and hitting times further extends to probabilistic models on symmetric structures.^[7]

Definition

Formal Definition

A graph G = (V, E) is vertex-transitive if, for every pair of vertices u, v \in V, there exists an automorphism \phi of G such that \phi(u) = v.^[8] A graph automorphism is a bijective mapping \phi: V \to V such that adjacency is preserved, meaning \{x, y\} \in E if and only if \{\phi(x), \phi(y)\} \in E.^[9] Equivalently, the automorphism group \Aut(G) acts transitively on the vertex set V, so that the orbit of any single vertex under the action of \Aut(G) is all of V.^[8] The order of this group is denoted |\Aut(G)|. Vertex-transitivity implies that the graph is regular, meaning all vertices have the same degree, since automorphisms preserve the degree of each vertex. For instance, the cycle graph C_n and the complete graph K_n are vertex-transitive for n \geq 3.^[1]

Equivalent Formulations

A graph G is vertex-transitive if and only if its automorphism group \operatorname{Aut}(G) acts transitively on the vertex set V(G), meaning that for any two vertices u, v \in V(G), there exists an automorphism \phi \in \operatorname{Aut}(G) such that \phi(u) = v.^[10] Equivalently, the orbit of any vertex under the action of \operatorname{Aut}(G) coincides with the entire vertex set V(G).^[1] This transitivity implies a strong form of local equivalence: the subgraphs induced by the open neighborhoods N(u) and N(v) of any two vertices u, v \in V(G) are isomorphic via an automorphism of G. More generally, for any integer k \geq 0, the balls of radius k centered at u and at v—consisting of all vertices within distance at most k from the center, together with the edges between them—are isomorphic via an automorphism mapping u to v.^[10] From a group-theoretic perspective, G is vertex-transitive if and only if it admits a transitive group of automorphisms acting on V(G), where the stabilizer subgroups \operatorname{Stab}_{\operatorname{Aut}(G)}(u) and \operatorname{Stab}_{\operatorname{Aut}(G)}(v) are isomorphic for all u, v \in V(G), as they are conjugate subgroups under the transitive action.^[11] By the orbit-stabilizer theorem, the index of each stabilizer equals |V(G)|, ensuring uniformity across vertices.^[10] Sabidussi (1964) showed that every connected vertex-transitive graph admits a regular subgroup of automorphisms, allowing it to be realized as a Cayley graph of that group.^[12]

Properties

Structural Properties

Vertex-transitive graphs are regular, meaning every vertex has the same degree \delta. This follows from the transitivity of the automorphism group action, which preserves degrees and maps any vertex to any other, ensuring uniformity in the neighborhood size of each vertex.^[1]^[13] The size of the automorphism group of a vertex-transitive graph G with n = |V(G)| vertices satisfies |\Aut(G)| = n \cdot |\Stab(v)|, where \Stab(v) is the stabilizer subgroup of a fixed vertex v. This equality arises directly from the orbit-stabilizer theorem applied to the transitive action of \Aut(G) on the vertex set.^[1] Connected vertex-transitive graphs exhibit strong connectivity properties. By Mader's theorem, the edge-connectivity equals the degree \delta. The vertex-connectivity \kappa(G) is at least $2(\delta + 1)/3, as established by Watkins. These bounds highlight the robustness of such graphs against vertex or edge failures.^[13]^[14] Vertex-transitive graphs can be disconnected, in which case they consist of multiple isomorphic connected components, with the automorphism group acting transitively on both the vertices within components and the components themselves.^[1] Invariants such as the chromatic number \chi(G) and independence number \alpha(G) are uniform across the graph due to the symmetry, meaning they do not vary relative to any particular vertex. Vertex-transitivity implies the existence of equitable partitions of the vertex set, where each part has vertices with the same number of neighbors in every other part; in particular, the orbits under the automorphism group form such partitions.^[15]

Metric Properties

In vertex-transitive graphs, the symmetry imposed by the automorphism group ensures a uniform metric structure across the vertex set. Specifically, the distance profile from any vertex is identical: for each integer k \geq 0, the number of vertices at graph distance k from a given vertex v, denoted N_k(v), is independent of the choice of v. Thus, N_k(v) = N_k for some constant N_k that depends only on k and the graph. This uniformity arises because any automorphism mapping one vertex to another preserves distances, thereby mapping the k-sphere around the first vertex bijectively to the k-sphere around the second. The sequence (N_0, N_1, \dots, N_D), where D is the diameter of the graph and N_0 = 1, fully characterizes the distance distribution from every vertex in a connected vertex-transitive graph. For example, in the cycle graph C_n (which is vertex-transitive), N_1 = 2 and N_k = 2 for $1 < k \leq \lfloor n/2 \rfloor, reflecting the balanced spread of distances along the cycle. This sphere uniformity underpins many metric invariants and distinguishes vertex-transitive graphs from more general regular graphs, where distance profiles may vary by vertex. In a connected vertex-transitive graph, the eccentricity of every vertex—defined as the maximum distance to any other vertex—is identical, implying that the radius equals the diameter. Moreover, since the automorphism group acts transitively on vertices, every vertex achieves this common eccentricity value, making the graph self-centered. For instance, in the hypercube graph Q_d, both the radius and diameter are d, and this holds uniformly for all vertices.^[16] The girth g, the length of the shortest cycle in the graph, exhibits invariance under vertex-transitivity: every vertex lies on at least one cycle of length g. This follows from the transitivity of the automorphism group, which maps any girth-attaining cycle to a cycle containing an arbitrary target vertex while preserving cycle length. In graphs without cycles (trees), the girth is infinite, but connected vertex-transitive trees are limited to the infinite regular tree, where distances grow uniformly.^[16] Automorphisms in vertex-transitive graphs preserve distances and thus map shortest paths to shortest paths. However, this does not guarantee uniqueness of shortest paths between pairs of vertices; vertex-transitive graphs are generally not geodetic unless additional symmetry is present. For example, the d-dimensional hypercube Q_d (distance-transitive) has multiple shortest paths between many pairs, yet its automorphisms act transitively on ordered pairs at fixed distance k. In contrast, distance-transitive graphs— a proper subclass of vertex-transitive graphs—extend this by allowing automorphisms to map any ordered pair (u, v) to any other (w, x) with \mathrm{dist}(u, v) = \mathrm{dist}(w, x), but even these need not be geodetic. Algebraically, the uniformity manifests in the adjacency matrix A: since the graph is regular of degree \delta, each row (and column) of A sums to \delta. For powers A^k, the diagonal entries (A^k)_{v,v} are constant across all vertices v, equal to the number of closed walks of length k starting and ending at v, which is invariant under automorphisms. Similarly, the row sums of A^k are constant, representing the total number of walks of length k from any vertex, further underscoring the metric homogeneity.^[16]

Automorphism and Symmetry

Automorphism Group Action

A vertex-transitive graph G is characterized by the transitive action of its automorphism group \operatorname{Aut}(G) on the vertex set V(G), meaning that for any two vertices u, v \in V(G), there exists \phi \in \operatorname{Aut}(G) such that \phi(u) = v.^[17] This action partitions V(G) into orbits under \operatorname{Aut}(G), but transitivity ensures a single orbit comprising all vertices; the only exception occurs when |V(G)| = 1, where each orbit is a singleton.^[17] The orbit-stabilizer theorem provides a fundamental group-theoretic relation for this action: for any vertex v \in V(G), |\operatorname{Aut}(G)| = |V(G)| \cdot |\operatorname{Aut}(G)_v|, where \operatorname{Aut}(G)_v = \{\phi \in \operatorname{Aut}(G) \mid \phi(v) = v\} is the stabilizer subgroup of v.^[18] This equation quantifies the size of the automorphism group in terms of the graph order and the "local symmetry" at a single vertex, as all stabilizers are isomorphic by transitivity.^[18] The action of \operatorname{Aut}(G) on V(G) is faithful by definition, embedding \operatorname{Aut}(G) injectively into the symmetric group \operatorname{Sym}(V(G)); for connected graphs, this faithfulness ensures that the symmetries are fully captured without a nontrivial kernel.^[17] If the stabilizer \operatorname{Aut}(G)_v is trivial for some (equivalently, every) vertex v, the action is regular, meaning \operatorname{Aut}(G) acts freely and transitively on V(G). In this case, G admits \operatorname{Aut}(G) as a regular group of automorphisms, implying G is isomorphic to a Cayley graph of \operatorname{Aut}(G).^[17] Computing \operatorname{Aut}(G) for vertex-transitive graphs often leverages the permutation group structure induced by the action on vertices, with the Schreier-Sims algorithm providing an efficient method to determine a base and strong generating set for small to moderate-sized graphs (up to thousands of vertices).^[19] Theoretical bounds on |\operatorname{Aut}(G)| arise from the orbit-stabilizer theorem combined with restrictions on the stabilizer: for a connected d-regular vertex-transitive graph G with n = |V(G)| vertices, \operatorname{Aut}(G)_v acts faithfully on the d neighbors of v, yielding |\operatorname{Aut}(G)_v| \leq d! and thus |\operatorname{Aut}(G)| \leq n \cdot d!.^[20] For infinite vertex-transitive graphs, the automorphism group action remains transitive on the vertex set, but \operatorname{Aut}(G) may be uncountable; for instance, the unit distance graph on \mathbb{R}^2 (with edges between points at Euclidean distance 1) has \operatorname{Aut}(G) equal to the uncountable group of plane isometries, which acts transitively on vertices.

Relation to Other Symmetries

A graph is edge-transitive if its automorphism group acts transitively on the set of edges, meaning any edge can be mapped to any other edge by some automorphism.^[21] This property does not imply vertex-transitivity in general, as demonstrated by semisymmetric graphs, which are regular, edge-transitive, and bipartite but not vertex-transitive.^[22] In contrast, a graph is arc-transitive (also called symmetric) if its automorphism group acts transitively on the set of arcs, where an arc is an ordered pair of adjacent vertices.^[23] Arc-transitivity implies both edge-transitivity and vertex-transitivity, establishing a hierarchy where arc-transitive graphs form a subclass of edge-transitive graphs, which in turn include but are not limited to vertex-transitive graphs.^[22] Vertex-transitivity alone implies nothing about edge or arc transitivity; for instance, the Petersen graph is vertex-transitive and edge-transitive but not arc-transitive. This hierarchy has significant implications for graph properties. All vertex-transitive graphs are regular, as automorphisms preserve degrees, but they are distance-regular only in specific cases, such as when additional symmetry conditions hold; in general, regularity and vertex-transitivity do not suffice for distance-regularity.^[24] Arc-transitive graphs, being vertex-transitive, are also regular and exhibit stronger uniformity in their structure, often leading to applications in combinatorial designs and network theory. In bipartite graphs, arc-transitivity requires the two parts to have equal size and the graph to be biregular with the same degree on both sides, though this degree can be odd, as in the complete bipartite graph K_{3,3}.^[25] A generalization of these symmetries is s-arc-transitivity, where the automorphism group acts transitively on the set of s-arcs—sequences of s+1 vertices such that consecutive vertices are adjacent and no three consecutive vertices repeat (for s ≥ 2). Vertex-transitivity corresponds to the case s=0, while arc-transitivity is s=1; higher s values impose increasingly stringent conditions on the graph's symmetry.^[26] Distinctions between these symmetries are evident in simple graphs: the complete graph K_4 is arc-transitive, as are all complete graphs K_n for n ≥ 2, due to their full symmetry under the symmetric group.^[23] Cycle graphs C_n for n ≥ 3 are also arc-transitive (in fact, 2-arc-transitive), illustrating how circulant structures often achieve high symmetry.^[27] Not all connected vertex-transitive graphs are Cayley graphs; the Petersen graph is a well-known counterexample.^[28] However, every vertex-transitive graph of order p^k, where p is prime and k \leq 3, is a Cayley graph.^[29]

Examples

Finite Examples

Cycle graphs C_n for n \geq 3 provide a basic example of finite vertex-transitive graphs. These graphs consist of n vertices connected in a single cycle, with the automorphism group generated by rotations, ensuring every vertex is equivalent. They are 2-regular, with girth equal to n. Complete graphs K_n for n \geq 1 are another fundamental class of vertex-transitive graphs, exhibiting full symmetry where every pair of distinct vertices is adjacent. These graphs have n vertices, degree n-1 for each vertex, and diameter 1. The Petersen graph, with 10 vertices and degree 3, is a prominent example of a vertex-transitive graph that is not a Cayley graph. It has girth 5 and is famously non-Hamiltonian, serving as a counterexample in several graph theory conjectures. Its construction can be viewed as the odd graph O_3 or via the complement of the line graph of K_5.^[30] Hypercube graphs Q_d for dimension d \geq 1 are vertex-transitive, with $2^d vertices each corresponding to a binary string of length d, and edges connecting strings differing in exactly one bit. These graphs are d-regular, and their symmetries preserve Hamming distances between vertices. Paley graphs offer a family of vertex-transitive graphs defined on the vertices of the finite field \mathbb{F}_q where q is a prime power congruent to 1 modulo 4. Two vertices are adjacent if their difference is a quadratic residue in \mathbb{F}_q. These graphs are strongly regular and self-complementary. The enumeration of connected vertex-transitive graphs on n vertices reveals rapid growth with n, with no known closed-form formula. For instance, there is 1 on 1 vertex, 1 on 3 vertices, 2 on 4 vertices, and 64 on 12 vertices.^[31] Not all vertex-transitive graphs are Cayley graphs; the Frucht graph on 12 vertices is a cubic example that is vertex-transitive but admits no regular group action on its vertices, distinguishing it from Cayley constructions.

Infinite Examples

One prominent example of an infinite vertex-transitive graph is the infinite regular tree T_d, where each vertex has degree d \geq 2. This graph embeds naturally in hyperbolic geometry and has infinite diameter, with no cycles and exponential growth from any vertex.^[32] The integer lattice \mathbb{Z}^d for d \geq 1 provides another fundamental example, defined as the graph with vertices at integer coordinates in d-dimensional space and edges connecting points differing by exactly one unit in a single coordinate. It is regular of degree $2d, and distances correspond to the \ell_1 norm, yielding infinite diameter and polynomial growth of order d.^[33] Cayley graphs of infinite groups offer a broad class of infinite vertex-transitive graphs, constructed via the left regular action of the group on itself. For instance, the Cayley graph \mathrm{Cay}(\mathbb{Z}, \{1, -1\}) is the bidirectional infinite path graph, regular of degree 2 with infinite diameter. More complex examples include Cayley graphs of free groups on k \geq 2 generators, which are infinite regular trees of degree $2k. By definition, all Cayley graphs are vertex-transitive.^[34] Hyperbolic tilings of the hyperbolic plane yield additional infinite vertex-transitive graphs through their 1-skeletons. The regular tiling denoted by Schläfli symbol \{7,3\}, consisting of regular heptagons meeting three at each vertex, is uniform and thus has a vertex-transitive automorphism group, realizing a 3-regular graph of infinite diameter embedded in hyperbolic space.^[35] The Bethe lattice, synonymous with the infinite regular tree of degree k+1 for k \geq 1, is an acyclic graph without leaves, exhibiting uniform exponential growth and serving as a model for mean-field approximations in statistical mechanics; it is vertex-transitive due to its tree structure.^[36] Uncountable examples exist as well, such as the Cayley graph of the additive group (\mathbb{R}, +) with generating set \{1, -1\}, where vertices are real numbers and edges connect points exactly distance 1 apart. This graph is 2-regular, vertex-transitive under translations, and disconnected with uncountably many components, each isomorphic to the infinite path, but the overall structure admits infinite distances without a finite diameter.^[34] contrasted by uniform growth rates: the number of vertices at graph distance n from any fixed vertex is identical across all starting vertices, reflecting the symmetry.^[37]

Constructions

Cayley Graphs

A Cayley graph provides a canonical method for constructing vertex-transitive graphs from group-theoretic data. Formally, given a group \Gamma and a symmetric generating set S \subseteq \Gamma \setminus \{e\} (meaning s \in S implies s^{-1} \in S), the Cayley graph \mathrm{Cay}(\Gamma, S) is the undirected graph with vertex set \Gamma and an edge between distinct vertices g and h if and only if h = gs for some s \in S. This construction, introduced by Arthur Cayley in 1878 to represent abstract groups graphically, yields a |S|-regular graph since each vertex g connects precisely to gs for all s \in S.^[34] Cayley graphs are inherently vertex-transitive. The left regular action of \Gamma on itself, given by the maps \lambda_h: g \mapsto hg for h \in \Gamma, preserves adjacency: if g is adjacent to gs, then \lambda_h(g) = hg is adjacent to \lambda_h(gs) = hgs = (hg)s. These automorphisms act transitively on the vertices because for any g, k \in \Gamma, the map \lambda_{k g^{-1}} sends g to k. Moreover, the graph is connected if and only if S generates \Gamma, as paths in the graph correspond to words in the generators from S.^[38]^[38] Representative examples illustrate these properties. For the cyclic group \mathbb{Z}_n with S = \{1, n-1\}, \mathrm{Cay}(\mathbb{Z}_n, S) is the cycle graph C_n, which is 2-regular and connected. Similarly, for the symmetric group S_3 generated by the set of all transpositions S = \{(1\,2), (1\,3), (2\,3)\}, the resulting Cayley graph is the complete bipartite graph K_{3,3}, a 3-regular graph on six vertices. In the infinite case, \mathrm{Cay}(\mathbb{Z}, \{\pm 1\}) forms the infinite path graph, which is connected and 2-regular but unbounded.^[34]^[39]^[40] Different pairs (\Gamma, S) can produce isomorphic Cayley graphs, highlighting a lack of uniqueness in representations. For instance, the cycle C_4 arises as \mathrm{Cay}(\mathbb{Z}_4, \{1,3\}) and also as \mathrm{Cay}(V_4, S') where V_4 is the Klein four-group and S' its two non-identity elements of order 2; these groups are non-isomorphic, yet yield the same graph. This non-uniqueness extends broadly, with some Cayley graphs admitting multiple nonequivalent representations over distinct groups, as characterized by conditions on regular automorphism actions.^[41]^[42]

Other Constructions

One method for constructing vertex-transitive graphs involves graph covers, where a covering graph of a base graph inherits symmetry properties. Specifically, the universal cover of a finite d-regular graph is the infinite d-regular tree, which is vertex-transitive due to the free action of its automorphism group on the vertices.^[43] This construction yields infinite vertex-transitive graphs that serve as fundamental examples in geometric group theory.^[44] Voltage graphs provide an algebraic technique to generate vertex-transitive covering graphs from a base graph and a voltage assignment. In this approach, voltages from a group are assigned to the directed edges of a base graph, and the derived covering graph admits a regular group action, ensuring vertex-transitivity.^[45] This method generalizes covering constructions and has been used to build large symmetric graphs, such as cages, by composing regular coverings.^[46] Coset graphs offer another algebraic construction, where vertices correspond to cosets of a subgroup H in a group Γ acting transitively on a set, with edges defined by the action of a connection set. Such graphs are vertex-transitive by the transitive action of Γ on the cosets.^[47] Every finite vertex-transitive graph arises as a coset graph for some transitive permutation representation of its automorphism group.^[48] Geometric constructions yield vertex-transitive graphs through incidence structures. The incidence graph of a finite projective plane of order q is (q+1)-regular and vertex-transitive, with vertices representing points and lines, and edges indicating incidence relations.^[49] Similarly, incidence graphs of affine geometries over finite fields produce vertex-transitive bipartite graphs, often used to build large graphs of small diameter.^[50] In the context of polyhedral graphs, operations like truncation and taking duals preserve vertex-transitivity when applied to uniform polyhedra. Truncation cuts off vertices of a vertex-transitive polyhedron, replacing each with a face while maintaining the transitive automorphism action on the new vertex set; the resulting graph remains vertex-transitive as part of the uniform polyhedra family.^[51] Probabilistic methods establish the asymptotic existence of dense vertex-transitive graphs with prescribed properties. Randomized constructions, such as those generating vertex-transitive graphs via random Cayley connections or coset actions, show that for large n and degree d = Θ(n^α) with α > 0, such graphs exist with high probability and avoid certain subgraphs.^[52] Historically, W. T. Tutte introduced early constructions of symmetric graphs, which are vertex-transitive, in his work on cubic graphs. His method, involving voltage-like assignments over finite fields, produced the Tutte 8-cage, a 3-regular symmetric graph of girth 8, influencing subsequent algebraic constructions.

References

[1]
Vertex-Transitive Graph -- from Wolfram MathWorld
A vertex-transitive graph is where every pair of vertices is equivalent under its automorphism group, meaning every vertex has the same local environment.
[2]
[PDF] Algebraic Graph Theory: Automorphism Groups and Cayley graphs
Definition. A graph Γ is vertex transitive if there exists a single orbit of V (Γ) under. Aut(Γ). That is, given any ...
[3]
[PDF] Regular permutation groups and Cayley graphs - mathtube.org
Cayley graph: Γ = Cay(G, S). Always: GR ≤ Aut (Γ), so Cayley graphs are always vertex-transitive. Example: G = Z5, S = {1,4}, obtain Γ = C5, Aut(Γ) = D10 . 1.
[4]
Traversability of vertex-transitive graphs - InnoRenew CoE
Nov 7, 2018 · In computer science, they represent networks of communication, data organization, computational devices, and more. In statistical physics ...
[5]
[PDF] International Journal of Applied Engineering & Technology
Notable applications include network analysis, graph partitioning, and expander graphs, with implications across computer science, physics, and communication ...<|separator|>
[6]
[PDF] Hitting times for random walks on vertex-transitive graphs
This paper studies hitting times for random walks on vertex-transitive graphs, finding equalities, inequalities, and limit theorems, including a condition for ...
[7]
[PDF] Automorphism groups, isomorphism, reconstruction (Chapter 27 of ...
Jun 12, 1994 · A graph is vertex-transitive if its automorphism group acts transitively on the set of ... A vertex-transitive graph need not be edge-transitive.
[8]
[PDF] Automorphisms of Graphs Math 381 - People
An automorphism of a graph is an isomorphism with itself. That means it is a bijection, α : V (G) → V (G), such that α(u)α(v) is an edge if and only if uv ...
[9]
Vertex-transitive graphs (Chapter 16) - Algebraic Graph Theory
Vertex-transitive graphs · Norman Biggs, London School of Economics and Political Science; Book: Algebraic Graph Theory; Online publication: 05 August 2012 ...
[10]
Vertex-transitive Graphs - Gert Sabidussi, Hamilton, Ontario, Canada
The present note is an extension of the author's paper [7] on strongly fixed-point-free graphs. It is prompted by the observation that graphs.
[11]
Vertex-transitive graphs | Monatshefte für Mathematik
Vertex-transitive graphs. Published: October 1964. Volume 68, pages 426 ... Sabidussi, G., On a class of fixed-point-free graphs, Proc. Amer. Math. Soc ...
[12]
[2207.07536] The Edge-Connectivity of Vertex-Transitive Hypergraphs
Jul 15, 2022 · A classic theorem of Mader asserts that every connected vertex-transitive graph is maximally edge-connected. We generalise this result to hypergraphs.
[13]
Connectivity of vertex and edge transitive graphs - ScienceDirect.com
It is proved that a connected vertex and edge transitive graph is not super-connected if and only if it is isomorphic to the lexicographic product of a cycle C ...
[14]
[PDF] Equitable Partitions and Orbit Partitions - UChicago Math
A graph is called vertex-transitive if for any u, v ∈ V , there is an automorphism which maps u to v. Note that a vertex-transitive graph is necessarily regular ...
[15]
Algebraic Graph Theory - Cambridge University Press & Assessment
Algebraic Graph Theory. Algebraic Graph Theory. Algebraic Graph Theory. Search ... 16 - Vertex-transitive graphs. pp 122-129. You have access Access. PDF ...
[16]
[PDF] Automorphisms of graphs - vlsicad page
A graph G is vertex-transitive if the automorphism group of G acts transi- tively on the vertex set of G. Any vertex-transitive graph has a description as a ...
[17]
[PDF] Pretty Theorems on Vertex Transitive Graphs
The diameter of a subset of vertices X, denoted diam(X) is ... through an arbitrary vertex of G (since G is vertex transitive this number is the same for.Missing: equal | Show results with:equal
[18]
[PDF] Computing with graphs and groups
Automorphism groups and graph isomorphism. 7. Computing with vertex-transitive graphs. 8. Coset enumeration. 9. Coset enumeration in the study of symmetric ...
[19]
(PDF) Algebraic Graph Theory - ResearchGate
... Algebraic Graph Theory by Chris Godsil and Gordon. Royle. The chapters in brackets were revision or introductory material. Briefly, the content of each ...
[20]
On edge-primitive 2-arc-transitive graphs - ScienceDirect.com
An edge-primitive graph has an automorphism group that acts primitively on the edge set. A 2-arc-transitive edge-primitive graph has an almost simple ...
[21]
Half-arc-transitive graphs of arbitrary even valency greater than 2
A half-arc-transitive graph is a regular graph that is both vertex- and edge-transitive, but is not arc-transitive. If such a graph has finite valency, ...
[22]
On the orders of arc-transitive graphs - ScienceDirect
A graph is called arc-transitive (or symmetric) if its automorphism group has a single orbit on the set of all ordered pairs of adjacent vertices in the graph.
[23]
Vertex transitivity, distance metric, and hierarchical structure of the ...
May 23, 2022 · In particular, a vertex-transitive graph is necessarily regular, whereas an edge-transitive graph need not be regular. If a graph is both vertex ...Missing: implies | Show results with:implies
[24]
Arc-transitive elementary abelian covers of the Pappus graph
It may be easily seen that if X is edge-transitive but not vertex-transitive then X is necessarily bipartite, and if X has regular valency then the two parts of ...
[25]
Arc-transitive Cayley graphs on nonabelian simple groups with ...
A graph Γ, with G ≤ Aut ( Γ ) , is said to be ( G , s ) -arc-transitive or G-regular if G is transitive on the s-arc set of Γ or G is regular on the vertex set ...
[26]
A note on arc-transitive circulant digraphs - De Gruyter Brill
We prove that, for a positive integer n and subgroup H of automorphisms of a cyclic group Z of order n , there is up to isomorphism a unique connected ...
[27]
Yahya Ould Hamidoune's mathematical journey: A critical review of ...
In [10] there is a section on vertex-transitive graphs which contain two key results: the arc-connectivity of a connected vertex-transitive graph equals the ...
[28]
Vertex-transitive graphs which are not Cayley graphs, I
The Petersen graph on 10 vertices is the smallest example of a vertex-transitive graph which is not a Cayley graph. We consider the problem of determining the ...
[29]
[PDF] The Transitive Graphs with at Most 26 Vertices Brendan D. McKay ...
The circulant graphs. (those on n vertices whose automorphism group contains an n-cycle) were found up to order 37 by the first author in 1977 (unpublished).<|control11|><|separator|>
[30]
[PDF] arXiv:1508.02247v2 [math.MG] 17 Feb 2019
Feb 17, 2019 · Observe that given an integer d ≥ 2, any d-regular graph X is covered by the d-regular (infinite) tree Td. ... Let X be a vertex-transitive graph.<|control11|><|separator|>
[31]
[PDF] Low-dimensional lattices. VII Coordination sequences - Neil Sloane
The following symbols will be used: L J for integer part or floor, F for ceiling, Z for the integers, Q for the rationals, IR for the reals. For undefined terms ...
[32]
Cayley Graph -- from Wolfram MathWorld
A (directed or undirected) Cayley graph is always vertex-transitive, but the converse need not hold. However, a large fraction of small vertex-transitive graphs ...
[33]
Semi-regular Tilings of the Hyperbolic Plane
Dec 1, 2019 · Moreover, in this case, the tiling T is uniform, i.e., it has vertex transitive automorphism group. As a corollary, we obtain the uniqueness of ...
[34]
On vertex‐transitive graphs with a unique hamiltonian cycle
Aug 22, 2024 · We find all uniquely hamiltonian vertex-transitive graphs with finitely many ends, and also discuss some examples with infinitely many ends.
[35]
[PDF] characterizing a vertex-transitive graph by a large ball - Normale sup
By Proposition 1.5 there exists R ≥ 2 such that every k-simply connected graph which is R-locally X is isomorphic to X. We prove Corollary 1.6 for this R. Let ...
[36]
[PDF] Lecture 2 1 Automorphism group 2 Cayley graphs - ktiml
Nov 6, 2012 · A graph G is vertex-transitive if Aut(G) acts transitively on V . 2 Cayley graphs. In the last lecture we saw that the hypercube can be defined ...
[37]
[PDF] Cayley graphs - OSU Math
We now look at some examples to help illustrate this theorem. Figure 2. Two Cayley graphs for S3. The Cayley graph on the left is with respect to generating ...
[38]
[PDF] Locally infinite graphs and symmetries - arXiv
Jan 5, 2017 · In particular, if G is transitive, then for every vertex o of G, the generalised diameter of G is equal to the generalised radius of (G,o).
[39]
[PDF] Cayley Graphs - Simon Rubinstein-Salzedo
In this paper, we start by summarizing the basics of group theory and graph theory, as well as group actions, orbits, stabilizers, and group and graph ...
[40]
[PDF] Structural characterization of Cayley graphs - arXiv
Sep 27, 2016 · Sabidussi's theorem characterizes the undirected and unlabelled Cayley graphs as the con- nected graphs having a free transitive action by a ...Missing: Stein conjecture resolved
[41]
Presentations for vertex-transitive graphs | Journal of Algebraic ...
Oct 4, 2021 · We proceed with the formal definition of P. The vertex classes of ... Godsil, C., Royle, G.: Algebraic Graph Theory. Graduate Texts in ...
[42]
Presentations for vertex-transitive graphs - PMC - NIH
We generalise the standard constructions of a Cayley graph in terms of a group presentation by allowing some vertices to obey different relators than others.
[43]
Generalised voltage graphs - ScienceDirect
The aim of this paper is to present such a method, which generalises both the coset graph construction as well as the covering graph construction based on the ...
[44]
[PDF] Composition of regular coverings of graphs and voltage assignments
In conclusion we apply our results to a composition of regular covering of graphs that has arisen in constructions of currently largest vertex-transitive graphs ...
[45]
[PDF] A construction of vertex-transitive non-Cayley graphs
The construction based on representing vertex-transitive graphs as coset graphs of groups, and on a simple but powerful necessary arithmetic condition for ...
[46]
[PDF] arXiv:2407.02316v1 [math.CO] 2 Jul 2024
Jul 2, 2024 · It has long been known that a vertex-transitive graph Γ is isomorphic to a double coset graph Cos(G, H, S) of a transitive group G ≤ Aut(Γ) ...
[47]
[PDF] Dynamic Cage Survey - The Electronic Journal of Combinatorics
The incidence graph of a projective plane of order q is regular of degree q + 1, has 2(q2 +q+1) vertices, diameter 3, and girth 6. Since the Moore bound for ...<|control11|><|separator|>
[48]
Large vertex-transitive graphs of diameter 2 from incidence graphs ...
Oct 6, 2013 · Abstract. Under mild restrictions, we characterize all ways in which an incidence graph of a biaffine plane over a finite field can be extended ...
[49]
[PDF] Classification of uniform polyhedraby their symmetry-type graphs
A polyhedron P is called uniform if it is vertex-transitive and if all its faces are regular polygons or regular stars.
[50]
[PDF] Computational and Theoretical Aspects of N-E.C. Graphs
We give a new randomized construction of n-e.c. vertex-transitive graphs, exploiting Cayley graphs. The construction uses only elementary probability and group ...