共查询到20条相似文献,搜索用时 15 毫秒
1.
设G是一个无向多重图,G的定向直径是指G的所有强连通定向中直径的最小值.Dankelmann,Guo,Surmacs [J.Graph Theory,2018,88:5-17]证明了n阶无桥图G的定向直径至多为n-Δ+3,这里Δ是G的最大度.设H是G的一个生成子图,定义■,利用上述结论他们还证明了,给定边e的无桥图G的定向直径至多为n-|NG(e)|+5,以及给定无桥子图H的无桥图G的定向直径至多为n-|NG(H)|+3.设P3=uvw是G的一条长为2的路.易见P3包含两条边且这两条边均是P3的桥.本文利用将一条路收缩为一点的方法证明了给定P3的无桥图G的定向直径的上界为n-|NG(P3)|+5.特别地,若P3在一个4圈上或P3不在一个圈上但uv,vw分别在一个3圈上,定向直径至多为n-|NG(P3)|+4.最后举例说明了上述上界是紧的. 相似文献
2.
Letting F be a homogeneous(α1, α2) metric on the reductive homogeneous manifold G/H, we first characterize the natural reductiveness of F as a local f-product between naturally reductive Riemannian metrics. Second, we prove the equivalence among several properties of F for its mean Berwald curvature and S-curvature. Finally, we find an explicit flag curvature formula for G/H when F is naturally reductive. 相似文献
3.
令G是一个有限图,H是G的一个子图.若V(H)=V(G),则称H为G的生成子图.图G的一个λ重F-因子,记为Sλ(F,G),是G的一个生成子图且可分拆为若干与F同构的子图(称为F-区组)的并,使得V(G)中的每一个顶点恰出现在λ个F-区组中.一个图G的λ重F-因子大集,记为LSλ(F G),是G中所有与F同构的子图的一个分拆{B_i}_i,使得每个B_i均构成一个Sλ(F,G).当λ=1时,λ可省略不写.本文中,我们证明了当v≡4 mod 24时,存在LS(K1,3,Kv,v,v). 相似文献
4.
一个阶为n的图G称为是任意可分的(简作AP),如果对于任一正整数序列τ=(n1,n2,…,nk)满足n=n1+n2+…+nk,总是存在顶点集V(G)的一个划分(V1,V2,…,Vk)满足:对于i∈[1,k],|Vi|=ni,且子图G|Vi|是图G的Vi导出的一个连通子图.我们用S~*=S(n;m1,m2,…,mn)来表示最大度△(S~*)=3的太阳图.本文讨论了图S~*Pm(m≥3)的任意可分性. 相似文献
5.
令G表示n个顶点的图,如果G的每个子图中都包含一个度至多为k的顶点,则称G为k-退化图.令N(G,F)表示G中F子图的个数.主要研究了k-退化图中完全子图和完全二部子图的计数问题,给出了计数的上界以及相应的极图.首先,证明了Ν(G,Kt)≤(n-k)(k t-1)+(k t).其次,如果s,t≥1,n≥k+1且s+t≤k,我们证明了Ν(G,Ks,t)≤{(k s)(n-s s)-1/2(k s)(k-s s),t=s,(k s)(n-s t)+(k t)(n-t s)-(k t)(k-t s),t≠s.此外,还研究了在最大匹配和最小点覆盖为给定值的情况下,图G中的最大边数.记v(G),K(G)分别为图G的最大匹配数和最小点覆盖.证明了当v(G)≤k,K(G)=k+r且n≥2k+2r2+r+1时,有e(G)≤(k+r+1 2)+(k-r)(n-k-r-1). 相似文献
6.
图的联结数与[a,b]-因子存在性 总被引:2,自引:0,他引:2
设G是一个n阶图,a,b,m1,m2是非负整数且满足1≤a<b和b≥m1.H1和H2是图G的两个边不交的子图且满足|E(H1)|=m1和|E(H2)|=m2.证明下列结论:若图G的联结数bind(G)>(a+b-1)(n-1)/bn-(a+b)-2(m1+m2)+2且n≥(b-1)(a+b-1)(a+b-2)+2b(m1+m2)/b(b-1),则图G有一个[a,b]-因子F满足E(H1)(∈)E(F)和E(H2)∩ E(F)=φ.进一步指出这个结果是最好的. 相似文献
7.
设G是一个图,并设n,k,r,a和b是整数且满足k≥1,k≤a<b和n≥3.对于G的给定的k-正则图H,如果G是K1,n-free图,且G的最小度至少是((n(a+1)+b-a-(k+1))/(b-k))「(ab+b-a-k)/(2(n-1))」-(n-1)/(b-k)(「(an+b-a-k)/(2(n-1))」)2-1,那么G有一个[a,b]-因子F使得E(H)(∈)E(F).类似地,也得到了关于图G有一个r-因子含有G中给定的k-正则子图的度条件.进一步,指出这些度条件是最佳的. 相似文献
8.
图G为具有m条边的连通图,E(G)={e1,e2,…,em},H={H1,H2,…,Hm}为由m个连通图构成的集合.图G[H]为G与H的张量积图,即对每个i(1≤i≤m),ei被Hi替代而得到的图.张量积这一图运算包含了多个边替代图运算,例如细分、三角化、钻石化等图运算.本文中,我们给出了G[H]的Tutte多项式的显式表达式,进而得到了细分图、三角化图、钻石化图等运算图的Tutte多项式和生成树数目. 相似文献
9.
《数学进展》2017,(2)
令G是一个有限图,H是G的一个子图.若V(H)=V(G),则称H为G的生成子图.图G的一个λ重F-因子,记为S_λ(F,G),是G的一个生成子图且可分拆为若干与F同构的子图(称为F-区组)的并,使得V(G)中的每一个顶点恰出现在λ个F-区组中.一个图G的λ重F-因子大集,记为LS_λ(F,G),是G中所有与F同构的子图的一个分拆{B_i},使得每个B_i均构成一个S_λ(F,G).当λ=1时,λ可省略不写.在[Ars Combin.,2010,96:321-329]中已经得到了LS_λ(K_(1,2),K_(v,v))的存在谱.本文证明了当v≡4(mod 12)时,存在LS(F,K_(v,v,v)),这里F∈{K_(1,3),K_(2,2)}. 相似文献
10.
设F是一个图,■是一个超图,如果存在一个双射φ:E(F)→E(■),使得?e∈E(F)有e?φ(e),那么称超图■是Berge-F.不含Berge-F作为子超图的n阶r-一致超图所能达到的最大边数称为Berge-F的Turán数,记作exr(n,Berge-F).线性森林是指连通分支全是路或者孤立顶点的图.设■n,k是一类含有n个顶点k条边的线性森林图族.本文研究了r-一致超图中Berge-■n,k的Turán数.当r≥k+1和3≤r≤■(k-1)/2■-1时,分别确定了exr(n,Berge-■n,k)的精确值;当■(k-1)/2■≤r≤k时,给出了exr(n,Berge-■n,k)的上界. 相似文献
11.
12.
设G是一个n阶简单图.G的第二类Zagreb指数定义为M2(G)=■didj.其中di表示顶点i的度.Xu等(2014)提出了一个关于第二类Zagreb指数的猜想:在所有阶数为n、边数为m的图中,M2(G)最大的图是拟完全的.借助于门槛图的Ferrers表的性质,本文将上述猜想转化为组合矩阵论优化问题,并给出该猜想的一个代数证明. 相似文献
13.
设G是顶点数为2n且至多含有2(n-c)个奇分支的简单图(1≤c≤n).若不存在G的两个距离为2的顶点,其度均小于c-1,则G的边独立数至少为c,除非G含一类明显的禁用导出子图.特别,我们给出了Fan(-1)-型图含有1-因子的充要条件. 相似文献
14.
15.
给定图G=(V,E)和非负整数h,图G的h-限制点割S是V(G)的一个子集(如果存在)使得G-S不连通且G-S中任一点的度数至少为h.图G的h-限制连通度κ~h(G)是G的最小h-限制点割的阶数.本文中,我们证明了κ~2(FCQn)=4n-4 (n≥8),κ~2(SQn)=4n-8(n≥4),其中FCQn和SQn分别是n维折叠交叉超立方体和n维spined cube. 相似文献
16.
Let F={H1,...,Hk}(k> 1) be a family of graphs.The Turán number of the family F is the maximum number of edges in an n-vertex {H1,...,Hk)-free graph,denoted by ex(n,F) or ex(n,{H1,H2,...,Hk}).The blow-up of a graph H is the graph obtained from H by replacing each edge in H by a clique of the same size where the new vertices of the cliques are all different.In this paper we determine the Turán number of the family cons... 相似文献
17.
图G的边分解是指将G分解成子图G1,G2,...,Gm,使得E(G)-E(G1)∪…∪.E(Gm),且对任意i≠j,有E(Gi)∩E(Gj)=?.若一个森林的每个连通分支都是路,则称该森林为线性森林.图G的线性荫度la(G)是指使得G可以边分解为m个线性森林的最小整数m.本文证明了Δ(G)≥15的IC-平面图G的线性荫度为[Δ(G)/2],这里Δ(G)是图G的最大度. 相似文献
18.
用P(G,λ)表示简单图G的色多项式.设G是一个给定的简单图,若对任意简单图H,当P(H,λ)=P(G,λ)时都有H和G同构(记为H≌G),则称图G是色唯一的.本文证明了以下结果:设n,k,△都为非负整数,其中k≥0,△∈{4,5},若n≥1/3k~2+1/3△~2-1/3k△-1/3k-1/3△+4/3,则完全三部图K(n,n+△,n+k)是色唯一的.同时还给出了一个猜想. 相似文献
19.
20.
顶点数为n,边数为m的简单图G的非负广义邻接矩阵定义为U(G)=γAA(G)+γII(G)+γJJ(G)+γDD(G),其中γA,γI,γJ,γD是一些非负实数,A(G)是图G的邻接矩阵,D(G)=diag(d1,d2,…,dn),I(G)是单位矩阵,J(G)是全1矩阵.本文得到了谱半径ρU(G)的一些界,并刻画了达到这些界时的极图.此外还得到了ρAα(G)的新界以及ρA(G),ρL(G)和ρQ(G)的已知界. 相似文献