1. bookAHEAD OF PRINT
Journal Details
License
Format
Journal
eISSN
2083-5892
First Published
13 Apr 2013
Publication timeframe
4 times per year
Languages
English
access type Open Access

A Note on Forcing 3-Repetitions in Degree Sequences

Published Online: 16 Dec 2020
Volume & Issue: AHEAD OF PRINT
Page range: -
Received: 25 Jun 2020
Accepted: 02 Nov 2020
Journal Details
License
Format
Journal
eISSN
2083-5892
First Published
13 Apr 2013
Publication timeframe
4 times per year
Languages
English
Abstract

In Caro, Shapira and Yuster [1] it is proven that for any graph G with at least 5 vertices, one can delete at most 6 vertices such that the subgraph obtained has at least three vertices with the same degree. Furthermore they show that for certain graphs one needs to remove at least 3 vertices in order that the resulting graph has at least 3 vertices of the same degree.

In this note we prove that for any graph G with at least 5 vertices, one can delete at most 5 vertices such that the subgraph obtained has at least three vertices with the same degree. We also show that for any triangle-free graph G with at least 6 vertices, one can delete at most one vertex such that the subgraph obtained has at least three vertices with the same degree and this result is tight for triangle-free graphs.

Keywords

MSC 2010

[1] Y. Caro, A. Shapira and R. Yuster, Forcing k-repetitions in degree sequences, Electron. J. Combin. 21 (2014) #P1.24. doi: 10.37236/3503Open DOISearch in Google Scholar

[2] P. Erdős, G. Chen, C.C. Rousseau and R.H. Schelp, Ramsey problems involving degrees in edge-colored complete graphs of vertices belonging to monochromatic sub-graphs, European J. Combin. 14 (1993) 183–189. doi: 10.1006/eujc.1993.1023Open DOISearch in Google Scholar

[3] P. Erdős, S. Fajtlowicz and W. Staton, Degree sequences in triangle-free graphs, Discrete Math. 92 (1991) 85–88. doi: 10.1016/0012-365X(91)90269-8Open DOISearch in Google Scholar

Recommended articles from Trend MD

Plan your remote conference with Sciendo