论文部分内容阅读
对于图G=(V,E)的一个点v，G的平均最小独立数iav(G)被定义为1/|V(G)|∑v∈V(G)iv(G)，其中iv(G)是包含v的极大独立集所含的最少点数.i(G)被定义为G的一个极大独立集所含的最少点数.γ(G)为G的控制集所含的最少点数.对任一个点v∈V(G)，G的匹配数β(G)被定义为G中最大匹配所含的边数，βv(G)为图G-N[v]中最大匹配所含的边数.所以βv(G)=β(G-N[v]).
Henning(Treeswithequalaveragedominationandindependentdominationnumbers，ArsCommbin.71(2004)305-318)证明了对于一个顶点数n≥2的树T，iav(T)≤n-2+2/n.Blidiaetal.(Onaveragelowerindependenceanddominationnumbersingraphs，DiscreteMathematics295(2005)1-11)证明了对于任意n个点m条边的图G，iav(G)≤n-2m/n-1/n∑v∈V(G)βv(G).受到这些结果的启发，我们给出了单圈和双圈图平均最小独立数的上界.我们的主要结论是：(1)设G是一个顶点数n≥5的单圈图，则iav(G)≤n-3+3/n,等号成立当且仅当G是一个通过连接n个顶点星图Sn的两个一度点得到的图.(2)设G是一个顶点数n≥6的双圈图，则2iav(G)＜n-3+2/n.