-1
$\begingroup$

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!

Improve this question
$\endgroup$
1
  • 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
    Commented Oct 31, 2018 at 17:11

1 Answer 1

Reset to default
3
$\begingroup$

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

Improve this answer
$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .