z-logo
open-access-imgOpen Access
A note on forcing 3-repetitions in degree sequences
Author(s) -
Shimon Kogan
Publication year - 2020
Publication title -
discussiones mathematicae graph theory
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.476
H-Index - 19
eISSN - 2083-5892
pISSN - 1234-3099
DOI - 10.7151/dmgt.2376
Subject(s) - mathematics , degree (music) , forcing (mathematics) , combinatorics , mathematical analysis , acoustics , physics
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.

The content you want is available to Zendy users.

Already have an account? Click here to sign in.
Having issues? You can contact us here
Accelerating Research

Address

John Eccles House
Robert Robinson Avenue,
Oxford Science Park, Oxford
OX4 4GP, United Kingdom