1
$\begingroup$

Let's say we have a graph $T$, which is also a spanning tree of a graph $G$, $T$ is connected, now let's say the diameter of $T$ is $x$.

Now, what would be the diameter of :

$$ (T \cup T^c) + (T \cup T^c) $$

where $T^c$ is the complement of $T$, and we assume that $T$, $T^c$ are the different copies of $T$.

What I know is since $T$ and $T^c$ are disjoint, the union of them will be a disconnected graph, but I'm not clear how the join operation denoted by $+$ sign here change the final resulting graph. Is it still disconnected? (which I hope not)

My idea was that the union of $T$ and $T^c$ would be a complete graph, but it seems like it's wrong if I plot a sample graph. Hence, I'm looking for help. Thank you for any support in advance.

$\endgroup$
3
  • $\begingroup$ This depends a little on the definitions. What do you mean by union specifically, and what do you mean by $+$? $\endgroup$ Dec 3, 2021 at 4:25
  • $\begingroup$ The union of two graphs G 1 = (V_1 ,E_1 ) and G2 = (V_2 ,E_2 ), where V_1 ∩ V_2 = ∅ , is the graph G1 ∪ G2 = (V_1 ∪ V_2 ,E_1 ∪ E_2 ). And the + signifies the Join operation of two graphs, which follows the standard definition of join operation of two graphs. $\endgroup$ Dec 3, 2021 at 4:39
  • $\begingroup$ And this is the definition of join: Let G1 = (V_1 ,E_1 ) and G2 = (V_2 ,E_2 ) be two graphs such that V 1 ∩ V 2 = ∅ . The join G1 + G2 is the graph that has the vertices and the edges of the original graphs, in addition to the edges that connect all the vertices of G with all the vertices of H. $\endgroup$ Dec 3, 2021 at 4:42

1 Answer 1

1
$\begingroup$

The union of $T$ and its complement $T^{c}$ is a complete graph $K_n$, where $n$ is the number of nodes in $T$. The diameter of a complete graph is ofcourse 1, since all vertices are connected to each other by distance 1. Hence, since the join of graphs $G+H$ connects every node of $G$ to each one of $H$, we obtain that the problem's join graph $$(T\cup T^c) + (T\cup T^c) = K_n + K_n = K_{2n}$$ is also complete, so its diameter is 1.

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