Irregular subgraphs

Noga Alon; Fan Wei

doi:10.1017/S0963548322000220

Irregular subgraphs

Noga Alon, Fan Wei

Mathematics

Research output: Contribution to journal › Article › peer-review

4 Scopus citations

Abstract

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.

Original language	English (US)
Pages (from-to)	269-283
Number of pages	15
Journal	Combinatorics Probability and Computing
Volume	32
Issue number	2
DOIs	https://doi.org/10.1017/S0963548322000220
State	Published - Mar 1 2023

All Science Journal Classification (ASJC) codes

Theoretical Computer Science
Statistics and Probability
Computational Theory and Mathematics
Applied Mathematics

Keywords

irregular subgraph
repeated degrees

Access to Document

10.1017/S0963548322000220

Cite this

@article{78bb80a7384d48ae94bcdc8fc3fb08c1,

title = "Irregular subgraphs",

abstract = "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.",

keywords = "irregular subgraph, repeated degrees",

author = "Noga Alon and Fan Wei",

note = "Publisher Copyright: {\textcopyright} The Author(s), 2022. Published by Cambridge University Press.",

year = "2023",

month = mar,

day = "1",

doi = "10.1017/S0963548322000220",

language = "English (US)",

volume = "32",

pages = "269--283",

journal = "Combinatorics Probability and Computing",

issn = "0963-5483",

publisher = "Cambridge University Press",

number = "2",

}

TY - JOUR

T1 - Irregular subgraphs

AU - Alon, Noga

AU - Wei, Fan

N1 - Publisher Copyright: © The Author(s), 2022. Published by Cambridge University Press.

PY - 2023/3/1

Y1 - 2023/3/1

N2 - 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.

AB - 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.

KW - irregular subgraph

KW - repeated degrees

UR - http://www.scopus.com/inward/record.url?scp=85206492079&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85206492079&partnerID=8YFLogxK

U2 - 10.1017/S0963548322000220

DO - 10.1017/S0963548322000220

M3 - Article

AN - SCOPUS:85206492079

SN - 0963-5483

VL - 32

SP - 269

EP - 283

JO - Combinatorics Probability and Computing

JF - Combinatorics Probability and Computing

IS - 2

ER -

Irregular subgraphs

Abstract

All Science Journal Classification (ASJC) codes

Keywords

Access to Document

Other files and links

Fingerprint

Cite this