Article in volume
Authors:
Title:
A note on forcing 3-repetitions in degree sequences
PDFSource:
Discussiones Mathematicae Graph Theory 43(2) (2023) 457-462
Received: 2020-06-25 , Revised: 2020-11-02 , Accepted: 2020-11-02 , Available online: 2020-11-21 , https://doi.org/10.7151/dmgt.2376
Abstract:
In Caro, Shapira and Yuster [Forcing k-repetitions in degree sequences, Electron. J. Combin.
21 (2014) #P1.24] 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:
repeated degrees
References:
- Y. Caro, A. Shapira and R. Yuster, Forcing k-repetitions in degree sequences, Electron. J. Combin. 21 (2014) #P1.24.
https://doi.org/10.37236/3503 - 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 subgraphs, European J. Combin. 14 (1993) 183–189.
https://doi.org/10.1006/eujc.1993.1023 - P. Erdős, S. Fajtlowicz and W. Staton, Degree sequences in triangle-free graphs, Discrete Math. 92 (1991) 85–88.
https://doi.org/10.1016/0012-365X(91)90269-8
Close