共查询到20条相似文献,搜索用时 218 毫秒
1.
施容华 《青海师范大学学报(自然科学版)》1986,(Z1)
除非特别指出,本文所说的图都是无向、无环和多重边的有限图。未定义的术语可参见文献[1,2,3]。圈是连通图理论中基本的重要研究对象之一。无圈的连通图只有树;除树外,每个连通图都含有圈。图G的最长圈的长度称为G的周长,记作C(G);图G的最短圈的长度称为G的围长,记为g(G)。非树连通图的周长和围长都是有限数,且g(G)≤C(G)。什么时后非树连通图G的圈长整数集就是整数子集{g(G),……,C(G)}?对 相似文献
2.
Rm-边割存在的充分条件 总被引:1,自引:0,他引:1
Rm边割是这样一种边割, 它将连通图分割为各分支的阶都不小于m的不连通图. 设G是一个阶不小于2m的连通图. 用 c(G)表示G的周长 (即G中最长圈的长度), 如果c(G)≥m+1, 那么G含有Rm边割, 而且周长c的下界在一定程度上是不可改进的. 相似文献
3.
《青海师范大学学报(自然科学版)》2018,(4)
圈基常用于描述图的圈结构.在实际应用算法中,算法的复杂度取决于圈基的选择.圈基的长,即其包含的边数,直接影响算法的速度.2-连通图G圈基长的一个下界是2 |E (G)|-|V (G)|,其中V (G)和E (G)分别是顶点集和边集.若图G包含长为2 |E (G|)-|V (G)|的圈基,则它是平面图.本文应用曲面嵌入图理论将这一结果推广至曲面嵌入图上. 相似文献
4.
设G是阶数为n 51的简单连通图,满足周长g(G)4,且2δ(G)(2n-9)/5。若G是哈密顿图,则其线图L(G)是泛圈图。 相似文献
5.
设G为n阶的连通k(k≥3)圈图,λ1(G)是图G的laplacian矩阵的最大特征值.本文讨论了圈长为3的k圈图的最大特征值与其顶点数及各顶点的悬挂边个数之间的关系. 相似文献
6.
TT''''-free图的最长圈 总被引:1,自引:0,他引:1
本文提出了两类新的禁用子图T和T'.一个图G称为TT'-free图,若G中不含同构于T或T'的导出子图,它是比无爪图更广的一个图类.G的一个圈C称为控制圈(简记为D-圈),若E(G-C)=φ.本文证明了:顶点数不小于3的连通、局部连通TT'-free图G最长圈为D-圈,且G是局部泛圈的. 相似文献
7.
陈兰 《青海师范大学学报(自然科学版)》2009,(1)
图G的Merrifield-Simmons指标是指图G的独立集的个数,其中包括空集.文献[3]得到n阶单圈图中具有最大、次大、最小的Merrifield-Simmons指标的图类,以及讨论了当圈长为k时具有最大Merrifield-Simmons指标的图.文献[4,5,9]给出了圈长为k的n阶单圈图的第二大,第三大和第四大Merrifield-Simmons指标及对应的图.文献[10]给出了圈长为3的9阶单圈的Merrifield-Simmons指标的第五大值及对应的图,本文得到圈长为k的n阶单圈图的第五大Merrifield-Simmons指标及对应的图. 相似文献
8.
本文提出了两类新的禁用子图T和T′.一个图G称为TT-′free图,若G中不含同构于T或T′的导出子图,它是比无爪图更广的一个图类.G的一个圈C称为控制圈(简记为D-圈),若E(G-C)=Φ.本文证明了:顶点数不小于3的连通、局部连通TT-′free图G最长圈为D-圈,且G是局部泛圈的. 相似文献
9.
10.
对于任意自然数k ,如果图G包含模k长的每一个圈 ,那末图G被称为模k泛圈图 .本文证明了连通K1,4 -自由图G是k =3的泛圈图 ,这一结果断定了Thomason猜想在连通图中的正确性 . 相似文献
11.
设G=(X,Y;E)是连通二部图,|X|=n≥5,|Y|=n-δ,若NC2≥n-δ,则图G的周长C(G)≥2(n-δ)。进而G有控制圈。 相似文献
12.
《上海大学学报(自然科学版)》2017,(2)
对于图G,如果G-F是不连通的且至少有两个分支含有圈,则称F为图G的圈边割.如果图G有圈边割,则称其为圈可分的.最小圈边割的基数叫作圈边连通度.如果去除任何一个最小圈边割,总存在一分支为最小圈,则图G为超圈边连通的.设G=(G_1,G_2,(V_1,V_2))为双轨道图,最小度δ(G)≥4,围长g(G)≥6且|V_1|=|V_2|.假设G_i是k_i-正则的,k_1≤k_2且G_1包含一个长度为g的圈,则G是超圈边连通的. 相似文献
13.
马刚 《安徽大学学报(自然科学版)》2017,41(4)
对图G的一个正常边染色,如果图G的任何一个圈至少染3种颜色,则称这个染色为无圈边染色.若L为图G的一个边列表,对图G的一个无圈边染色φ,如果对任意e∈E(G),都有φ(e)∈L(e),则称φ为无圈L-边染色.用a′_(list)(G)表示图G的无圈列表边色数.论文证明:若图G是一个平面图,且它的最大度Δ≥5,围长g(G)≥7,则a′_(list)(G)=Δ. 相似文献
14.
图G的Merrifield-Simmons指标是指图G 的独立集的个数,其中包括空集.文献[2]得到n阶单圈图中具有最大、次大、 最小的Merrifield-Simmons指标的图类,以及讨论了当圈长为k时具有最大Merrifield-Simmons 指标的图.文献[3]给出了圈长为k的n阶单圈图的第二大Merrifield-Simmons指 标.本文得出了圈长为k的n阶单圈图的Merrifield-Simmons指标的第三大值和单圈 图簇∪nk=3C(n,k)的Merrifield-Simmons指标的第三大值及对应的图. 相似文献
15.
朱俊杰 《成都大学学报(自然科学版)》2010,29(2):124-126
1997年,C.Berge提出了图G奇圈横贯的定义,并用图G+K2研究了图G的奇圈横贯,最后得出结论,τ=n—-α(G+K2).将图G的奇圈横贯推广到超图H上,并引入新概念H+K2,得到超图H的两个顶点x和z之间有奇长链的充分条件. 相似文献
16.
图G的星边染色是指G的一个正常边染色,使得G中任一长为4的路和长为4的圈均不是2-边染色的.图G的星边色数χ’ st(G)表示图G有星边染色的最小颜色数.仙人掌图是一个连通图使得每个块是圈或者边.利用数学归纳法得到了一类仙人掌图Cn·Cm(n≥3,m≥3)的星边色数,从而推广已知结果 . 相似文献
17.
引进控制圈的定义,同时讨论了一类2-连通图的控制圈的一个下界,若G是2-连通的非 Hamilton图,含有控制圈C,令R=V(G)-V(C),如果存在v∈V(C),使dR(V)≧2,则G包含的控制圈的长至少为2σ-2. 相似文献
18.
定义在图G的顶点集V(G)上的函数f:V(G)→{0,1,2,3}称为G的双罗马控制函数,如果每个赋值为0的顶点至少与一个赋值为3或两个赋值为2的顶点相邻,并且每个赋值为1的顶点至少与一个赋值为2或3的顶点相邻。图的双罗马控制函数的权为所有顶点的赋值之和。双罗马控制函数的最小权称为双罗马控制数。利用顶点数、围长、周长以及最小度得到了含圈图的双罗马控制数的若干上下界。 相似文献
19.
王震 《哈尔滨商业大学学报(自然科学版)》2023,(2):212-220
设Gσ是定向图,S(Gσ)是其斜邻接矩阵.图Gσ的斜秩sr(Gσ)定义为其斜邻接矩阵的秩.图Gσ的围长,记为g(G),定义为其基础图G中最短圈的长度.刻画了斜秩等于围长的定向双圈图,定向三圈图进而推广至所有定向含圈图. 相似文献
20.
为了进一步探究平面图的injective-染色,通过分析临界图的结构性质并利用权转移方法,证明了围长至少为6,Δ(G)≥9且6-圈与6-圈不交的平面图G,有χi(G)≤Δ(G)+1.所得结果推广了平面图injective-染色的已知结果. 相似文献