تقرير
On some Graphs with a Unique Perfect Matching
| العنوان: | On some Graphs with a Unique Perfect Matching |
|---|---|
| المؤلفون: | Chaplick, S., Fürst, M., Maffray, F., Rautenbach, D. |
| سنة النشر: | 2017 |
| المجموعة: | Computer Science Mathematics |
| مصطلحات موضوعية: | Mathematics - Combinatorics, Computer Science - Discrete Mathematics |
| الوصف: | We show that deciding whether a given graph $G$ of size $m$ has a unique perfect matching as well as finding that matching, if it exists, can be done in time $O(m)$ if $G$ is either a cograph, or a split graph, or an interval graph, or claw-free. Furthermore, we provide a constructive characterization of the claw-free graphs with a unique perfect matching. |
| نوع الوثيقة: | Working Paper |
| URL الوصول: | http://arxiv.org/abs/1712.04228 |
| رقم الأكسشن: | edsarx.1712.04228 |
| قاعدة البيانات: | arXiv |
| الوصف غير متاح. |