Given a maximal degree $k$ and maximal diameter $d$. We identify 3 nodes, $i$, $j$, and $v$. Can an undirected graph exist, such that:

  • all nodes but $v$ have full degree $k$ ($v$ having a lower degree),
  • the distance between $i$ and $j$ is exactly $d+1$,
  • the distance between $i$ and $v$, and the distance between $j$ and $v$ is exactly $d$,
  • all other distances in the graph are at most $d$.

The distance is measured in the number of nodes that have to be visited on the shortest path between the two nodes.

My intuition would say no, but I'm looking forward to a proof!

  • 1
    $\begingroup$ I think we need at least $k\ge 3$, but I guess this was some implicit assumption. Is it intentional that your distance definition sets two adjacent vertices at distance two? Could you explain a bit about why your intuition says no? $\endgroup$ – M. Winter Oct 31 '18 at 17:11

It is not impossible in general. Here is a graph with $k=3$ and $d=10$ (if I understood your distance definition correctly).

Note that the colored vertices are the ones farthest away from the central vertex (for their resp. "component"). This helps in verifying that the distance of any two vertices other than $i$ and $j$ is always $\le d$.


Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

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