关于图的弱符号控制数的下界

图G的弱符号控制数γws（G）有着许多重要的应用背景,因而确定其下界有重要意义.在构造适当点集的基础上,给出了图的弱符号控制数的4个独立的下界,并给出了达到这4个下界的图.     

图的连通控制数与无赘数的一个不等式

设G是连通图,γ_C(G)和ir(G)分别表示G的连通控制数和无赘数。孙良于1990年证明了γ_c(G)≤4ir(G)—2,同时提出猜想γ_c(G)≤3ir(G)—2。本文进一步研究γ_c(G)与ir(G)的关系,并证得上述猜想成立。     

无向超环面网C(3,3…,3)的(n,2n)控制数

The(d,k)-dominating number is a new measure to characterize reliability of resourcesharing in fault tolerant networks.This paper obtains that the(n,2n)-dominating number of the n-dimensional undirected toroidal mesh C(3,3,…,3)is equal to 3(n≥3).     

直径为d的超环面网的(d,2n)-控制数

ｎ维超环面网Ｃ（ｄ１ｄｄ２,…,ｄｎ）定义如下：顶点集为｛（ｘ１,…;ｘｎ）｜０≤ｘｉ＜ｄｉ（１≤ｉ≤ｎ）｝;每个顶点（ｘｌ,…,ｘｎ）与（ｘ１±１,ｘ２,…,ｘｎ）,（ｘ１,ｘ２±１,…,ｘｎ）,…;（ｘｌ,ｘ２,…,ｘｎ±１）这２ｎ个顶点相邻．（ｄ,ｍ）－控制数是用来刻画互连网络数据传输某种模式的一个新参数．本文证明了：当 ｄ＝ｄｉａｍ（Ｃ（ｄ１,ｄ２,…,ｄｎ））时,ｎ维超环面网Ｃ（ｄ１,ｄ２,…,ｄｎ）≠Ｃ（３,３,…,３）的（ｄ,２ｎ）－控制数为２（ｎ≥３,ｄｉ≥３,ｉ∈｛１,２,…,ｎ｝）．     

关于图的连通DOMINATION的若干结果

设G是n阶连通图.γ_c(G),d_c(G),i(G)和ir(G)分别表示G图的连通Domination数,连通Domatic数,独立Domination数和Irredundance数,k(G)表示G的连通度.本文证明了下列结论. (1) 如n≥3,则i(G) γ_c(G)≤n [n/3]-2; (2) γ_c(G)≤4ir(G)-2; (3) γ_c(G)≤k(G) 1; (4) 如G≠K_n,则d_c(G)≤k(G). 此外,本文给出了满足等式γ_c(G) γ_c(G)=n和γ_c(G) γ_c(G)=n 1的图G的一个特征.     

图的好符号星控制数

引入了图的好符号星控制的概念,求出了欧拉图、完全二部图、完全图和轮图的好符号星控制数,并改进了图的符号星控制数的两个上界.     

图的符号团边控制数

本文研究了图的符号团边控制数的问题.利用鸽巢原理,获得了图K_n∨P_m和K_n∨C_m的符号团边控制数,推广了已有的结果.     

几类图的Fractional星控制数

设G=(V,E)是一个无孤立点的图,一个实值函数f:E(G)→[0,1]若对所有的点u∈V(G),均有∑uv∈Ef(uv)≥1成立,则称f为图G的一个Fractional星控制函数.图G的Fractional星控制数定义为γ_(fs)(G)=min{∑uv∈Ef(uv)|f为图G的一个Fractional星控制函数}.研究了几类乘积图的Fractional星控制问题,给出了一些常见特殊图的Fractional星控制数,主要确定了积图P_m×P_n和C_m×P_n的Fractional星控制数.     

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

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）成立。     

图的2-控制数的上界和一个Graffiti.pc猜想（英文）

设G=(V(G),E(G))是一个图,k是一个正整数.称一个顶点子集S为G的kk-控制集,若V(G)\S中的每个顶点在S中至少有k个邻点,我们用r_k (G)表示kk-控制集的最小阶数.令d₁≤d₂≤…≤d_n为图G的度序列.当n为偶数时,度序列中位数m(G)=d_n/2+1,当n为奇数时,度序列中位数m(G)=d_n+1/2.一个仍未解决的Graffiti.pc猜想说:对任一n个顶点的连通图G,r₂(G)≤n-m(G)+1.首先我们证明了此猜想的一个弱形式:r2(G) ≤n-d₁+1.此外,通过拓展此猜想在二部图上的结果,我们证明了对最小度不小于2的无三角形图G,r2(G)≤n-Δ(G),其中Δ(G)为图G的最大度.众所周知,每一个其边数不少于顶点数的图都包含一个圈.我们将此结论推广到超图上.进而得到上述猜想对所有分裂图都成立.