# Searching for a Connected Graph with Vertex Count $n$ and Path Lengths Less Than $k$

Question:

I'm looking for a type of connected graph where the number of vertices is $$n$$ and every pair of vertices is connected by a path with a length less than $$k$$, where $$k$$ is a constant. Are there any types of graphs that satisfy this property, apart from complete graphs?

If anyone has insights or suggestions on different types of graphs or specific properties that meet these criteria, I would greatly appreciate it.

The diameter of a graph is the length of the longest shortest path. Thus, you are describing graphs of bounded diameter, or graphs diameter $$k-1$$ in your case. Complete graphs you mention have diameter one.

• I'm afraid there is no easy characterization for diameter larger than 1 graphs. You can see that there are all sorts of diameter two graphs. In your application, would something else do? Can you sample and reject unsuitable graphs?
– Juho
Oct 13, 2023 at 6:44
• @Jxb you should be able to find an explicit construction, yes. If you get stuck, you can always ask a new, focused question detailing what you tried.
– Juho
Oct 16, 2023 at 11:37