共查询到20条相似文献,搜索用时 15 毫秒
1.
具有最大控制数的连通图的刻画 总被引:3,自引:3,他引:0
设G为一个P阶图,γ(G)表示G的控制数.显然γ(G)≤[p/2].本文的目的是刻画达到这个上界的连通图.主要结果:(1)当p为偶数时,γ(G)=p/2当且仅当G≈C4或者G为某连通图的冠;(2)当p为奇数时,γ(G)=(p-1)/2当且仅当G的每棵生成树为定理3.1中所示的两类树之一. 相似文献
2.
设γM(G)是连通图G=(V,E)的最大亏格,记EM^-(G)={e∈E(G)|G\e连通,且γM(G\e)=γM(G)}。若EM^-(G)≠0,则称G是γ(G)-可约的;否则称G是γM(G)-不可约的。本文证明了边的剖分不改变图的最大亏格可约性,点的扩张不改变上可嵌入图的最大亏格可约性;并给出了两类满足EM^-(G)=E(G)的非4-边连通图。 相似文献
3.
图的{P4}——分解 总被引:1,自引:0,他引:1
一个图G的路分解是指一路集合使得G的每条边恰好出现在其中一条路上.记Pl长度为l-1的路,如果G能够分解成若干个Pl,则称G存在{Pl}——分解,关于图的给定长路分解问题主要结果有:(i)连通图G存在{P3}-分解当且仅当G有偶数条边(见[1]);(ii)连通图G存在{P3,P4}-分解当且仅当G不是C3和奇树,这里C3的长度为3的圈而奇树是所有顶点皆度数为奇数的树(见[3]).本文讨论了3正则图的{P4}--分解情况,并构造证明了边数为3k(k∈Z且k≥2)的完全图Kn和完全二部图Kr,s存在{P4}-分解. 相似文献
4.
5.
p阶临界2-边连通图的最大边数 总被引:2,自引:0,他引:2
设G=(V,E)是2-边连通图,若对每个点v∈V,G-v不是2-边连通图,则称G是临界2-边连通图. 本文证明了p阶临界2-边连通图的最大边数是 7, P=6; (1/8)(P~2+4p) p=0(mod 4); f(p)= (1/8)(P~2+2p+13) p=1(mod 4); (1/8)(P~2+28) p=(2mod 4),p≠6 (1/8)(P~2+2p+9) p=3(mod 4)。并且给出了达到最大边数的极值图. 相似文献
6.
7.
8.
9.
图是超限制性边连通的充分条件 总被引:1,自引:0,他引:1
设G=(V,E)是连通图.边集S E是一个限制性边割,如果G-S是不连通的且G—S的每个分支至少有两个点.G的限制性连通度λ'(G)是G的一个最小限制性边割的基数.G是λ'-连通的,如果G存在限制性边割.G是λ'-最优的,如果λ'(G)=ζ(G),其中ζ(G)是min{d(x)+d(y)-2:xy是G的一条边}.进一步,如果每个最小的限制性边割都孤立一条边,则称G是超限制性边连通的或是超-λ'.G的逆度R(G)=∑_(v∈V) 1/d(v),其中d(v)是点v的度数.我们证明了G是λ'-连通的且不含三角形,如果R(G)≤2+1/ζ-ζ/((2δ-2)(2δ-3))+(n-2δ-ζ+2)/((n-2δ+1)(n-2δ+2)),则G是超-λ'. 相似文献
10.
图的最大亏格的一个性质 总被引:2,自引:0,他引:2
本文所考虑的图均指有限元向图,没有解释的术语和记号同[1].一个图称为简单图如果不含重边及环.曲面S这里指一个紧的,连通的,2-维闭流形(定向或不可定向),其亏格记为g(S).连通图G在曲面S上的一个2-胞腔嵌入意指存在一个1-1连续映射h:G→S使得S\h(G)的每个连通分支与圆盘拓扑同胚.连通图G的定向亏格γ(G)(或不可定向亏格γ(G))是指最小的整数k使得G在亏格为k的定向(或不可走向)曲面S上有2-胞腔嵌入;而图G的最大定向亏格,也常称之为最大亏格,记为γM(G),是指最大的整数k使得G在亏格为k定向曲面S上有… 相似文献
11.
12.
设G是一个图。G的最小度,连通度,控制数,独立控制数和独立数分别用δ,k,γ,i和α表示,图G是3-γ-临界的,如果γ=3,而且G增加任一条边所得的图的控制数为2.Sumner和Blitch猜想:任意连通的3-γ临界图满足i=3,本文证明了如果G是使α=k 1≤δ的连通3-γ-临界图,那么Sumner-Blitch猜想成立。 相似文献
13.
《数学的实践与认识》2013,(23)
有限群G的一个Cayley图X=Cay(G,S)称为正规的,如果右乘变换群R(G)在AutX中正规.研究了一类16p阶群G=〈a,b|a(8p)=b(8p)=b2=1,a2=1,ab=ab=a(4p-1)〉的3度无向连通Cayley图的正规性,其中p为奇素数,并得到该群的正规与非正规的Cayley图 相似文献
14.
图G中同构于K1,p的子图叫G的p-爪(p3).如果G中任意一个p-爪中1度顶点之间边的数目p-2,则称G为K1,p-受限图,它是无爪图(p=3时)的推广.本文证明了:连通、局部3-连通的K1,4-受限图是路可扩的. 相似文献
15.
16.
确定了广义超特殊p-群G的自同构群的结构.假设|G|=p^2n+m,|ζG|=p^m,其中n≥1,m≥2,(1)当p是奇数时,记AutG'G={α∈AutG|α在G上作用平凡},则(i)AutG'G Aut G,Aut G/AutG'G=~Zp-1;(ii)如果G的幂指数是p^m,那么AutG'G/InnG=~Sp(2n,p)×Zp^m-1;(iii)如果G的幂指数是p^m+1,那么AutG'G/InnG=~(K×Sp(2n-2,p))×Zp^m-1,其中K是p^2n-1阶超特殊p-群.特别地,当n=1时,AutG'G/Inn G=~Zp×Zp^m-1.(2)当p=2时,(i)如果G的幂指数是2^m,那么Out G=~Sp(2n,2)×Z2×Z2^m-2.特别地,当n=1时,|Aut G|=3·2^m+2,Aut G的Sylow子群都不是正规子群,并且Aut G的Sylow 2-子群都同构于HK,其中H=Z2×Z2×Z2×Z2^m-2,K=Z2.(ii)如果G的幂指数是2^m+1,那么OutG=~(ISp(2n2,2))×Z2×Z2^m-2,其中I是一个2^2n-1阶初等Abel 2-群.特别地,当n=1时,|AutG|=2^m+2并且Aut G=~HK,其中H=Z2×Z2×Z2^m-1,K=Z2. 相似文献
17.
设G=(V,E)是2(或3)-边连通的简单图,独立数为α,围长为g,n=|V|.若下列条件之一成立:(1)独立数α<3g2(或6g-21);(2)对G中任意含有m=3g2(或6g21)个顶点的独立集{v1,v2,...,vm}V,当g为偶数时,im=1dG(vi)n+4(或n-11);当g为奇数时,im=1dG(vi)n2(或n+1).则G是上可嵌入的. 相似文献
18.
19.
设G为n阶κ正则简单连通图(κ≥2),λ是图G的次根,d(G)是图G的直径,如果G不是二部图,且d(G)≠2,则d(G)≤[log(n-1)/log(κ/λ)],并且当G≌时,这一上界可达. 相似文献
20.
已经证明,当m≤3时,λ(m)-连通图G满足λ(m)(G)≤ξm(G)。当m≥4时,Bonsma等人指出不等式λ(m)(G)≤ξm(G)一般不再成立。最近,欧见平证明阶大于等于11的λ4-连通图G满足λ4(G)≤ξ4(G).本文通过研究满足λ(m)(G)〉ξm(G)的λm-连通图所具有的结构性质,不仅易得以上结论,还得到如下一般结论:当m≥5时,阶大于m(m-1)的λm-连通图G均满足λm(G)≤ξm(G).最后,通过构造例子说明本文给出的条件是最好的. 相似文献