1
$\begingroup$

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.

$\endgroup$
0

1 Answer 1

2
$\begingroup$

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.

$\endgroup$
2
  • 2
    $\begingroup$ 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? $\endgroup$
    – Juho
    Oct 13 at 6:44
  • 1
    $\begingroup$ @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. $\endgroup$
    – Juho
    Oct 16 at 11:37

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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