Here is a theorem from a textbook:

For even number of n , G is a graph with n vertices and no isolated vertice ; the domination number is $$\frac{n}{2}$$ if and only if The components ofG are C4 or the corona HoK1 for any connected graph H (Payan and Xuong )

Here is a question: for which graphs we have $$\gamma(G)=\frac{n-1}{2}$$

In other words: for odd number n and same upper properties ,but $$\frac{n-1}{2}$$ domination number , what are the components of G ?

I would even appreciate linking Thank you


1 Answer 1


(For context for readers who may not be familiar with the corona product, $H \circ K_1$ means we take any connected graph $H$ and add a new degree-$1$ vertex - a leaf vertex - adjacent to every vertex of $H$.)

If we try to generalize to $\gamma(G) = \frac{n-1}{2}$, then we can definitely take any connected $\frac{n+1}{2}$-vertex graph $H$, and add a leaf to all but one vertex of $H$. To dominate each degree-$1$ vertex $v$, we need to either take $v$ or its neighbor, and taking all of their neighbors will give us a dominating set.

However, there are plenty of other examples, so we probably can't characterize them as easily as in the $\frac n2$ case where there's just $C_4$. Mathematica's GraphData command knows about the following:

enter image description here

Out of the $15$ graphs above, $8$ belong to a different infinite family. Take a graph $H$ on $\frac{n+1}{2}$ vertices; it need not be connected, but it should have at most two connected components. To $\frac{n-3}{2}$ of the vertices, add a leaf vertex, as before; add one last vertex (call it $v$) adjacent to both of the remaining vertices of $H$ (call them $w_1, w_2$). If $H$ was not connected, then to make the result connected, the $w_1, w_2$ should be in different components of $H$.

The $\frac{n-1}{2}$ vertices we added are not adjacent and have no common neighbors, so the resulting graph needs a dominating set of size at least $\frac{n-1}{2}$. We can get one by taking either $V(H)-\{w_1\}$ or $V(H) - \{w_2\}$.


You must log in to answer this question.

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