DMGT

ISSN 1234-3099 (print version)

ISSN 2083-5892 (electronic version)

https://doi.org/10.7151/dmgt

Discussiones Mathematicae Graph Theory

Journal Impact Factor (JIF 2022): 0.7

5-year Journal Impact Factor (2022): 0.7

CiteScore (2022): 1.9

SNIP (2022): 0.902

Discussiones Mathematicae Graph Theory

Article in volume


Authors:

S. Kogan

Shimon Kogan

Weizmann Institute

email: shimon.kogan@weizmann.ac.il

Title:

A note on forcing 3-repetitions in degree sequences

PDF

Source:

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:

  1. 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
  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 subgraphs, European J. Combin. 14 (1993) 183–189.
    https://doi.org/10.1006/eujc.1993.1023
  3. 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