<p>Yes, it implies that $|I| \geq |H|$ but it does not imply $I$ contains only vertices of degree 1. The edges joining $H$ to $I$ <em>contain</em> an H-covering matching, but there can be many more edges. See, for instance, D. Marx' slides on crown reduction: <a href="http://www.cs.bme.hu/~dmarx/papers/marx-agape09-slides-print.pdf" rel="nofollow">http://www.cs.bme.hu/~dmarx/papers/marx-agape09-slides-print.pdf</a></p>

CC BY-SA 3.0
2014-11-20T17:03:07.833Z
2014-11-20T17:03:07.833Z
JimN
<p>I'm currently reading "Invitation to Fixed-Parameter Algorithms" by Rolf Niedermayer. Page 69 gives the following definition of the crown of a graph, which I do not quite understand:</p>

<p>A crown of a graph $G = (V,E)$ consists of $H\subseteq V$ and $I \subseteq V$ with $H \cap I = \varnothing$ s.t. the following three conditions hold:</p>

<ul>
<li>$H = N(I)$ </li>
<li>$I$ forms an independent set</li>
<li>the edges connecting $H$ and $I$ contain a matching in which all elements of $H$ are matched.</li>
</ul>

<p>$N(I)$ is the neighborhood of vertices $I$, i.e., $N(I) = \{u \mid v \in I \land  (u,v) \in E\}$.</p>

<p>I'm stuck with the third point: I'm interpreting it as "in the bipartite graph $(H, I, F)$ with $F = \{(u,v) \in E \mid u\in I \land v \in H\}$ there is a matching $M\subseteq F$ s.t. $\forall v \in H: \exists (u,v) \in F$, i.e., each vertex in $H$ is covered by an edge in the matching $M$".</p>

<p>But does this not imply that  $|I| \geq |H|$ since there can at most be $|I|$ non-adjacent edges connected to vertices in $I$? This would imply that $I$ is a set of vertices that have degree 1, which surely is not the intention since a crown is intended to be a generalization of 1-connected vertices.</p>

<p>What am I missing?</p>

CC BY-SA 3.0
2014-11-20T14:01:07.587Z
Your definition of $N(I)$ is neither necessary nor correct.
Yixin Cao
CC BY-SA 3.0
2014-11-20T14:04:55.637Z
Could you please explain why?
mort
CC BY-SA 3.0
2014-11-20T14:09:33.653Z
$H$ is supposed to be a generalization of the cutpoint (a 1-connected vertex?), not $I$.
Yixin Cao
<graph-theory><parameterized-complexity><matching>
Graph theory: definiton of the crown of a graph
mort
# Graph theory: definiton of the crown of a graph

(Asked by: username_0 on 2014-11-20)

I'm currently reading "Invitation to Fixed-Parameter Algorithms" by Rolf Niedermayer. Page 69 gives the following definition of the crown of a graph, which I do not quite understand:

A crown of a graph $G = (V,E)$ consists of $H\subseteq V$ and $I \subseteq V$ with $H \cap I = \varnothing$ s.t. the following three conditions hold:

* $H = N(I)$
* $I$ forms an independent set
* the edges connecting $H$ and $I$ contain a matching in which all elements of $H$ are matched.

$N(I)$ is the neighborhood of vertices $I$, i.e., $N(I) = \{u \mid v \in I \land (u,v) \in E\}$.

I'm stuck with the third point: I'm interpreting it as "in the bipartite graph $(H, I, F)$ with $F = \{(u,v) \in E \mid u\in I \land v \in H\}$ there is a matching $M\subseteq F$ s.t. $\forall v \in H: \exists (u,v) \in F$, i.e., each vertex in $H$ is covered by an edge in the matching $M$".

But does this not imply that $|I| \geq |H|$ since there can at most be $|I|$ non-adjacent edges connected to vertices in $I$? This would imply that $I$ is a set of vertices that have degree 1, which surely is not the intention since a crown is intended to be a generalization of 1-connected vertices.

What am I missing?

**Tags:** graph-theory, parameterized-complexity, matching
> **Comments:**
> **username_1**: Your definition of $N(I)$ is neither necessary nor correct.  
> **username_0**: Could you please explain why?  
> **username_1**: $H$ is supposed to be a generalization of the cutpoint (a 1-connected vertex?), not $I$.  

---

## 1 answers

### Answer by username_2 on 2014-11-20. Score: 2 | Accepted answer

Yes, it implies that $|I| \geq |H|$ but it does not imply $I$ contains only vertices of degree 1. The edges joining $H$ to $I$ *contain* an H-covering matching, but there can be many more edges. See, for instance, D. Marx' slides on crown reduction: <http://www.cs.bme.hu/~dmarx/papers/marx-agape09-slides-print.pdf>


---

