Regular subgraphs of almost regular graphs |
| |
Authors: | N Alon S Friedland G Kalai |
| |
Affiliation: | Department of Mathematics, Massachusetts Institute of Technology, Cambridge, Massachusetts, USA;Institute of Mathematics, Hebrew University of Jerusalem, Jerusalem, Israel;Department of Mathematics, Massachusetts Institute of Technology, Cambridge, Massachusetts, USA |
| |
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 , 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. |
| |
Keywords: | |
本文献已被 ScienceDirect 等数据库收录! |
|