# Build a 4-regular, vertex-transitive, least diameter graph with v vertices

How to build a 4-regular, vertex-transitive, 'least diameter' graph with $v$ vertices?

This implies to know what is the minimum diameter of a 4-regular vertex-transitive graph with $v$ vertices.

# What I found

If $v <= 4 + 1$, the diameter is $1$, and in the particular case $v = 4 + 1$, the only matching graph is $K_5$.

In the case $v = 6$, the graph shown below matches, with a diameter of $2$. The diameter can't be less than 2, since it would then be 1, meaning every vertex is adjacent to the five others, what contradicts with the 4-regularity. The cases $v=6,7,8$ and $9$ are diameter 2 as well and can be treated with the same pattern: putting a star in a polygon. Example of star used :

• 6: Two triangles (A double edge between opposed vertices works too)
• 7: Star formed by jumping over one vertex. (Over two vertices works too)
• 8: Two squares (The star formed by jumping over two vertices works too)
• 9: Three triangles (Seems to be the only possibility)

For the case $v=10$, the least diameter is 2 too. A matching graph can be obtained from Petersen graph, by adding parallel edges to the ones linking the pentagon to the central star.

## 1 Answer

There are restricted versions of the degree-diameter problem for vertex-transitive graphs. The problem asks for the following: Given that a graph $G$ is vertex-transitive, has maximum degree $\Delta$ and diameter $D$, what is the maximum possible number of vertices it can have? See the combinatorics wiki for latest results.