-
A graph
is vertex transitive if its automorphism group acts transitively on . -
Every vertex transitive graph is regular.
-
(Godsil 3.3.3) If
is a connected vertex-transitive graph with degree , then (see edge connectivity) -
(Godsil 3.4.2) A vertex transitive graph
with degree has vertex connectivity -
Proof: Let
be an atom of . By vertex transitivity and by the fact that atoms form a system of imprimitivity, we have . By (Godsil e3.20), . The degree of each atom vertex is bounded by
In other words
. Therefore substituting the constraint that Which completes the proof.
-
-
(Godsil e3.21) If a vertex transitive graph
with degree has vertex connectivity , then the atoms induce complete graphs. -
Proof: We argue using the proof from (Godsil 3.4.2) with some adjustments. First, for each atom vertex, let
be the number of internal edges. This gives external edges to . Clearly . Our goal is to show when is minimal. Our bound now becomes
or Where
and as in the proof with minimality holding precisely when . This gives us In other words
or . Substituting into the inequality above gives us which completes the proof.
-
-
(Godsil 3.5.1) Let
be a connected vertex-transitive graph. Then has a matching that leaves at most one vertex unmatched and each edge is contained in a maximum matching - If
is vertex transitive and one vertex is critical, then all vertices are critical. - If, in addition to the above,
is edge transitive, then no vertex is unmatched.
- If
-
(Godsil 3.6.3) A connected vertex transitive graph on
vertices contains a cycle of length at least . -
(Godsil 3.9.1) Any connected vertex transitive graph is a retract of a Cayley graph.
-
Let
be a vertex transitive graph and . Let be the set is a union of right cosets of and since is not adjacent with itself . Also If
and then This implies
. In combination with the fact that , we have . We can show inductively (via the diameter of
) that the automorphism subgroup generated by the elements of acts transitively on . The Cayley graph we are interested in is
. It can be shown that the right cosets of have no corresponding edges between them or are completely joined. The subgraph of induced by each right coset is empty since . The subgraph of
induced by any complete set of coset representatives of is isomorphic to . The homomorphism we are interested in is the map, from the vertices corresponding to the cosets of
, of the vertices from to . -
can be obtained from by replacing each vertex in with an independent set of size . The graph induced by a pair of them is empty when the vertices in are not adjacent or a complete bipartite subgraph if they are. -
-
-
Lovasz Conjecture: Every vertex transitive graph has a Hamiltonian path. Every vertex transitive graph contains a Hamiltonian cycle except for five counterexamples.
- the Petersen graph - The Coxeter graph
- The Petersen graph with vertices replaced by triangles
- The Coxeter graph with vertices replaced by triangles.