Graphs in which every spanning tree is an independency tree

Question

It follows from this question and the corresponding answers, that the complete graphs and the cycles are precisely the graphs $G$ having the property that, for every spanning tree $T$ of $G$, the set of leaves of $T$ is a clique in $G$.

Motivated by this fact, I am looking for a characterization of all (connected) graphs $G$ having the property that, for every spanning tree $T$ of $G$, the set of leaves of $T$ is an independent set in $G$. (Such spanning trees are called independency trees in the literature.)

Answer 1

A graph G has all spanning trees independency if and only if G does not contain two adjacent vertices v and w, neither of degree one, such that the graph G' formed by removing v and w and all their incident edges is connected. (I think this is the same as what McKay said in a comment.)

For, if G' is connected, then a spanning tree of G' plus two edges connecting it to v and w (which exist by the degree constraint) is a non-independency tree of G. And conversely, if T is a non-independency tree, let vw be an edge connecting two leaves of T; then v and w have the stated property.

As a check that this is a useful characterization (and not just a restatement of the definition): Based on this, it is trivial to test in polynomial time whether a given graph has all spanning trees independency, whereas a direct translation of the original definition into an algorithm would be exponential.

ETA: In response to McKay's request for a more structural characterization, here's a description of the graphs with all trees independency, rather than (as above) of the complementary class of graphs. Given a graph G, partition G into its biconnected components, and partition each nontrivial biconnected component into its SPQR tree (system of triconnected components). Then G has all trees independency if and only if, for every non-virtual edge of an R or S node of one of these SPQR trees, at least one endpoint is an articulation vertex. (This is because the edges that do not separate two triconnected components are exactly these edges, so to avoid leaving G' connected they have to instead separate two biconnected components.) And again, this is an improved characterization and not just a restatement of the earlier characterization, because it gives a linear time algorithm while a naive implementation of the earlier characterization would be a higher polynomial.

Answer 2

Here's something more about these graphs.

Theorem: Let $G$ be connected graph with $\geq 3$ vertices. Consider the next properties:

1) Every edge in $G$ is incident to a cut vertex.

2) $G$ has all spanning trees independency.

3) The set of all cut vertices in $G$ is dominating.

Then 1)$\Rightarrow$2)$\Rightarrow$3).

Proof

1)$\Rightarrow$2): Let $e=uv\in E(G)$ and $u$ is a cut vertex in $G$. Assume that $v$ isn't a leaf. Then $G-u$ is disconnected and $d_{G-u}(v)\geq 1$. Therefore $G-\{u,v\}$ is also disconnected. Thus $\{u,v\}$ is a separator in $G$.

2)$\Rightarrow$3): Assume that for some non-cut vertex $u\in V(G)$ the set $N(u)$ consists of non-cut vertices. Then for all $v\in N(u)$ the set $\{u,v\}$ is a separator in $G$. It means that $v$ is a cut vertex in $G-u$.

If there exists a component $A$ of $G-\{u,v\}$ such that $V(A)\cap N(u)=\emptyset$, then $A$ is also a component of $G-v$. It means that $v$ is a cut vertex in $G$ which is a contradiction. Thus every component of $G-\{u,v\}$ contains the vertices from $N(u)$.

Therefore, each vertex $v\in N(u)$ separates the set $N(u)-v$ in $G-u$. But this contradicts the connectedness of $G-u$. $\boxtimes$

Two counterexamples to the reverse statements of the Theorem.

2)$\nRightarrow$1):

3)$\nRightarrow$2): $K_{1}+(P_{2}\cup K_{1})$.

Answer 3

For the sake of completeness here's the proof of McKay's characterization. By $L(G)$ I denote the set of all leaves in $G$.

Theorem: Every spanning tree in $G$ is independency tree if and only if every edge $e=uv\in L(G)$ is incident to a leaf or the set $\{u,v\}$ is a separator in $G$.

Proof: $\Rightarrow$ Assume that for some edge $e=uv\in E(G)$ the set $\{u,v\}$ isn't a separator and $u,v\notin L(G)$. Then the graph $H=G-\{u,v\}$ is connected.

Now fix some spanning tree $T'\subset H$.

Since $u,v\notin L(G)$, it holds that $A=N_{G}(u)\cap V(T')\neq\emptyset$ and $B=N_{G}(v)\cap V(T')\neq\emptyset$. Choose $w_{1}\in A$, $w_{2}\in B$ and put $$V(T)=V(G),\ E(T)=E(T')\cup\{uw_{1},vw_{2}\}.$$ Clearly, $T$ is a spanning tree in $G$ and $u,v\in L(T)$ with $uv\in E(G)$ which is a contradiction.

$\Leftarrow$ Let $T\subset G$ be some spanning tree and $u,v\in L(T)$. Clearly, $G-\{u,v\}$ is connected. Therefore the set $\{u,v\}$ never a separator.

Again, assume that $e=uv\in E(G)$. Then $d_{G}(u)\geq 2$ and $d_{G}(v)\geq 2$. It means that $u,v\notin L(G)$. Again, a contradiction.

Answer 4

Here's a construction showing that the answer may be a bit complicated. Take any connected graph $G$, then add an additional set $X$ of $|V(G)|$ vertices, then add a perfect matching $M$ between $V(G)$ and $X$. Let the resulting graph be $G'$. It is easy to see that any spanning tree $T'$ of $G'$ must consist of $M \cup T$, where $T$ is a spanning tree of $G$. Thus, the only leaves of $T'$ are the vertices in $X$, which are indeed an independent set.

Therefore, the structure of such graphs may not be so nice, since any connected graph can be extended in this way to be in the class.