Abstract
Suppose every vertex of a graph G has degree k or k + 1 and at least one vertex has degree k + 1. It is shown that if k ≥ 2q - 2 and q is a prime power then G contains a q-regular subgraph (and hence an r-regular subgraph for all r < q, r ≡ q (mod 2)). It is also proved that every simple graph with maximal degree Δ ≥ 2q - 2 and average degree d > ( (2q - 2) (2q - 1))(Δ + 1), where q is a prime power, contains a q-regular subgraph (and hence an r-regular subgraph for all r < q, r ≡ q (mod 2)). These results follow from Chevalley's and Olson's theorems on congruences.
Original language | English (US) |
---|---|
Pages (from-to) | 79-91 |
Number of pages | 13 |
Journal | Journal of Combinatorial Theory, Series B |
Volume | 37 |
Issue number | 1 |
DOIs | |
State | Published - Aug 1984 |
Externally published | Yes |
All Science Journal Classification (ASJC) codes
- Theoretical Computer Science
- Discrete Mathematics and Combinatorics
- Computational Theory and Mathematics