Does any connected graph G have a spanning tree T with the same domination number?

Let $$G$$ be a simple graph. A spanning tree of a connected graph $$G$$ is an acyclic connected subgraph $$T$$ of $$G$$ such that $$V_T = V_G$$.

A dominating set of $$G$$ is a subset $$W$$ of $$V_G$$ such that every vertex in $$V_G\setminus W$$ is adjacent to some vertex in $$W$$. The domination number of $$G$$, $$\gamma(G)$$, is the minimum on the cardinalities of the dominating sets of $$G$$.

Evidently, for any spanning subgraph $$H$$ of $$G$$, the domination number of $$H$$ is lower-bounded by the domination number of $$G$$, i.e. $$\gamma(G) \le \gamma(H)$$. Particularly, for every spanning tree $$T$$ of a connected graph $$G$$, $$\gamma(T) \ge \gamma(G)$$.

Does every connected graph $$G$$ have a spanning tree $$T$$ such that $$\gamma(G)=\gamma(T)$$?

• Am I missing something, or should the paragraph that starts "Evidently, for any subgraph $H$ of $G$, [...]" instead start "Evidently, for any subgraph $H$ of $G$ with $V_H = V_G$, [...]"? Apr 30, 2021 at 6:02
• @ruakh Yes, it should - you'll get a much smaller domination number if you just take a subgraph with a single vertex. In other words, this works for any spanning subgraph - like a spanning tree. Apr 30, 2021 at 12:44
• Thanks for the correction, @ruakh. I already edited the post. May 1, 2021 at 18:42

Yes, and what's more, for any dominating set $$W$$ of $$G$$, there is a spanning tree $$T$$ for which $$W$$ is also a dominating set.

Begin choosing $$T$$ by going through all vertices $$v \notin W$$, and adding an edge from $$v$$ to some vertex $$w \in W \cap N(v)$$. This gives us a star forest in which $$W$$ is a dominating set. It can be extended to a spanning tree however you like.

• Nice solution :) Apr 29, 2021 at 21:39
• Thanks. It's a very good explanation. Apr 29, 2021 at 23:20

Assume $$G$$ is a graph and $$X$$ is a set such that every vertex is in $$X$$ or adjacent to a vertex in $$X$$.

We prove there is a spanning tree $$T$$ of $$G$$ such that every vertex is in $$X$$ or adjacent to a vertex in $$X$$. For each vertex $$v$$ not in $$X$$ we add exactly one edge from $$v$$ to $$X$$ that is in $$G$$. After doing this the graph has no cycles, because it is bipartite, and all the vertices in $$G\setminus X$$ have degree $$1$$. We can make this graph into a tree by adding edges in $$G$$.

• Nice solution :) Apr 29, 2021 at 21:39
• Thank you so much. The idea is so simple that I don't know how I didn't think of it before. Apr 29, 2021 at 23:18
• If it helps I feel that exact way a large chunk of the times I see a solution. Apr 29, 2021 at 23:20