Forcing k-repetitions in degree sequences

MaRDI QIDQ405103zbMATHFDO

Authors Yair Caro, Asaf Shapira, Raphael Yuster

Publication date 4 September 2014

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

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

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

zbMATH Keywords

degree sequencesubgraphrepetition

Mathematics Subject Classification ID

Vertex degrees (05C07)

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.

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 DE number 140115

Cites work

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

Cited in

(8)

• Induced subgraphs with many repeated degrees
• Large induced subgraphs with three repeated degrees
• scientific article; zbMATH DE number 810044 (Why is no real title available?)
• Equating \(\kappa\) maximum degrees in graphs without short cycles
• A note on repeated degrees of line graphs
• Equating two maximum degrees
• Large induced subgraphs with \(k\) vertices of almost maximum degree
• Repetition number of graphs

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)