Signed Domination in Regular Graphs and Set-Systems
Signed Domination in Regular Graphs and Set-Systems
复制标题
DOI：
10.1006/jctb.1999.1905
复制
发表时间：
1999-07
期刊：
影响因子：
--
通讯作者：
Z. Füredi;D. Mubayi
中科院分区：
文献类型：
--
作者：
Z. Füredi;D. Mubayi
设G是一个最小度为r的n阶图。使用标准的随机方法，它表明，存在一个两个着色的顶点G的颜色，+1和？1，使得所有闭邻域包含的1比？1的个数，而1的个数加在一起不超过？大于（4logr/r+1/r）n.对于大的r，这大大改善了以前的结果，几乎是最优的，因为从一个Hadamard矩阵的顺序r，一个二部r-正则图是建立在4 r个顶点的符号控制数至少（1/2）r？O（1）。limn的确定？∞？s（G）/n保持开放，并被证明是？（1/r）。
Suppose G is a graph on n vertices with minimum degree r. Using standard random methods it is shown that there exists a two-coloring of the vertices of G with colors, +1 and ?1, such that all closed neighborhoods contain more 1's than ?1's, and all together the number of 1's does not exceed the number of ?1's by more than (4logr/r+1/r)n. For large r this greatly improves earlier results and is almost optimal, since starting with an Hadamard matrix of order r, a bipartite r-regular graph is constructed on 4r vertices with signed domination number at least (1/2) r?O(1). The determination of limn?∞?s(G)/n remains open and is conjectured to be ?(1/r).