论文标题
降低图的最大程度：边界的比较
Reducing the maximum degree of a graph: comparisons of bounds
论文作者
论文摘要
令$λ（g）$为最少的顶点，可以从非空图$ g $中删除，以使所得图具有较小的最高度。令$λ_ {\ rm e}（g）$是可以从$ g $中删除的最小边缘，出于相同的目的。让$ k $为$ g $的最高度，让$ t $是度量$ k $的顶点的数量，让$ m（g）$是度量$ k $的顶点，让$ n $是$ m（g）$的封闭社区中的顶点数量，让$ m $ m $是$ m $的数量，即$ m $ in $ m（g）$。 Fenech和作者表明$λ（g）\ leq \ frac {n+（k-1）t} {2k} $，它们基本上表明$λ（g）\ leq n \ left（1- \ frac {k} }^{1/k} \ right）$。他们还表明，$λ_ {\ rm e}（g）\ leq \ frac {m +（k-1）t} {2k-1} $和$λ_ {\ rm e}（g）\ leq m \ left（1- \ frac {k-1} }^{1/（k-1）} \ right）$。如果$ k \ geq 2 $和$ g $是$ t $ t $ pairwise vertex-dischoint $（k+1）$ - 顶点恒星的结合，则将达到这些界限。对于$λ（g）$和$λ_{\ rm e}（g）$中的每一个，比较参数上的两个界限，以确定每个界限的目的，即界限比另一个界限更好。这项工作还引起了针对其他图参数的类似界限的可能性，并且可以应用相同的分析。
Let $λ(G)$ be the smallest number of vertices that can be removed from a non-empty graph $G$ so that the resulting graph has a smaller maximum degree. Let $λ_{\rm e}(G)$ be the smallest number of edges that can be removed from $G$ for the same purpose. Let $k$ be the maximum degree of $G$, let $t$ be the number of vertices of degree $k$, let $M(G)$ be the set of vertices of degree $k$, let $n$ be the number of vertices in the closed neighbourhood of $M(G)$, and let $m$ be the number of edges incident to vertices in $M(G)$. Fenech and the author showed that $λ(G) \leq \frac{n+(k-1)t}{2k}$, and they essentially showed that $λ(G) \leq n \left ( 1- \frac{k}{k+1} { \Big( \frac{n}{(k+1)t} \Big) }^{1/k} \right )$. They also showed that $λ_{\rm e}(G) \leq \frac{m + (k-1)t}{2k-1}$ and $λ_{\rm e} (G) \leq m \left ( 1- \frac{k-1}{k} { \Big( \frac{m}{kt} \Big) }^{1/(k-1)} \right )$. These bounds are attained if $k \geq 2$ and $G$ is the union of $t$ pairwise vertex-disjoint $(k+1)$-vertex stars. For each of $λ(G)$ and $λ_{\rm e}(G)$, the two bounds on the parameter are compared for the purpose of determining, for each bound, the cases in which the bound is better than the other. This work is also motivated by the likelihood that similar pairs of bounds will be discovered for other graph parameters and the same analysis can be applied.
