Irregular Subgraphs

DOI10.1017/S0963548322000220MaRDI QIDQ6374596arXivFDO

Authors Noga Alon, Fan Wei

Publication date 5 August 2021

Published in arXiv

Full work available at URL https://doi.org/10.1017/S0963548322000220

Mathematics Subject Classification ID

Vertex degrees (05C07) Extremal problems in graph theory (05C35)

arXiv classification

math.CO

Abstract: 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 $fracnd+1$ by at most $2$. The second is that every graph on $n$ vertices with minimum degree $delta$ contains a spanning subgraph in which the number of vertices of each degree does not exceed $fracndelta+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 $d^{3}lognleqo(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))fracnd+1$. We also prove that any graph with $n$ vertices and minimum degree $delta$ contains a spanning subgraph in which no degree is repeated more than $(1+o(1))fracndelta+1+2$ times.

This page was built for publication: Irregular Subgraphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6374596)