Irregular subgraphs

We suggest two related conjectures dealing with the existence of spanning irregular subgraphs of graphs. The first asserts that any -regular graph on vertices contains a spanning subgraph in which the number of vertices of each degree between and deviates from by at most. The second is that every graph on vertices with minimum degree contains a spanning subgraph in which the number of vertices of each degree does not exceed. Both conjectures remain open, but we prove several asymptotic relaxations for graphs with a large number of vertices. In particular we show that if then every -regular graph with vertices contains a spanning subgraph in which the number of vertices of each degree between and is. We also prove that any graph with vertices and minimum degree contains a spanning subgraph in which no degree is repeated more than times.

Duke Scholars

Author Fan Wei Mathematics