Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
419236 | Discrete Applied Mathematics | 2016 | 7 Pages |
Abstract
We show that a cubic graph GG of order nn has an induced 2-regular subgraph of order at least •n−24−4k, if GG has no induced cycle of length more than kk,•5n+68, if GG has no induced cycle of length more than 4, and n>6n>6, and•(14+ϵ)n, if the independence number of GG is at most (38−ϵ)n. To show the second result we give a precise structural description of cubic 4-chordal graphs.
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics
Authors
Michael A. Henning, F. Joos, C. Löwenstein, D. Rautenbach,