共查询到20条相似文献,搜索用时 78 毫秒
1.
棒棒糖图Bm,n是由圈Cm上的任一个顶点和路Pn的一个1度顶点重合而得到n+m-1阶连通图。研究了棒棒糖图Bm,n的IC-着色和IC-指数,推出了它的IC-指数的一个上界,并借助计算机编程,证明了m分别为3,4,5时的几种棒棒糖图Bm,n的IC-着色和IC-指数。当m=3,n=1,2,…,6时,有M(B3,n)=5n+2;当m=4,n=1,2,…,5时,有M(B4,1)=13,M(B4,2)=21,M(B4,3)=26,M(B4,4)=34,M(B4,5)=40;当m=5,n=1,2,3,4时,有M(B5,1)=21,M(B5,2)=31,M(B5,3)=39,M(B5,4)=48。 相似文献
2.
章鱼图H(Cm,n)是指由圈Cm的一个顶点与星图STn=K1,n的中心重迭得到的图,研究了章鱼图H(Cm,n)的IC-着色问题,通过分类讨论的方法,分别得到了当m=3,4,5,n≥1时章鱼图H(Cm,n)的极大IC-着色和它们相应的IC-指数,并提出章鱼图H(Cm,n)一个上界猜想。 相似文献
3.
设正整数 xi = f (vi)是图 G 的顶点 vi 的着色,H 是 G 的子图,f ()H 是 H 的顶点着色的和,若对任意正整数j(1 j f ()G )都存在 G 的连通子图 H 使得 j = f ()H ,则称 f 是 G 的 IC -着色.若 f ()G 最大,则称 f ()G 为 G 的 IC -指数.考虑了圈 Cn 的 IC -着色和 IC -指数 I ;得到了:当 n =10111214时 Cn 的 IC -指数 相似文献
4.
一类偶图的符号边控制数 总被引:1,自引:0,他引:1
徐保根 《华东交通大学学报》2004,21(2):124-126
对于任意正整数m和n,构造了一类偶图(二部图)G(m,n),其阶为2mn,边数为3mn-m-n,确定了其符号边控制数为γ',(G(m,n))=m+n-mn.从而证明了n阶偶图的最小符号边控制数B(n)<1+2( )2n-n/2,并指出了文[6]一个猜想的错误. 相似文献
5.
设r(G)表示图G的控制数,G○H表示两个图G和H的叉积,SGravier提出了如下猜想,对任意图G和H,均有r(G○H)≥r(G)r(H),本文给出了该猜想的反例,从而说明了该猜想是不正确的。 相似文献
6.
关于图的符号边控制数 总被引:5,自引:0,他引:5
徐保根 《华东交通大学学报》2003,20(2):102-105
设G为一个n阶连通图,m=|E(G)|,△和δ分别为图G的最大度和最小度,给出了图G的符号边控制数的一个下界、即γ‘‘‘‘‘‘‘‘,(G)≥[M-(△-δ)(△-2)(n-δ)/2△-1],并确定了几类特殊图的符号边控制数。 相似文献
7.
于崇智 《华东交通大学学报》1998,15(2):50-53
定义在图G=(V,E)顶点集V上的一个二值函数f;V→{ 1,-1},若任意υ∈V,f(N[υ])≥1,称f是G的一个符合控制函数,图G的符合控制函数f的权重f(V)=∑υ∈Vf(υ)的最小值定义为图G的符合控制数,记为rs(G),本文给出了图的最小控制函数的几个性质定理。 相似文献
8.
徐保根 《华东交通大学学报》2007,24(1):120-122
G.Chartand[1]引入了一个图G的局部色数x1(G)的概念,在本文中的我们主要出了图的局部色数的界限,证明了对任意n阶图G(n≥2),均有x1(G) x1(■)≤2n-1,并确下了一些特殊图的局部色数. 相似文献
9.
对图G(V,E),及二值函数f:V→{0,1}记f{v}={u│u∈N[v],且f(u)-1},其中N[v]={u│vu∈E}∪{v}若f满足任意v∈V,│f[v]│≥1,则称f为G的一控制函数,并称f(V)= ∑v∈V(f(v)为f的权;图的控制数γ(G)定义为图的控制函数的最小权,即γ(G)=min{│f(V)│f为G的一控制函数}类似的可定义图的边控制数,本文建立了确定图的控制数的Hopfield网络型和算法。 相似文献
10.
设G是一个图,用y(G)和E(G)表示它的顶点集和边集,并设g(x)和f(x)是定义在V(G)上的两个整数值函数,且对C每个x∈V(G),有5/2r-1≤g(x)≤f(x),则图G的一个支撑子图,称为G的一个(g,f)-因子,如果对每个x∈V(G),有g(x)≤d,(x)≤f(x).图G的(g,f)-因子分解是指E(G)能划分成边不交的(g,f)-因子,设F=|F1,F2,…,Fm|和H分别是图G的因子分解和子图,若对所有1≤i≤m有|E(H)∩E(Fi)|=r,则称,和H(m,r)-正交.本文证明:若G是一个(mg m-1,mf-m 1)-图,H是G中任一有mr条边的子图,则G有一个(g,f)-因子分解与H(m,r)-正交。 相似文献
11.
一个简单无向图,如果它的全自同构群作用在它的弧集上传递,则称该图为对称图.本文给出了3p2阶连通4度对称图的完全分类,其中P是一个素数. 相似文献
12.
周尚超 《华东交通大学学报》2006,23(5):128-129
A.Kotzig提出这样一个问题:对于任意正则自补图G,是否存在G的一个自补置换s,s是{1,4,4,...,4}型,定理1否定地回答了这个问题. 相似文献
13.
14.
15.
1994年, Mitchem和Simoson在研究标号图的问题时,提出了超边优美图的概念。在随后的研究中,一些图被证明具有超边优美性质,同时关于超边优美图的一些猜想也被提出。本文利用递归方法构造了轮图Wn与舵轮图Hn的超边优美标号,证明了这两类图是超边优美图。 相似文献
16.
如果一个图的自同构群作用在它的弧集上是传递的,那么称这个图为对称图.文中给出了8p阶5度对称图的完全分类. 相似文献
17.
根据3-正则Halin图的Hamilton性,结合其顶点间距离的关系,通过适当地选取顶点进行着色后得证了4和6阶以上3-正则Halin图G的可区别数分别为3和2. 相似文献
18.
A code is said to be a w-identifiable parent property code (or w-IPP code for short) if whenever d is a descendant of w (or fewer) codewords, and one can always identify at least one of the parents of d. Let C be an (N, w 1, q)-code and C* an (w 1)-color graph for C. If a graph G is a subgraph of C* and consists of w 1 edges with different colors, then G is called a (w 1)-pattern of C*. In this paper, we proved that C is a w-IPP code if and only if there exists at most one vertex with color degree more than 1 in any (w 1)-pattern of C*. 相似文献
19.
给出了ω4g,4h+3的(r1,r2,…,r4g,4h+2)-冠的定义,讨论了ω4g,4h+3的(r1,r2,…,r4g,4h+2)-冠的优美性,用构造性的方法给出了一些特殊的ω4g,4h+3的(r1,r2,…,r4g,4h+2)-冠的优美标号。证明了一些特殊的ω4g,4h+3的(r1,r2,…,r4g,4h+2)-冠是交错图。 相似文献
20.
关于圈C4h的(r1,r2,…,r4h)-冠的优美性 总被引:17,自引:0,他引:17
吴跃生 《华东交通大学学报》2011,28(1):77-80
给出了圈C4h的(r1,r2,…,r4h)-冠的定义,讨论了圈C4h的(r1,r2,…,r4h)-冠的优美性,用构造性的方法给出了一些特殊的圈C4h的(r1,r2,…,r4h)-冠的优美标号.证明了一些特殊的圈C4h的(r1,r2,…,r4h)-冠是交错图. 相似文献