A lower bound on the acyclic matching number of subcubic graphs
| Autor: | Maximilian Fürst, Dieter Rautenbach |
|---|---|
| Rok vydání: | 2018 |
| Předmět: |
Discrete mathematics
010102 general mathematics 0102 computer and information sciences 01 natural sciences Upper and lower bounds Graph Theoretical Computer Science Combinatorics 010201 computation theory & mathematics FOS: Mathematics Mathematics - Combinatorics Discrete Mathematics and Combinatorics Combinatorics (math.CO) 0101 mathematics Mathematics |
| Zdroj: | Discrete Mathematics. 341:2353-2358 |
| ISSN: | 0012-365X |
| Popis: | The acyclic matching number of a graph G is the largest size of an acyclic matching in G , that is, a matching M in G such that the subgraph of G induced by the vertices incident to edges in M is a forest. We show that the acyclic matching number of a connected subcubic graph G with m edges is at least m ∕ 6 except for two graphs of order 5 and 6. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|
Full Text from ScienceDirect