关于Cockayne E J等人的一个猜想

On a Conjecture of Cockayne E J etc.

Cockayne E J引入了一个图G的k-符号控制数γk-s11(G)的概念,提出了如下猜想:对任意n阶连通图G和正整数k(n2<k≤n),均有γk-s11(G)≤2k-n。我们证明了3方体Q3的5-符号控制数γ-5s11(Q3)=4,从而否定了这个猜想。此外,我们还给出了3-正则二部图k-符号控制数的一个上界,即证明了:对于任意n阶3-正则二部图G和正整数k(n2+1≤k≤n),均有γ-ks11(G)≤2(k+1)-n成立。

Abstract：Cockayne E J introduced the concept of the signed k - subdomination number γks^-11 （G） of a graph G,posed a conjecture as follows：For any connected graph G of order n and integer k（n/2〈k≤n） ,then γks^-11（G）≤2k - n. This paper prove that γSs^-11 （ Q3 ） = 4 for the 3 - Cube Q3, and hence disprove the conjecture. In addition, we - n give an upper bound of the signed k - subdomination numbers for 3 - regular bipartite graphs, that is, k（n/2＋1≤k≤n） holds for all 3 - regular bipartite graphs G and positive integers γks^-11（G）≤2（k ＋ 1） - n.