论文标题
亚采比图中的独立统治
Independent Domination in Subcubic Graphs
论文作者
论文摘要
如果每个顶点在$ s $相邻的$ s $中，则图表$ g $中的$ s $顶点是一个主体集。如果此外，$ s $是独立的集合，则$ s $是独立的主导套装。 $ g $的独立支配数字$ i（g）$是$ g $中独立支配的最低基数。 In 2013 Goddard and Henning [Discrete Math 313 (2013), 839--854] conjectured that if $G$ is a connected cubic graph of order $n$, then $i(G) \le \frac{3}{8}n$, except if $G$ is the complete bipartite graph $K_{3,3}$ or the $5$-prism $C_5 \, \Box \，K_2 $。此外，他们构建了两个无限的连接的立方图家族，独立统治了八分之三。他们指出，也许对于$ n> 10美元来说，这两个家庭只是平等所拥有的家庭。在本文中，我们提供了一个新的连接立方图的系列$ g $ $ n $的$ g $，以便$ i（g）= \ frac {3} {8} n $。我们还表明，如果$ g $是一个没有孤立顶点的订单$ n $的亚立方图，则$ i（g）\ le \ frac {1} {2} {2} n $，我们表征了在此界限中实现平等的图。
A set $S$ of vertices in a graph $G$ is a dominating set if every vertex not in $S$ is adjacent to a vertex in $S$. If, in addition, $S$ is an independent set, then $S$ is an independent dominating set. The independent domination number $i(G)$ of $G$ is the minimum cardinality of an independent dominating set in $G$. In 2013 Goddard and Henning [Discrete Math 313 (2013), 839--854] conjectured that if $G$ is a connected cubic graph of order $n$, then $i(G) \le \frac{3}{8}n$, except if $G$ is the complete bipartite graph $K_{3,3}$ or the $5$-prism $C_5 \, \Box \, K_2$. Further they construct two infinite families of connected cubic graphs with independent domination three-eighths their order. They remark that perhaps it is even true that for $n > 10$ these two families are only families for which equality holds. In this paper, we provide a new family of connected cubic graphs $G$ of order $n$ such that $i(G) = \frac{3}{8}n$. We also show that if $G$ is a subcubic graph of order $n$ with no isolated vertex, then $i(G) \le \frac{1}{2}n$, and we characterize the graphs achieving equality in this bound.
