论文标题
关联独立数量和解离号
Relating the independence number and the dissociation number
论文作者
论文摘要
图$ g $的独立数$α（g）$和分离号$ {\ rm diss}（g）$是最大的最大$ g $最高$ g $ $ g $的订单，最多$ 0 $，最多最多$ 1 $。我们考虑可能改善明显不平等的$2α（g）\ geq {\ rm diss}（g）$。对于连接的立方图$ g $不同于$ k_4 $，我们显示$5α（g）\ geq 3 {\ rm diss}（g）$，并详细描述了极端图的丰富且有趣的结构。对于两部分图，更一般而言是无三角形的图，我们还获得了改进。但是，对于亚地带图，通常无法改善不平等，我们表征了所有极端的亚基图。
The independence number $α(G)$ and the dissociation number ${\rm diss}(G)$ of a graph $G$ are the largest orders of induced subgraphs of $G$ of maximum degree at most $0$ and at most $1$, respectively. We consider possible improvements of the obvious inequality $2α(G)\geq {\rm diss}(G)$. For connected cubic graphs $G$ distinct from $K_4$, we show $5α(G)\geq 3{\rm diss}(G)$, and describe the rich and interesting structure of the extremal graphs in detail. For bipartite graphs, and, more generally, triangle-free graphs, we also obtain improvements. For subcubic graphs though, the inequality cannot be improved in general, and we characterize all extremal subcubic graphs.
