令G是一个图,v是图G的任意一个顶点.用NG(v)表示图G中和点v相邻的点的集合,也称为图G中v的开邻集.图G中v的闭邻集定义为NG(v)∪{v}.一个点子集称为图G的一个控制集,如果这个点子集的闭邻集控制图G的所有点.图G中最小控制集所包含的点的个数,称为图G的控制数,记为γ(G).全控制集是指开邻集可以控制图G的所有点的一个点子集.图G中最小全控制集所包含的点的个数,称为图G的全控制数,记为γt(G).
在随后的讨论中,如不加特殊说明,只考虑广义Mycielskian图的补图.令图G=(V0,E0),V0={v01,v02,…,v0n}.广义Mycielskian图μm(G)的顶点集为:{V0,V1,V2,…,Vm},Vi也可看作是图G的顶点集V0的拷贝点集,u为μm(G)的根点,m是图μm(G)的拷贝层数.广义Mycielskian图的补图记为μ^-m(G).
在这一节中,首先给出μ^-m(G)的控制数和全控制数的结果.由控制数和全控制数的定义.对任意的至少有两个顶点的简单图G.有如下事实:
事实(i):γ(G)≥1,并且γ(G)=1,当且仅当G有一个全局点;
事实(ii):γt(G)≥2,并且γt(G)=2,当且仅当u,v∈V(G),s.t.,NG(u)∪NG(v)=V(G).
显然,当m=0时,γ((-overμ)0(G))=γ((-overG))+1.对于m≥1时,有如下结果:
定理1 令G是一个图,(-overμ)m(G)是图G的广义Mycielskian图的补图.则
γ((-overμ)m(G))={1,图G有孤立点时,
2,其他.
证明 由μm(G)的定义,(-overμ)m(G)有全局点,当且仅当G有孤立点.所以当G有孤立点时,γ((-overμ)m(G))=1.
下面假设G没有孤立点,即(-overμ)m(G)没有全局点,则γ((-overμ)m(G))≥2.分两种情形证明:γ((-overμ)m(G))≤2.
情形1)若图G连通且至少有两个顶点时,在(-overμ)m(G)中,令S={vmi,u}.S中vmi可以控制Vm中的所有点; 而u可以控制除Vm以外(-overμ)m(G)中的所有点.根据控制集的定义可知,S是(-overμ)m(G)的一个控制集,再由最小控制集的定义,γ((-overμ)m(G))≤2.
情形2)若图G不连通,在(-overμ)m(G)中,令S={v0i,v0j},i,j=1,2,…,n且i≠j,其中v0i,v0j分别代表G中任意两个不同连通分支中的任意一点.S中v0i可以控制除自身所在连通分支及相应拷贝点集外的所有其他点; 同理v0j可以控制除自身所在连通分支及相应拷贝点集外的所有其他点; 而v0i,v0j取自不同的连通分支,则根据控制集的定义可知,S是(-overμ)m(G)的一个控制集,所以γ((-overμ)m(G))≤2.综上可得,γ((-overμ)m(G))=2.
在这一节中,考虑(-overμ)m(G)的全控制数.首先,当m=0时,显然γt((-overμ)m(G))不存在.下面只需考虑m≥1的情形.
定理2 令G是一个图,diam(G)是图G的直径.则
γt((-overμ)m(G))={3,m=1且{diam(G)=1或2},
2,其他.
证明 分以下3种情形证明.
情形1)当m>1时,在(-overμ)m(G)中,令S={v0i,u}.由(-overμ)m(G)的构造可以看出,S的点v0i可以控制点u和Vm中的所有点,而u可以控制V0,V1,…,Vm-1中的所有点,根据全控制数的定义可知,S是(-overμ)m(G)的一个全控制集,故γt((-overμ)m(G))≤2.
情形2)当m=1且diam(G)>2时,取S={v0i,v0j},其中dG(v0i,v0j)=3.由(-overμ)m(G)的定义可知,在(-overμ)m(G)中,S中的v0i可以控制除NG(v0i)和NG(v0i)在V1中的拷贝点集以外的(-overμ)m(G)中的所有点; 而v0j可以控制除NG(v0j)和NG(v0j)在V1中的拷贝点集以外的(-overμ)m(G)中的所有点; 同时NG(v0i)(或NG(v0j))和NG(v0i)(或NG(v0j))在V1中的拷贝点集可被v0j(或v0i)控制.由全控制数的定义,S是(-overμ)m(G)的一个全控制集,故γt((-overμ)m(G))≤2.
由事实(ii)可知,γt((-overμ)m(G))≥2.综上所述,在情形1)和2)下,γt((-overμ)m(G))=2.
情形3)当m=1且diam(G)=1或2时.令S={v0i,v1i,u},在(-overμ)m(G)中,S中的点v0i可以控制u和v1i; 而v1i可以控制除自身以外的V1中的所有点和点v0i; u可以控制V0中的所有点,即N(-overμ)m(G)(v0i)∪N(-overμ)m(G)(v1i)∪u=V((-overμ)m(G)).所以γt((-overμ)m(G))≤3.反之,证明γt((-overμ)m(G))≥3,则下面只需证明(-overμ)m(G)中任意两个点的集合都不是(-overμ)m(G)的全控集即可.根据任意两个点在(-overμ)m(G)中的位置不同,分以下5种情形:
子情形i 若两个点都位于V0.不妨设为{v0i,v0j},i,j=1,2,…,n,i≠j.若diam(G)=1,则v0i,v0j在(-overμ)m(G)中无法被自身所控制; 若diam(G)=2且v0iv0jE(G),则在G中至少存在一个点v0k,使得v0k=NG(v0i)∩NG(v0j),而v0i,v0j在(-overμ)m(G)中无法控制v0k.
子情形ii 若两个点分别位于V0和V1.不妨设为{v0i,v1j},i,j=1,2,…,n.当i=j时,则在(-overμ)m(G)中,v0i和v1j都无法控制NG(v0i); 当i≠j时,如果v0iv1j∈E(G).则v0i,v1j在(-overμ)m(G)中无法控制自身.若v0iv1jE(G).则G中至少存在一个点v0k,使得v0k=NG(v0i)∩NG(v0j),而v0i,v0j无法控制v0k.
子情形iii 若两个点均位于V1中.不妨设为{v1i,v1j},i,j=1,2,…,n,i≠j.则v1i,v1j无法控制点u.
子情形iv 若两个点分别位于V0和u点.不妨设为{v0i,u},i=1,2,…,n,则v0i,和u无法控制NG(v0i)在V1中的拷贝点集.
子情形v 若两个点分别位于V1和u点.不妨设为{v1i,u},i=1,2,…,n,则v1i,和u无法控制自身的两个点.
综上可知,γt((-overμ)m(G))≥3.故在情形3)下,γt((-overμ)m(G))=3.
如果一个点子集中的每个点的闭邻集和这个点子集中的其他点的闭邻集都没有交点,本文中称这个点子集为图G的一个packing集.图G中最大packing集的点的个数,称为图G的packing数,记为η(G).open packing集是指每个点的开邻集和这个集合中的其它点的开邻集都没有交点的一个点子集,open packing数指的是图G中最大的open packing集所包含的点的个数,记为η0(G).
由open packing集的定义,有如下事实(m):对于任意简单图G,有η(G)≥1(或η0(G)≥1),其中η(G)=1(或η0(G)=1)当且仅当diam(G)≤2.
当m=0时,显然有η((-overμ)m(G))=η((-overG))+1,η0((-overμ)m(G))=η0((-overG))+1.下面只需证明m≥1的情形.
定理3 令G是一个连通图.则η((-overμ)m(G))=1.
证明 由μm(G)和(-overμ)m(G)的定义,显然有diam((-overμ)m(G))≤2,根据事实(m)可知,η((-overμ)m(G))=1.
定理4 令G是一个连通图,则
η0((-overμ)m(G))=
{2,m=1且图G至少存在一个点的度为n-1,
1,其他.
证明 分下面两种情形证明:
情形1)当m=1且G中至少存在一个度为n-1(n≥2)的点.不妨设v0k是图G中任意一个度为n-1的点.令S={v0k,u},由(-overμ)1(G)和open packing集的定义可知,N(-overμ)1(G)(v0k)={v1k,u},而N(-overμ)1(G)(u)={v01,v02,…,v0n}.故S中的每个点的开邻集与其他点的开邻集没有交点,则S是(-overμ)1(G)的open packing集,即η0((-overμ)1(G))≥2.
反之,只需证明η0((-overμ)1(G))≤2成立即可.由此,只需证明在(-overμ)1(G)中任取3个点的集合S'都不是open packing集即可.根据所取3个点在(-overμ)1(G)中的位置不同,分以下7种子情形:
子情形i 若S'={vi',vj',vg'},i,j,g=1,2,…,n(n≥3),且i≠j≠g.由(-overμ)1(G)的定义可知vi'vj'∈E((-overμ)1(G)),vj'vg'∈E((-overμ)1(G)).S'中的点vi'的开邻集和vg'的开邻集有交点vj',故S'不是open packing集.
子情形ii 若S'={vi',vj',v0g},i,j,g=1,2,…,n(n≥3),且i≠j.当i≠j≠g时,vi'vj'∈E((-overμ)1(G)),v1gv0g∈E((-overμ)1(G)),S'中的点v1i的开邻集和v0g的开邻集有交点v1g,故S'不是(-overμ)1(G)的open packing集.当i=j或者j=g时,不妨假设i=g,根据(-overμ)1(G)的定义可知,v0gv1i∈E((-overμ)1(G)),v1iv1j∈E((-overμ)1(G)),S'中的点v0g的开邻集与v1j的开邻集有交点v1i.
子情形iii 若S'={v1i,v0j,v0g},i,j,g=1,2,…,n,且j≠g.同样,由(-overμ)1(G)的定义可知,v0ju∈E((-overμ)1(G)),v0gu∈E((-overμ)1(G)),即S'中的点v0j的开邻集与v0g的开邻集有交点u.
子情形iv 若S'={v0i,v0j,v0g},i,j,g=1,2,…,n,且i≠j≠g,易知,v0ju∈E((-overμ)1(G)),v0iu∈E((-overμ)1(G)),则S'中的点v0i的开邻集与v0j的开邻集有交点u.
子情形v 若S'={v1i,v1j,u},i,j=1,2,…,n,且i≠j,易知,v0iv1i∈E((-overμ)1(G)),v0iu∈E((-overμ)1(G)),则S'中的点v1i的开邻集与u的开邻集有交点v0i.
子情形vi 若S'={v1i,v0j,u},i,j=1,2,…,n,且i≠j,易知,v0iv1i∈E((-overμ)1(G)),v0iu∈E((-overμ)1(G)),则S'中的点v1i的开邻集与u的开邻集有交点v0i.
子情形vii 若S'={v0i,v0j,u},i,j=1,2,…,n,且i≠j,由(-overμ)1(G)的定义可知,v0iu∈E((-overμ)1(G)),v0ju∈E((-overμ)1(G)),则S'中的点v0i的开邻集与v0j的开邻集有交点u.
综上可知,η0((-overμ)1(G))≤2.故η0((-overμ)1(G))=2.
情形2)当m=1且图G的所有点的度都小于n-1或m>1时,令S'={v01},根据图的open packing集的定义,S'是(-overμ)m(G)的一个open packing集,再由open packing数的定义,则η0(G)≥1.
当G是一个连通图时,根据μm(G)图和(-overμ)m(G)图的定义,很显然diam((-overμ)m(G))≤2,再根据事实(iii),一定有η0(G)=1成立.
