论文标题
具有界限最大程度的图形独立统治
Independent domination of graphs with bounded maximum degree
论文作者
论文摘要
一个独立的统治图集，也称为最大独立集，是成对的非贴上的顶点的一组$ s $，以至于每个顶点$ s $中的每个顶点都与$ s $中的某个顶点相邻。我们证明，对于$δ= 4 $或$δ\ ge 6 $，每个连接的$ n $ vertex最高学位最多$δ$具有独立的主导尺寸集，最多最多（1- \fracΔ{\lfloorΔ^2/4 \ rfloor+δ}）（n-1）+1 $。另外，我们表征了具有平等性的所有连接图，并表明其他连接的图具有独立的主导尺寸集，最多是$（1- \fracδ{\lfloorΔ^2/4 \ rfloor+δ}）n $。
An independent dominating set of a graph, also known as a maximal independent set, is a set $S$ of pairwise non-adjacent vertices such that every vertex not in $S$ is adjacent to some vertex in $S$. We prove that for $Δ=4$ or $Δ\ge 6$, every connected $n$-vertex graph of maximum degree at most $Δ$ has an independent dominating set of size at most $(1-\fracΔ{\lfloorΔ^2/4\rfloor+Δ})(n-1)+1$. In addition, we characterize all connected graphs having the equality and we show that other connected graphs have an independent dominating set of size at most $(1-\fracΔ{ \lfloorΔ^2/4\rfloor+Δ})n$.
