6
$\begingroup$

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)$?

$\endgroup$
3
  • $\begingroup$ 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$, [...]"? $\endgroup$
    – ruakh
    Apr 30, 2021 at 6:02
  • $\begingroup$ @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. $\endgroup$ Apr 30, 2021 at 12:44
  • $\begingroup$ Thanks for the correction, @ruakh. I already edited the post. $\endgroup$ May 1, 2021 at 18:42

2 Answers 2

5
$\begingroup$

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.

$\endgroup$
2
  • $\begingroup$ Nice solution :) $\endgroup$
    – Asinomás
    Apr 29, 2021 at 21:39
  • $\begingroup$ Thanks. It's a very good explanation. $\endgroup$ Apr 29, 2021 at 23:20
5
$\begingroup$

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

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

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .