共查询到20条相似文献,搜索用时 15 毫秒
1.
研究了含有多个圈的图的邻接矩阵的秩.将k(k≥2)条点不交的路,首和尾分别粘合得到的图称为Θ-图.用Γ(k-1)表示含有Θ-图作为导出子图的(k-1)-圈图的集合,而用C(η,k)表示含有n个顶点和k个边不交的圈的图的集合.确定了Γ(k-1)中秩等于5和6的图以及C(n,k)中秩等于4,5和6的图. 相似文献
2.
一个图G 的无圈k- 边染色是指G 的一个正常的不产生双色圈的k- 边染色. G 的无圈边色数a′(G) 定义为使得G 有一个无圈k- 边染色的最小的整数k. 本文完全刻画了最大度不为4 的没有K4-图子式的图的无圈边色数. 相似文献
3.
设k是一个正整数,G是一个顶点数为|G|=4k的图. 假设σ\-2(G)≥4k-1, 则G有一个支撑子图含k-1个4圈和一条顶点数为4的路,使得所有这些圈和路都是相互独立的. 设G=(V\-1,V \-2;E)是一个二分图使得|V\-1|=|V\-2|=2k. 如果对G中每一对满足x∈V\-1和y∈V\-2的不 相邻的顶点x和y 都有d(x)+d(y)≥2k+1, 则G包含k-1个相互独立的4圈和一条顶点数为4的路,使得所有这些圈和路都是相互独立的,并且此度条件是最好的. 相似文献
4.
图G包含4k个点,k≥2,如果σ_2(G)≥4k,则G包含k-2个4-圈和一个8-圈,并且这k-1个圈点不相交. 相似文献
5.
6.
若多重二部图中不同划分的任意一对点之间至多包含两条边,则称其为标准多重二部图.令D是一个标准多重二部图,使得|V1|=|V2|=n≥2,其中n是正整数.我们证明了若D的最小度至少是3n/2,则D 一定包含(「)n/2」个点不交的4圈,并且当n为奇数时,上述(「)n/2」个4圈中的前n-3/2中的每条边都是重边,剩余的一... 相似文献
7.
8.
图G的一个k-边染色是一个映射ψ:E(G)→{1,2…k},使得每一对相邻边x和y,有ψ(x)≠ψ(y,).G的边色数χ'(G)是使得G有一个k-边染色的最小的整数k.本文证明了:如果G是一个最大度为6能嵌入到欧拉示性数非负的曲面的图,且满足下列条件之一,那么χ'(G)=6:(1)不含带弦4-圈;(2)同时不含带弦5-圈和带弦6-圈. 相似文献
9.
图G的一个边分解是指将G分解成子图G_1,G_2,…,G_m使得E(G)=E(G_1)=∪E(G_2)∪…∪E(G_m),且对于i≠j,E(G_i)∩E(G_j)=?.一个线性k-森林是指每个分支都是长度最多为k的路的图.图G的线性k-荫度la_k(G)是使得G可以边分解为m个线性k-森林的最小整数m.显然,la_1(G)是G的边色数χ'(G); la_∞(G)表示每条分支路是无限长度时的情况,即通常所说的G的线性荫度la(G).利用权转移的方法研究平面图的线性2-荫度la_2(G).设G是不含有5-圈和相邻4-圈的平面图,证明了若G连通且δ(G)≥2,则G包含一条边xy使得d(x)+d(y)≤8或包含一个2-交错圈.根据这一结果得到其线性2-荫度的上界为[△/2]+4. 相似文献
10.
《数学的实践与认识》2020,(10)
如果对一个图G的每个顶点v,任给一个k-列表L(v),使得G要么没有正常列表染色,要么至少有两种正常列表染色,则称图G具有M(k)性质.定义图G的m数为使得图G具有M(k)性质的最小整数k,记为m(G).已有研究表明,当k=3,4时,图K_(1*r,3*(k-2))具有M(k)性质,且当r≥2时,m(K_(1*r,3*(k-2)))=k.本文将上述结论推广到每一个k,证明了对任意r∈N~+,k≥3,图K_(1*r,3*(k-2))具有M(k)性质,且当k≥4,r≥(k-2)时,m(K_(1*r,3*(k-2)))=k.此外,得到图K_(1,3,3,3)的m数为4,该图是图K_(1*r,3*(k-2))中r=1,k=5时的特殊情况,同时也是现有研究中尚未解决的一个问题. 相似文献
11.
记[k]={1,2,…,k),称为颜色集.设φ:E(G)→[k]为图G的边集合到[k]的映射,令f(v)表示与顶点v关联的边的颜色的加和.如果对任意一条边uv∈E(G),都有φ(u)≠φ(v),f(u)≠f(v),则称φ为图G的邻和可区别[k]-边染色,k的最小值称为图G的邻和可区别边色数,记为ndi_Σ(G).若对任意一条边uv∈E(G),都有f(u)≠f(v),则称φ为图G的k-边权点染色,称图G是k-边权可染的.运用组合零点定理证明了对于最大度不等于4的Halin图有:ndi_∑(G)≤Δ(G)+2,并证明了任一Halin图是4-边权可染的. 相似文献
12.
14.
设G是一个图,若对于图G的任一条边e,G-e都存在一个分数k-因子,则称G是一个分数k-消去图.若k=2,则称分数k-消去图为分数2-消去图.本文证明了当bind(G)≥2,并且δ(G)≥3时,G是分数2-消去图. 相似文献
15.
对于图G=(V(G),E(G)),如果一个映射φ:E(G)→{1,2,…,k},使得G中任意相邻的两边e1,e2满足φ(e1)≠φ(e2),并且G中不含有双色圈,则称φ为G的一个无圈边染色.对于给定的列表分配L={L(e)|e∈E(G)},如果存在图G的一个无圈边染色φ,使得对于任意边e∈E(G),均有φ(e)∈L(e),则称染色φ为G的一个无圈L-边染色.如果对于任意的列表分配L,当对所有的边e∈E(G)满足|L(e)|≥k时,图G均存在无圈L-边染色,那么称G是无圈k-边可选的.使图G无圈k-边可选的最小的正整数k,称为G的无圈列表边色数,用a’l(G)表示.本文证明了对于最大度△≤4的连通图G,如果|E(G)|≤2|V(G)|-1,则a’l(G)≤6,扩展了Basavaraju和Chandran文[J.Graph Theory,2009,61(3):192-209]的结果. 相似文献
16.
Fan和Raspaud 1994年提出如下猜想任一无桥3正则图必有三个交为空集的完美匹配. 本文研究一类特殊的无桥3正则图G存在图G的一个完美匹配M1使得G-M1恰含有两个奇圈和若干偶圈. 在偶圈数≤2的情形以及在偶圈数≤4且G是圈4-边连通的情形,本文证明了一定存在图G的两个完美匹配M2和M3使得M1∩M2∩M3=φ. 相似文献
17.
图的正常k-全染色是用k种颜色给图的顶点和边同时进行染色,使得相邻或者相关联的元素(顶点或边)染不同的染色.使得图G存在正常k-全染色的最小正整数k,称为图G的全色数,用χ″(G)表示.证明了若图G是最大度△≥6且不含5-圈和相邻6-圈的平面图,则χ″(G)=△+1. 相似文献
18.
过抛物线上任意三点 A1 ,A2 ,A3 ,分别作切线 ,三条切线围成一个△ B1 B2 B3 叫做切线三角形 ,而△ A1 A2 A3 叫切点三角形 .同样过抛物线上任意四点 A1 ,A2 ,A3 ,A4,分别作切线 ,四条切线围成一个凸四边形叫切线四边形 ,同样 A1 A2 A3 A4叫切点四边形 .不难发现 ,过抛物线上任意五点作五条切线 ,它们相交成 10个点 ,已不能围成凸五边形 ,看来 n≥ 5时 ,切点 n边形已不再有切线 n边形了 .本文将研究切点 n( =3 ,4 )边形与此时切线 n边形的重心的性质 ,然后给出一个应用 .定理 1 如图 1,设 A1 与 A2 是抛物线 y2= 2 px上任意两点 ,… 相似文献
19.
设Kv是一个v点完全图.G是一个有限简单图.Kv上的一个图设计G-GD是一个对子(X,B),其中X是Kv的顶点集合,B是Kv的一些与G同构的子图(称为区组)的集合,使得Kv的任意一条边恰出现在B的一个区组中.文中讨论的简单图是C^(r)2k,即带有一条弦的2k长圈,其中r表示弦的两个端点之间的顶点个数,1≤r≤k-1.文中给出了一个构作C^(r)m设计的统一方法,并得到关于v≡0,1(mod2k+1)时C^(r)2k-GD(v)的一系列结果. 相似文献
20.
用g(G)和δ(G)分别表示一个图G的围长和顶点最小度. ζ(G)为图G的Betii亏数,主要证明了以下2个结果1)设G为k-边连通简单图,若对G中任意圈C,存在点x∈C满足dG(x)>|V(G)|/(k-1)2+2)+k-g(G)+2,k=1,2,3,则G是上可嵌入的.且不等式的下界是最好的;2)设G为k-边连通简单图,则ζ(G)≤{max{1,m},k=1,max{1,1/(k-1)m -1}K=2,3 其中m= |V(G)|g(G)-6/g(G)2+(δ(G)-2)g(G)-4'且不等式的上界是可达的.进而得到了最大亏格一个比较好的下界. 相似文献