论文部分内容阅读
Cockayne E J 引入了一个图G的k-符号控制数γks^-11（G）的概念，提出了如下猜想：对任意n阶连通图G和正整数k（n/2-＜k≤n），均有γks^-11（G）≤2k-n.我们证明了3方体Q3的5-符号控制数γSs^-11（Q3）=4，从而否定了这个猜想。此外，我们还给出了3-正则二部图k-符号控制数的一个上界，即证明了：对于任意n阶3-正则二部图G和正整数k（n/2＋1≤k≤n），均有γks^-11（G）≤2（k＋1-n）成立。