论文标题
解离数
A bound on the dissociation number
论文作者
论文摘要
图$ g $的分离数字$ {\ rm diss}（g）$是一组$ g $的顶点的最大顺序，该$ g $诱导了最大程度最高$ 1 $的子图。即使仅限于亚地带两部分图，计算给定图的分离数也很难。对于图形$ g $，带有$ n $顶点，$ m $边缘，$ k $组件和$ c_1 $诱导的长度$ 1 $ 1 $ modulo $ 3 $，我们显示$ {\ rm diss}（g）\ geq n- \ geq n- \ frac {1} {1}} {3} {3} \ big big big big big big+k+c_1 \ big）此外，我们表征了极端图，其中每两个循环是顶点 - 偶会。
The dissociation number ${\rm diss}(G)$ of a graph $G$ is the maximum order of a set of vertices of $G$ inducing a subgraph that is of maximum degree at most $1$. Computing the dissociation number of a given graph is algorithmically hard even when restricted to subcubic bipartite graphs. For a graph $G$ with $n$ vertices, $m$ edges, $k$ components, and $c_1$ induced cycles of length $1$ modulo $3$, we show ${\rm diss}(G)\geq n-\frac{1}{3}\Big(m+k+c_1\Big)$. Furthermore, we characterize the extremal graphs in which every two cycles are vertex-disjoint.
