Induced Cycles in Graphs |
| |
Authors: | Michael A Henning Felix Joos Christian Löwenstein Thomas Sasse |
| |
Institution: | 1.Department of Pure and Applied Mathematics,University of Johannesburg,Auckland Park,South Africa;2.Institute of Optimization and Operations Research,Ulm University,Ulm,Germany |
| |
Abstract: | The maximum number vertices of a graph G inducing a 2-regular subgraph of G is denoted by \(c_\mathrm{ind}(G)\). We prove that if G is an r-regular graph of order n, then \(c_\mathrm{ind}(G) \ge \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_\mathrm{ind}(G) > \frac{13}{20}n\) and this bound is asymptotically best possible. |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|