Domination number of a graph G

[Robb]

Homework Statement

Determine the domination number of the graph G in figure 17

Relevant Equations

N/A

$\gamma(G) \leq 4$
$Claim: \gamma(G) = 4$
Since $\Delta(G) = 3$ a vertex can dominate at most four vertices. There are eight vertices equivalent to $\Delta(G)$, so these are dominated by two vertices. The remaining four vertices are of degree two which require two vertices to dominate them, therefore, requiring four vertices to dominate the given graph G, hence $\gamma(G) = 4$.

My instructor says I need to show why $\gamma(G) \neq 3$ using partite sets |U| = |W| = 6. I'm not sure how to go about this last step. Any help would be much appreciated. Attached is the graph in question. Also, is there a way to create graphs on PF?

 

[Antarres]

Just like you said, $\Delta(G)=3$, so a vertex can dominate four vertices, at most. Therefore, since the graph has 12 vertices, if we prove that $\gamma(G) \neq 3$, then it is equal to 4 by construction that you have made.

In order to have $\gamma(G) = 3$, that means that those three vertices must dominate four vertices each, AND, that no vertex should be dominated by two different vertices.
However, if we try to establish this requirement with two vertices, we will find that we can't pick a third one such that the requirement is still satisfied. Therefore, we will have a contradiction. That's the idea. Hope that helps.

 

[WWGD]

Can't you produce a bound by using the degree of the vertices? Deg(v)=3 for all v, so, at best $3 \cdot 3 =9 < 12$

 

[Antarres]

He used $\Delta(G)$, though, which is maximum degree of vertices. It is clear that domination number is bounded below by three, and his construction gives a case when it's 4. So he just needs to prove that it isn't three, hope he did it so far, it's not too hard.

 

[WWGD]

He used Δ(G)Δ(G), though, which is maximum degree of vertices. It is clear that domination number is bounded below by three, and his construction gives a case when it's 4. So he just needs to prove that it isn't three, hope he did it so far, it's not too hard.

But then if the max degree is 3, then 3 vertices can be incident with at most 3⋅33⋅3 vertices, right? Then show incident vertices must overlap. Doesn't that do it? EDIT: True, 3+3(3)=12. But we can show there must be at least one vertex incident with any 3 other vertices, so we get less than 12 total.

 

[Antarres]

Yeah but domination number counts the vertex that dominates, as well, every vertice that has a vertex degree of 3, dominates four vertices, itself and three adjacent ones. But yeah, you have to show that even if you try to do $3 \cdot 4$ in this case, you will get overlapping, so it doesn't work.

 

[Robb]

When I asked my instructor about it she said to use partite sets. Hence, |U| = |W| = 6. One vertex from W can dominate 3 vertices in U and one vertex in U can dominate 3 vertices in W. This leaves 2 vertices in each set U and W. These must be dominated by two vertices. Hence, $\gamma \neq 3$.

 

[Antarres]

Yeah, that's basically what I hinted @WWGD.
@Robb I don't know which sets you chose for U and W, I went with horizontal ones, but what you said in last post doesn't hold either way. If you pick a subgraph U with 6 vertices, you can't find a vertex in U that dominates 3 vertices in W, or vice versa. You find that each vertex in U dominates 3 vertices in itself and one in W. So however you try to cover the graph, you will get that two vertices with no overlaps will leave the graph with vertices that are not connected, therefore overlaps are inevitable. Which means $\gamma \neq 3$.

EDIT: Nevermind, I figured what you meant probably, you just colored it in two colors, in that case you're right, every vertex from U dominates 3 from W and vice versa. That leaves 2 vertices in both U and W, however no vertex in this case can dominate two vertices in it's own set, so you can conclude $\gamma \neq 3$. That's another way to look at it.

 

[Robb]

Yeah, that's basically what I hinted @WWGD.
@Robb I don't know which sets you chose for U and W, I went with horizontal ones, but what you said in last post doesn't hold either way. If you pick a subgraph U with 6 vertices, you can't find a vertex in U that dominates 3 vertices in W, or vice versa. You find that each vertex in U dominates 3 vertices in itself and one in W. So however you try to cover the graph, you will get that two vertices with no overlaps will leave the graph with vertices that are not connected, therefore overlaps are inevitable. Which means $\gamma \neq 3$.

EDIT: Nevermind, I figured what you meant probably, you just colored it in two colors, in that case you're right, every vertex from U dominates 3 from W and vice versa. That leaves 2 vertices in both U and W, however no vertex in this case can dominate two vertices in it's own set, so you can conclude $\gamma \neq 3$. That's another way to look at it.

Right, I get what you're saying. Going to revisit.

 

[Robb]

Yeah, that's basically what I hinted @WWGD.
@Robb I don't know which sets you chose for U and W, I went with horizontal ones, but what you said in last post doesn't hold either way. If you pick a subgraph U with 6 vertices, you can't find a vertex in U that dominates 3 vertices in W, or vice versa. You find that each vertex in U dominates 3 vertices in itself and one in W. So however you try to cover the graph, you will get that two vertices with no overlaps will leave the graph with vertices that are not connected, therefore overlaps are inevitable. Which means $\gamma \neq 3$.

EDIT: Nevermind, I figured what you meant probably, you just colored it in two colors, in that case you're right, every vertex from U dominates 3 from W and vice versa. That leaves 2 vertices in both U and W, however no vertex in this case can dominate two vertices in it's own set, so you can conclude $\gamma \neq 3$. That's another way to look at it.

I thought it was ok. Thanks for the help..., again!