solidot新版网站常见问题,请点击这里查看。
消息
本文已被查看241次
Equating two maximum degrees. (arXiv:1704.08472v1 [math.CO])
来源于:arXiv
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 \geq 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 \geq 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 $\Delt 查看全文>>