2021/08/05 by Alon, Noga, Wei, Fan · 1 citation
#05C07 #05C35 #Combinatorics (math.CO) #FOS: Mathematics
paper · doi:10.48550/arxiv.2108.02685
We suggest two related conjectures dealing with the existence of spanning irregular subgraphs of graphs. The first asserts that any d-regular graph on n vertices contains a spanning subgraph in which the number of vertices of each degree between 0 and d deviates from (n)/(d+1) by at most 2. The second is that every graph on n vertices with minimum degree δ contains a spanning subgraph in which the number of vertices of each degree does not exceed (n)/(δ+1)+2. Both conjectures remain open, but we prove several asymptotic relaxations for graphs with a large number of vertices n. In particular we show that if d3 log n ≤ o(n) then every d-regular graph with n vertices contains a spanning subgraph in which the number of vertices of each degree between 0 and d is (1+o(1))(n)/(d+1). We also prove that any graph with n vertices and minimum degree δ contains a spanning subgraph in which no degree is repeated more than (1+o(1))(n)/(δ+1)+2 times.