Induced Cycles in Graphs
| Autor: | Henning, Michael A., Joos, Felix, Löwenstein, Christian, Sasse, Thomas |
|---|---|
| Rok vydání: | 2014 |
| Předmět: | |
| Druh dokumentu: | Working Paper |
| Popis: | The maximum cardinality of an induced $2$-regular subgraph of a graph $G$ is denoted by $c_{\rm ind}(G)$. We prove that if $G$ is an $r$-regular graph of order $n$, then $c_{\rm ind}(G) \geq \frac{n}{2(r-1)} + \frac{1}{(r-1)(r-2)}$ and we prove that if $G$ is a cubic claw-free graph on order $n$, then $c_{\rm ind}(G) > 13n/20$ and this bound is asymptotically best possible. Comment: 17 pages |
| Databáze: | arXiv |
| Externí odkaz: |
|