Equating two maximum degrees

Abstract

Given a graph $G$, we would like to find (if it exists) the largest induced subgraph $H$ in which there are at least $k$ vertices realizing the maximum degree of $H$. This problem was first posed by Caro and Yuster. They proved, for example, that for every graph $G$ on $n$ vertices we can guarantee, for $k=2$, such an induced subgraph $H$ by deleting at most $2\sqrt{n}$ vertices, but the question if $2\sqrt{n}$ is best possible remains open. Among the results obtained in this paper we prove that: 1. For every graph $G$ on $n\ge 4$ vertices we can delete at most $\lceil \frac{-3+\sqrt{8n-15}}{2}\rceil$ vertices to get an induced subgraph $H$ with at least two vertices realizing $\Delta (H)$, and this bound is sharp, solving the problems left open by Caro and Yuster. 2.For every graph $G$ with maximum degree $\Delta \ge 1$ we can delete at most $\lceil \frac{-3+\sqrt{8\Delta +1}}{2}\rceil$ vertices to get an induced subgraph $H$ with at least two vertices realizing $\Delta (H)$, and this bound is sharp. 3. Every graph $G$ with $\Delta (G)\le 2$ and least $2k-1$ vertices (respectively $2k-2$ vertices if k is even) contains an induced subgraph $H$ in which at least $k$ vertices realise $\Delta (H)$, and these bound are sharp.

Cited by in corpus (1)

• Equating $k$ Maximum Degrees in Graphs without Short Cycles