Domination number of a path graph P(n)

1k Views Asked by At

I know that P(n) is a path graph which has vertices like V(P)={V1,V2,...,Vn}

What is the domination number of this graph? I pose some examples for myself and I realized that the domination number of a path graph with n vertices is uprounding of $$\frac{n}{3}$$ But It is not a proof , How can I prove it by using some theories I know ? (And I know some basic theories)

2

There are 2 best solutions below

1
On BEST ANSWER

This will be similar to LVM's answer, maybe just extrapolating a bit.

You don't need any theorems or heavy-duty machinery to answer this, just, as LVM suggests, showing that the "weak" inequalities hold in either direction. First, $\Delta(P_n) = 2$, so any given vertex may only dominate, at most, 2 vertices besides themselves; hence $\lceil \frac{n}{3} \rceil$ is a lower bound. On the other hand, starting with the second vertex at one end of the path and picking every third vertex thereafter (along with the final vertex when $n \not\equiv 0$ (mod 3)) gives a dominating set of size $\lceil \frac{n}{3} \rceil$, yielding our desired matching upper bound. At this point, we may conclude that, indeed, $\gamma(P_n) = \lceil \frac{n}{3} \rceil$.

This probably wasn't far off your original intuition, and indeed constitutes a full proof. No higher-level methods or theorems are necessary; all we needed to do to show that $\gamma(P_n) = \lceil \frac{n}{3} \rceil$ was that both of the inequalities $\gamma(P_n) \leq \lceil \frac{n}{3} \rceil$ and $\gamma(P_n) \geq \lceil \frac{n}{3} \rceil$ hold, which requires only elementary methods.

Remark: Keep this method of showing both loose inequalities hold in mind as you explore further in graph theory. It is akin to showing that two sets are equal by showing that either is a subset of the other. The technique is useful in many foundational results of graph theory, and, of course, other branches of math as well. Hope this has helped.

0
On

First show that there exist a dominating set with $\lceil \frac{n}{3} \rceil$ vertices. Constructing the dominating set is probably the most simple way of doing it.

Then show that it can't be done with less vertices, for example by showing how many vertices a single vertex dominates in a path.