Timeline for Induced matching number
Current License: CC BY-SA 4.0
11 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Oct 30, 2022 at 23:31 | history | edited | Tony Huynh | CC BY-SA 4.0 |
deleted 16 characters in body; edited tags
|
| Dec 27, 2019 at 14:35 | vote | accept | user177523 | ||
| May 13, 2019 at 12:41 | answer | added | Tony Huynh | timeline score: 3 | |
| May 23, 2017 at 8:03 | comment | added | Peter Heinig | And on the topic of your question being too general: a nearly-tautological answer would be "Let $\mathfrak{M}$ denote the set of all largest induced matchings of $G$. Then $x\in V(G)$ is a vertex with the property $a(G\setminus x)<a(G)$ if and only if $x \in \bigcap_{\mathcal{M}\in\mathfrak{M}} (\cup\mathcal{M})$." This is a characterization of sorts. Since $\mathfrak{M}$ can be expected to typically have little humanly understandable structure (whatever that means), this is not an enlightening characterization, though. | |
| May 23, 2017 at 7:57 | comment | added | Peter Heinig | Tangential comment on the topic of induced matchings being more complicated than matchings: while many objects attached to matchings can be efficiently found for bipartite graphs, it was proved by L.J. Stockmeyer, V.V. Vazirani, and K. Cameron around thirty years ago that even restricted to bipartite graphs, it is an NP-complete problem to find a maximum induced matching in a given graph. Intuitively: the hardness of the maximum-independent-set problem infects the induced-matching problem. I recognize that your question is not about the set of maximum matchings (though closely related to it). | |
| S May 23, 2017 at 7:52 | history | suggested | Peter Heinig | CC BY-SA 3.0 |
Formulation "the vertex $x$ such that" was ungrammatical. Corrected.
|
| May 23, 2017 at 7:42 | comment | added | Peter Heinig | Would you please be more specific: are you asking "send me all characterizations of this set that you happen to know" (at one extreme there is is always the tautological one, at the other there is always the 'discrete characterization' consisting of the list of all such sets---of course, both are maximally unenlightening), or are you asking for a specific type of characterization? @selva | |
| May 23, 2017 at 7:38 | review | Suggested edits | |||
| S May 23, 2017 at 7:52 | |||||
| S May 23, 2017 at 7:27 | history | suggested | Glorfindel | CC BY-SA 3.0 |
thanks removed as per https://meta.stackexchange.com/q/2950/295232
|
| May 23, 2017 at 7:17 | review | Suggested edits | |||
| S May 23, 2017 at 7:27 | |||||
| May 23, 2017 at 4:48 | history | asked | user177523 | CC BY-SA 3.0 |