4
$\begingroup$

I have a hard time understanding the intuition behind what a vertex transitive graph is. I was told that a circle graph on $10$ vertices is vertex transitive, but have been unable to generalize. The mathematical definition is unclear to me. Does anyone have a simple way of understanding it? Is there an example of an adjacency matrix representation of this?

$\endgroup$
  • $\begingroup$ You can't tell vertices apart, the graph looks the same standing on any of them? The $K_n$'s are examples. Looking at graphs that are not examples should also be useful. Examples of the latter could be graphs in which two vertices have different degrees. $\endgroup$ – Marja Aug 8 '17 at 1:31
  • $\begingroup$ Are you asking for a simple to understand example, or a simple to understand explanation? You ask for one in the title and the other in the body. $\endgroup$ – Morgan Rodgers Aug 8 '17 at 1:55
  • $\begingroup$ Also, what do you know about automorphism groups? $\endgroup$ – Morgan Rodgers Aug 8 '17 at 1:55
  • $\begingroup$ I am hoping to get an adjacency matrix representation of the vertices. Is there an example there? $\endgroup$ – user321627 Aug 8 '17 at 2:38
5
$\begingroup$

In an effort to make the idea of vertex-transitivity more intuitive, I'll move through the formal definition with some comments, then give a few examples of graphs that are transitive, and a few that are not.

Automorphisms

The most important idea with any kind of transitivity is a graph automorphism. You probably know this, but I'll give a definition for completeness' sake.

For a graph $X$, an automorphism of $X$ is a bijective function $\varphi: V(X)\to V(X)$ which has the property that $x,y\in V(X)$ are adjacent if and only if $\varphi(x)$ and $\varphi(y)$ are adjacent.

Intuitively, you can think of an automorphism as a symmetry the graph $X$ has. For example, you can label the circle graph on $10$ vertices with $\{0,1,\dots, 9\}$ in order, going clockwise. An example of automorphism of this graph is $$\varphi: C_{10}\to C_{10} ~\text{ where }~ i\mapsto i+1\!\!\!\!\pmod{10}.$$ You can formally show that this is an automorphism, but an easy way to convince yourself of this is to see that $\varphi$ is really just a rotation moving to the right by $2\pi/10$. Similarly, the automorphism $\psi: C_{10}\to C_{10}$ given by $\psi(i)=-i$ is the same as picking the graph up off the paper and flipping it over. A good exercise is to take the graph of a cube and find automorphisms of the graph by thinking about moving around a 3-D cube.

Vertex Transitivity

To apply this to vertex-transitivity, we first have the definition.

A graph $X$ is called transitive if for any pair of vertices $x,y\in V(X)$ there is some automorphism $\varphi$ such that $\varphi(x) = y$.

What does this mean about the graph on an intuitive level? We can, as Marja does in the comments, think of it as saying that if you were to stand on any vertex and look out at the neighboring vertices, you wouldn't be able to tell which particular vertex you were on. In fact, it could be that you're on any vertex!

One consequence of this idea is that, at a minimum, a vertex-transitive graph must be $k$-regular, that is, all vertices must have degree $k$ for some integer $k$. In terms of the adjacency matrix, this means that the matrix has row sums equal to $k$, or that $k$ is an eigenvalue of the all-ones vector.

However, being regular and being transitive are not the same. This is because an automorphism, in a sense, 'picks up' the whole neighborhood of a vertex $x$ and moves them all together, so the neighborhood of every vertex must look exactly the same in the graph -- not just have the same size. This means that if some neighbor of $x$ has an important function in the graph (e.g. if you remove the neighbor the graph becomes disconnected), then the vertex you move it to has to have the same property.

Examples

To illustrate some of these ideas, here are a few examples. First, we have some examples of vertex-transitive graphs. Wolfram MathWorld has a good collection of small examples. Important classes of vertex-transitive graphs include

with the Peterson graph and the Heawood graph being important specific examples. Graphs that are regular but not transitive are a little harder to come by, but there are definitely plenty. Examples include Tietze's graph, Frucht's graph, and a class of graphs called semisymmetric graphs, which the Folkman graph is an interesting example of.

Finally, there are many graphs which are not vertex-transitive. One important class of non-transitive graphs are trees (except $K_2$). In fact, almost all graphs are completely asymmetric, that is, they have no symmetry at all.

Edit: Somehow I blanked on adding Cayley graphs to the list of important vertex-transitive graphs. Doing exercises on Cayley graphs is a great way to gain intuition about what it means for the neighborhood of each vertex to 'look the same.'

$\endgroup$
1
$\begingroup$

Two people independently draw the same specific graph, one marks a node on this graph and tries to describe to the other what node has been marked.

Imagine trying this exercise with a friend using the 3 node path graph. The problem is symmetry, it's ok if you chose the middle node to mark otherwise there is no one answer but you can narrow it down.

Now try with the 4 node cycle graph. You'll find that whatever point you chose you cannot narrow it down at all, therefore this graph is vertex transitive.


vertex transitive graphs:

  • You cannot describe a choice of any strict subset of nodes.
  • extremely symmetric
  • Every node has the same number of neighbours.

.

examples include:

  • cycles
  • complete graphs
  • complete bipartite graphs
  • Graphs of 2 nodes and fewer.
  • Graphs of N dimensional platonic solids.
  • Graphs of extruded polygons.
  • A cycle, then additionally joining nodes N distance apart.
  • the endless square grid
  • the endless cubic grid
  • the endless hexagonal grid
  • Infinite trees where every node has N neighbours. This includes the infinite path.
  • Cartesian (also called direct) product of vertex transitive graphs.
  • Addition of a vertex transitive graph and itself.
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.