论文标题
和弦图的束缚数量
The bondage number of chordal graphs
论文作者
论文摘要
如果每个顶点在$ s $中具有邻居或属于$ s $，则图$ G $的集合$ s \ subseteq v（g）$是一个主体集。令$γ（g）$为$ g $中的最低主导地位的基数。图$ g $的债券数字$ b（g）$是设置边缘$ a \ subseteq e（g）$的最小基数，因此$γ（g-a）=γ（g）+1 $。和弦图是无诱导循环长度四个或更多的图形。在本文中，我们证明了和弦图$ g $的束缚数量最多是其最大集团的顺序，即$ b（g）\leqΩ（g）$。我们表明，这是最好的。
A set $S\subseteq V(G)$ of a graph $G$ is a dominating set if each vertex has a neighbor in $S$ or belongs to $S$. Let $γ(G)$ be the cardinality of a minimum dominating set in $G$. The bondage number $b(G)$ of a graph $G$ is the smallest cardinality of a set edges $A\subseteq E(G)$ such that $γ(G-A)=γ(G)+1$. A chordal graph is a graph with no induced cycle of length four or more. In this paper, we prove that the bondage number of a chordal graph $G$ is at most the order of its maximum clique, that is, $b(G)\leq ω(G)$. We show that this bound is best possible.
