论文标题
图表的最高程度和欧拉的特征的新上限
New upper bounds for the bondage number of a graph in terms of its maximum degree and Euler characteristic
论文作者
论文摘要
图$ g $的束缚数字$ b（g）$是最小的边缘数量，其从$ g $中删除的图形中的图形具有较大的统治数。让$ g $可以嵌入在其euler特性$χ$尽可能大的表面上，并假设$χ\ \ leq0 $。 Gagarin-Zverovich和Huang最近在最高度$δ（g）$和Euler特性$χ（g）=χ$方面发现了$ b（g）$的上限。在本文中，我们证明了更好的上限$ b（g）\leqΔ（g） + \ lfloor t \ rfloor $其中$ t $是立方方程的最大真实根$ z^3 + z^2 +（3χ-8）z +9χ-12 = 0 $;该上限在渐近上等同于$ b（g）\leqδ（g）+1+ \ lfloor \ sqrt {4-3χ} \ rfloor $。当图$ g $的周长，订单或大小与其Euler特性$χ$相比，我们还为$ b（g）$建立了进一步改进的上限。
The bondage number $b(G)$ of a graph $G$ is the smallest number of edges whose removal from $G$ results in a graph with larger domination number. Let $G$ be embeddable on a surface whose Euler characteristic $χ$ is as large as possible, and assume $χ\leq0$. Gagarin-Zverovich and Huang have recently found upper bounds of $b(G)$ in terms of the maximum degree $Δ(G)$ and the Euler characteristic $χ(G)=χ$. In this paper we prove a better upper bound $b(G)\leqΔ(G)+\lfloor t\rfloor$ where $t$ is the largest real root of the cubic equation $z^3 + z^2 + (3χ- 8)z + 9χ- 12=0$; this upper bound is asymptotically equivalent to $b(G)\leqΔ(G)+1+\lfloor \sqrt{4-3χ} \rfloor$. We also establish further improved upper bounds for $b(G)$ when the girth, order, or size of the graph $G$ is large compared with its Euler characteristic $χ$.
