2
$\begingroup$

I have an unweighted undirected graph $G(V, E)$ of diameter 3 and a subset $T\subseteq V$ of these vertices. I want to find the minimum tree $(V', E')$ that contains all vertices in $T$, minimizing the number of nodes $|V'|$.

Is it true that $|V'|\le 2|T|$? If $G$ is of diameter 2 it is easy to prove that this is true. Also for diameter 4, it is not true always since we can take a path graph of 5 vertices with $T$ as two leaves.

$\endgroup$
3
$\begingroup$

This is an interesting question.

It is not true that $|V'|$ is always less than or equal to $2|T|$. Here is the smallest example of $G$ and $T$ where $|V'|$ must be greater than $2|T|$.

An example of a graph of diameter 3 where a subtree to span the given 3 nodes must contain at least 7 nodes, created at https://graphonline.ru/en/?graph=tIKAJTyDudVDUxXs

Graph $G$ as depicted above has 9 vertices $A,A_1,A_2,B,B_1,B_2,C,C_1,C_2$ and 12 edges $AA_1, A_1A_2, A_2A,$ $BB_1,B_1B_2,B_2B,$ $CC_1, C_1C_2, C_2C,$ $A_1B_2, B_1C_2, C_2A_1$. It is easy to check the diameter of $G$ is 3.

Let $T=\{A,B,C\}$. Suppose $T'=(V',E')$ is a minimal tree in $G$ that spanns $T$.

  • If $V'$ contains all 9 vertices, then $|V'|=9$.
  • Otherwise, WLOG, assume $V'$ does not contain $A_1$. If anyone of $A_2$, $C_1$, $C_2$ and $B_1$ is not in $T'$, then $A$ and $B$ will not be connected in $T'$. Since $A$ and $B$ are connected in $T'$, all of those 4 vertices must be in $T'$. So $|V'|\ge3+4=7$.

So $|T'|\gt 6= 2|T|.$

Exercise 1. Verify that the following two graphs are also examples where $|V'|$ must be greater than $2|T|$ with $T=\{A, B, C\}$

An example of a graph of diameter 3 with 10 vertices and 15 edges where a subtree that spans 3 node A, B and C must contain at least 7 nodes, created at https://graphonline.ru/en/?graph=dvCkpGmiVCvZsDwz An example of a graph of diameter 3 with 12 vertices and 15 edges where a subtree that spans 3 node A, B and C must contain at least 7 nodes, created at https://graphonline.ru/en/?graph=aBfaNOIrXdEmBiPe

Exercise 2. (less than 1 minute) If $|T|=3$, then $|V'|\le7$.

Exercise 3. Let $n\ge3$. Construct $G$ and $T$ such that $G$ is connected of diameter 3, $|T|=n$ and $|V'|\gt 2|T|$. (Hint, imitate the simpler example in exercise 2.)

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