Forcing k-repetitions in degree sequences

zbMATH Open1300.05064arXiv1312.1213MaRDI QIDQ405103FDOQ405103

Authors: Yair Caro, Asaf Shapira, Raphael Yuster 

Publication date: 4 September 2014

Published in: The Electronic Journal of Combinatorics (Search for Journal in Brave)

Abstract: One of the most basic results in graph theory states that every graph with at least two vertices has two vertices with the same degree. Since there are graphs without $3$ vertices of the same degree, it is natural to ask if for any fixed $k$, every graph $G$ is ``close to a graph $G^{\prime }$ with $k$ vertices of the same degree. Our main result in this paper is that this is indeed the case. Specifically, we show that for any positive integer $k$, there is a constant $C=C(k)$, so that given any graph $G$, one can remove from $G$ at most $C$ vertices and thus obtain a new graph $G^{\prime }$ that contains at least $mink,|G|-C$ vertices of the same degree. Our main tool is a multidimensional zero-sum theorem for integer sequences, which we prove using an old geometric approach of Alon and Berman.

Full work available at URL: https://arxiv.org/abs/1312.1213

File on IPFS (Hint: this is only the Hash - if you get a timeout, this file is not available on our server.)

Recommendations

• Repetition number of graphs
• scientific article; zbMATH DE number 810044
• Turán theorems with repeated degrees
• Large induced subgraphs with three repeated degrees
• scientific article

zbMATH Keywords

degree sequencesubgraphrepetition

Mathematics Subject Classification ID

Vertex degrees (05C07)

Cites Work

• Repetition number of graphs
• Title not available (Why is that?)
• Title not available (Why is that?)
• Bounding the monomial index and \((1,l)\)-weight choosability of a graph
• A new upper bound for the irregularity strength of graphs
• Small Ramsey numbers
• Regular hypergraphs, Gordon's lemma, Steinitz' lemma and invariant theory
• Ramsey problems involving degrees in edge-colored complete graphs of vertices belonging to monochromatic subgraphs
• Independent sets and repeated degrees
• Degree multiplicities and independent sets in \(K_ 4\)-free graphs
• Ramsey Problems with Bounded Degree Spread
• Repeated Degrees in Random Uniform Hypergraphs
• Title not available (Why is that?)
• Large induced subgraphs with equated maximum degree

Cited In (8)

• A note on repeated degrees of line graphs
• Equating \(\kappa\) maximum degrees in graphs without short cycles
• Equating two maximum degrees
• Repetition number of graphs
• Induced subgraphs with many repeated degrees
• Title not available (Why is that?)
• Large Induced Subgraphs with $k$ Vertices of Almost Maximum Degree
• Large induced subgraphs with three repeated degrees

This page was built for publication: Forcing \(k\)-repetitions in degree sequences

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