I need help in characterizing the classes of graphs that results from taking the complementary of a tree, i.e., the graph that results from removing the edges of a tree from a complete graph. More formally, let $T=(V,E)$ be an $n$-vertex tree with vertex set $V$ and edge set $E$. Are there known results on the classes of graphs defined by $\overline{T}$?
There are two trivial cases. If $T=S_n$, i.e., is a star tree (one single vertex has degree $n-1$ and the other vertices have degree $1$), we have that $\overline{S_n}=\{v\}\cup K_{n-1}$, i.e., $\overline{S_n}$ is a graph with an isolate vertex (degree $0$) and a $(n-1)$-vertex clique. I've got the feeling that $\overline{P_n}$ (where $P_n$ is an $n$-vertex path graph) has a precise characterization but I can't put a name to it.
If there are no (or few) results about general $T$, can we say something about $\overline{T}$ if $T$ belongs to a class of trees, for example caterpillar trees (trees in which the removal of all leaves produces a path graph), lobster trees (trees in which the removal of all leaves produces a caterpillar tree), ...?
Any help will be appreciated. Thank you.
Note: I also posted this on mathoverflow.
It is not completely clear what kind of characterization you are looking for. Here's one: complements of trees are the maximal graphs not containing a complete bipartite graph as a spanning subgraph. That is, maximal graphs that do not contain a subgraph of the form $K_{s,t}$, where $s+t$ is the number of vertices of the graph. Indeed, a graph is connected if and only if its complement does not contain a subgraph of this form. Since trees are the minimal connected graphs, their complements are the maximal graphs with this property.