<p>I gave a quick look, it looks like you didn't copy the definition right, the second requirement state that if $u$ e $v$ belong to $D$, <strong>not</strong> $C$, then $(u,v) \notin E$, where $D = \bigcup_{e \in C}∂e$. What I guess they mean is that if, say, $(a,b)$ and $(c,d)$ belong to $C$ and $(u,a)$, $(c,v)$ belong to $E$ then $(u,v) \notin E$ otherwise it could be added to $C$ and it would still be a valid matching.</p>

CC BY-SA 3.0
2015-07-07T16:29:56.573Z
Just to clarify, for an edge $e = (u,v)$ does $\partial e$ denote the set $\{u, v\}$?
Lagerbaer
CC BY-SA 3.0
2015-07-07T18:35:38.253Z
I don't think so. From earlier in the paper,  "$∂v$ corresponds to the subset of $E$ of edges which connect to $v$". On edges, the meaning of ∂ doesn't seem to be formally defined, hence I am assuming it is what seems to me to be the natural extension: for an edge $e=(u,v)$, I think $∂e$ represents the subset of edges of $E$ with an endpoint equal to either $u$ or $v$.
drew
CC BY-SA 3.0
2015-07-07T09:39:53.677Z
2015-07-07T09:39:53.677Z
drew
<p>The <a href="https://www.nada.kth.se/~viggo/wwwcompendium/node21.html" rel="nofollow">standard definition</a> of the minimum maximal matching problem is exactly what it sounds like: we are looking for a matching (a set $C$ of edges, no two of which share an endpoint) which is maximal (if $e \not \in C$, then $C \cup \{e\}$ is not a matching) with the smallest possible size (i.e. we wish to minimize $|C|$, over all maximal matchings $C$.)</p>

<p>I'm not sure how to interpret the definition in the paper to which you linked. If you replace the second requirement with your proposed criterion, you end up with a definition of a maximal matching.</p>

CC BY-SA 3.0
2015-07-07T07:14:56.190Z
2015-07-07T07:14:56.190Z
William Hoza
<p>in the following paper <a href="http://journal.frontiersin.org/article/10.3389/fphy.2014.00005/full" rel="nofollow">http://journal.frontiersin.org/article/10.3389/fphy.2014.00005/full</a>
the author describes the minimax problem as follows:</p>

<p>Given a graph G = (V, E), we are looking for a particular coloring $C \subseteq E$ such that no two edges in $C$ share a vertex and -- and this is the part I'm confused about -- if nodes $u$ and $v$ belong to edges in $C$ then the edge (u, v) isn't in $E$.</p>

<p>But that clearly can't make sense because somehow that means that if $(u, v) \in C$ then $(u, v) \not\in E$ but $C \subseteq E$.</p>

<p>Would the correct form of the second requirement be that:
For each $(u, v) \in E - C$ there exists an edge in $C$ that is adjacent to either $u$ or $v$?</p>

<graph-theory><matching>
Is there a typo in this definition of Minimal Maximal Matching
Lagerbaer
# Is there a typo in this definition of Minimal Maximal Matching

(Asked by: username_0 on 2015-07-07)

in the following paper <http://journal.frontiersin.org/article/10.3389/fphy.2014.00005/full>
the author describes the minimax problem as follows:

Given a graph G = (V, E), we are looking for a particular coloring $C \subseteq E$ such that no two edges in $C$ share a vertex and -- and this is the part I'm confused about -- if nodes $u$ and $v$ belong to edges in $C$ then the edge (u, v) isn't in $E$.

But that clearly can't make sense because somehow that means that if $(u, v) \in C$ then $(u, v) \not\in E$ but $C \subseteq E$.

Would the correct form of the second requirement be that:
For each $(u, v) \in E - C$ there exists an edge in $C$ that is adjacent to either $u$ or $v$?

**Tags:** graph-theory, matching

---

## 2 answers

### Answer by username_1 on 2015-07-07. Score: 0 | Accepted answer

I gave a quick look, it looks like you didn't copy the definition right, the second requirement state that if $u$ e $v$ belong to $D$, **not** $C$, then $(u,v) \notin E$, where $D = \bigcup\_{e \in C}∂e$. What I guess they mean is that if, say, $(a,b)$ and $(c,d)$ belong to $C$ and $(u,a)$, $(c,v)$ belong to $E$ then $(u,v) \notin E$ otherwise it could be added to $C$ and it would still be a valid matching.

> **Comments:**
> **username_0**: Just to clarify, for an edge $e = (u,v)$ does $\partial e$ denote the set $\{u, v\}$?  
> **username_1**: I don't think so. From earlier in the paper,  "$∂v$ corresponds to the subset of $E$ of edges which connect to $v$". On edges, the meaning of ∂ doesn't seem to be formally defined, hence I am assuming it is what seems to me to be the natural extension: for an edge $e=(u,v)$, I think $∂e$ represents the subset of edges of $E$ with an endpoint equal to either $u$ or $v$.  

---

### Answer by username_2 on 2015-07-07. Score: 0

The [standard definition](https://www.nada.kth.se/~viggo/wwwcompendium/node21.html) of the minimum maximal matching problem is exactly what it sounds like: we are looking for a matching (a set $C$ of edges, no two of which share an endpoint) which is maximal (if $e \not \in C$, then $C \cup \{e\}$ is not a matching) with the smallest possible size (i.e. we wish to minimize $|C|$, over all maximal matchings $C$.)

I'm not sure how to interpret the definition in the paper to which you linked. If you replace the second requirement with your proposed criterion, you end up with a definition of a maximal matching.


---

