共查询到19条相似文献,搜索用时 62 毫秒
1.
研究了n个顶点的连通二部图当控制数γ(G)≥3,最大度Δ(G)≥n-γ(G)-1时的最大边数。 相似文献
2.
研究了图的 Fractional 控制问题,主要给出了关于联图的 Fractional 控制数的1个上界,由此确定了几类特殊联图的 Fractional 控制数,并推广了部分已知的结果。 相似文献
3.
欧建光 《温州大学学报(自然科学版)》1995,(3):24-29
设G是n阶连通图γc(G)dc(G)i(G)和ir(G)分别表示图G的连通控制数,边通控制划分数,独立控制数和无赘数,本文证明了此结构。 相似文献
4.
刘凌 《上海理工大学学报》2015,37(6):517-519
Wenger图H_m(q)是定义在有限域F_q上的q-正则二部图.根据二部图G=(X∪Y,E)的控制数为Y在X中的控制数与X在Y中的控制数之和,采用矩阵运算的方法在H_m(q)中通过构造含点数最少的控制集,说明了这两个控制数应该相等,从而确定了Wenger图的控制数. 相似文献
5.
设G=(X,Y;E)是连通二部图,│X│= │Y│=n,则(1)NC2=n≥4,则G是点泛圈偶图。(2)NC2≥n-1≥4,且6≥2,则G含有Hamilton圈,或者G的任何一点都含在G中长为2n-2的圈中,且这个圈为G的控制圈。 相似文献
6.
对于一个非空图G=(V,E)和一个函数f:E→{-1,+1},若SE,则记f(S)=∑e∈Sf(e).若对于G中每个非平凡的团K均满足f(E(K))≥1,则f被称为G的一个符号团控制函数,G的符号团控制数表达为 相似文献
7.
8.
建立了二部图C=(V,U,E)的二级优先匹配规则,在此规则下,用改进的深度优先搜索对匹配算法进行改进,使得算法能够根据连通分量的个数动态优化算法的性能,使动态最大匹配算法的时间复杂度提高到0(max(|V|,|E|,m|E|)). 相似文献
9.
《汕头大学学报(自然科学版)》2017,(4):25-34
设图G=(V,E)是一个简单无向图,若实值函数f:V→{-1,1,2}满足以下两个条件:(i)对于任意v∈V,均有∑_(u∈N[v])f(u)≥1成立;(ii)任意v∈V,若f(v)=-1,则存在一个与v相邻的顶点u∈V,满足f(u)=2,则称该函数为图G的符号罗马控制函数.定义图的符号罗马控制数为γSR(G)=min{f(V)f是图G的符号罗马控制函数}.通过对完全多部图中的顶点数进行分类,给出了当k≥3时,完全多部图K(n_1,…,n_i,…,n_k)的符号罗马控制数的准确值. 相似文献
10.
11.
对于图G,如果收缩任意一条边,它的控制数下降,则称图G是圆点临界图.如果粘贴图G中任意两个顶点,它的控制数下降,则称图G是全圆点临界图.证明了对于k-正则图,当k为奇数时不存在2-全圆点临界图;当k为偶数时当且仅当此图为k+2阶图时其为2-全圆点临界图.还对是否存在不含临界点的k-全圆点临界图(k≥4)进行了研究,并得出结论:存在不含临界点的4-全圆点临界图和5-全圆点临界图. 相似文献
12.
研究定义在Γn,γ(n≥2γ+1,γ≥2)中的树,借助夺邻、嫁接等移边定理,通过构造一种新的移边运算Operation I,给出了Γn,γ中前两大谱半径,并证明了T(n,r),S(n,r)是达到前两大谱半径的图. 相似文献
13.
证明了(1)若图G是二部图,则当r≥s(χ’(G)-1)+2时,χr,s,1(G)=χr,0,0(G);(2)若图G是非二部图,则当r≥sχ’(G)/χ(G)-s+1且r不是s的倍数时,χr,s,1(G)=χr,0,0(G);(3)当Δ(G)≥2,χ’(G)=Δ(G),且s≥2r,r≥2t时,χr,s,t(G)=χ0,s,0(G);(4)当χ’(G)=Δ(G)+1且s-t≥r≥t时,χr,s,t(G)=χ0,s,0(G)。 相似文献
14.
15.
16.
设γ’st(G)表示图G的符号边全控制数,给出了一般图G和超立方体的符号边全控制数的一个下界和一个上界,计算了等完全二部图的符号边全控制数的精确值。 相似文献
17.
18.
设G=(V,E)是一个没有孤立顶点的图,如果一个函数f:E→{-1,1},满足f(E(v))≥1,v∈V(G),则称f为图G的一个符号星控制函数.图G的符号星控制数定义为:γss(G)=min{f(E)|f为G的反符号星控制函数},论文确定了pq(2pq,且p、q为互异的素数)阶群Q上Cayley图X(Q,M)的符号星控制数γss(X(Q,M))=(p-1)q+1,M表示群Q的极小生成集. 相似文献
19.
利用图论的方法研究了图G同其补图G的Roman控制数,得到了完全图和完全多部图的补图的Roman控制数及图G同其补图G的Roman控制数的关系;还研究了图G的生成子图H同G的Roman控制数的关系和极大无完美匹配的简单图G的Roman控制数. 相似文献