# 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.

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.