0
$\begingroup$

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.

4-regular graph with 6 vertices

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.

$\endgroup$
0
$\begingroup$

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.

$\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.