导出子图相关论文
本文主要结果分为两个部分,第一部分刻画了所有的第二大特征值不超过1的广义θ-图;第二部分刻画了所有的第二大特征值不超过1的θn,t......
设G是简单图,V(G)={v1,v2,…,vn},A是G的邻接矩阵.G的邻接矩阵A的特征多项式记作χ(G,x)=det(xI-A=|xI-A|,其中I为单位矩阵.A的特征值......
设T是n阶树,在Neumaier给出的树图第二大特征值性质的基础上,通过构造导出子树的结构,刻画了所有λ2(T)≤ √3的树图.......
<正>不含导出子图同构于K_(1,3)或F的图称{K_(1,3),F}-free图.设图G含有无弦的点控制圈(简称VD-圈):C=C_1C_2…C_kC_1,并假定依下......
本文研究了图的Betti亏数与图的顶点划分的导出子图之间的关系,得到了图的最大亏格上界由其顶点划分的导出子图所表达的关系式,由......
n-维立方图是以n-维布尔向量的全体为顶点集, 并且两顶点相领当且仅当其对应的两个n-维布尔向量仅在一个数位上不同.该文对n-维立......
本论文在前人研究的基础上,对第二大特征根不超过1的三圈图进行了刻画,主要内容包括:
·在前两节,我们首先介绍了关于第二大特征......
设G是无孤立点的简单图,令m(G)=max{P|存在A(C)V(G),G[A](≌)Kp}本文给出了m(G)≤3且第二特征值等于(√5-1)/2的图G的结构.......
根据Gyárfás的猜想,即对于一个给定的森林 F ,存在一个整数函数 f (F ,ω(G)),满足对任何一个不含 F作为导出子图的图G ,有χ(G)≤ f (F ,ω(G)),......
一个实矩阵的符号稳定性问题在经济学、生态学等诸多领域中都有应用背景.本文利用[1]中给出的不可约矩阵的符号稳定性的有关结论,......
一个图若不含与K1.3同构的导出子图,则称它为无爪图,本文利用T-插点方法,得到(k+1)-连通无爪图是Hamilton-连通的两个充分条件,(1)设G是(k+1)-连通无爪图(k≥2),若对每个X∈Ik+1(G)有......
设有n个集合X1,X2,…,Xn,一个以X=∪ni=1Xi为顶点集的图G称为一个关于集合序列(X1,X2,…,Xn)的可行图,如果对每一个Xi(i=1,2,…,n)......
设有n个集合X1,X2,…,Xn,一个以X=∪ni=1Xi为顶点集的图G称为是一个关于集合序列(X1,X2,…,Xn) 的可行图,如果对每一个Xi (i=1,2,......
一个图G中所含的三结点连通导出子图的个数记为, 它在网络可靠性中起着重要作用. 在同点数同边数图类中具有最大的图称为3-优图, ......
证明了如果G是3连通无爪图,且G的每个导出子图A、子图T都满足φ(α、α2),则G是泛连通图(当u、v∈V(G),d(u,v)=1时;G中可能不存在(u,v)-k路,k=2......
证明了若G是3连通无爪图,且G的每个同构于A的导出子图都满足φ(a1,a2),则G是泛连通图(除了u,v∈V(G),d(u,v)=1时,G中可能不存在(u,......
对魏暹荪在其所著《图论基础》一书中所给出的2个定理进行了改进,给出了2个更为确切实用的结论.......
图染色是图论中研究热点问题之一,在许多领域都有重要的应用.用χ(G)和φ(G)分别表示连通图G的色数和b-色数.对连通图R,S,称图G不......
对两个给定的图G和H,以G+H表示G和H的联,以G[H]表示G对图H的结合图,证明了如下结果:(1)G+H是Menger图当且仅当G和H均为Menger图;(2......
利用强完美图定理,得到不含{2K2、C4、C5}为导出子图的图是完美图。进而证明了每一个不含{2K2、C4}为导出子图的图是(ω(G)+1)可着色的,......
对任意正整数i,若图G的导出子图L的顶点满足:x,y∈V(L), dL(x,y)=imax{dG(x),dG(y)}≥|G|/2,则称L具有性质DL(i).设C(G)为图G的......
针对现有云计算平台资源随机调配与传统导出子图挖掘效率较低等问题,进一步提升云计算平台中资源整合利用效率与大规模导出子图挖......
本文得到了奇数度循环图C_n<j_1,j_2,…,j_r,n/2>是连通的充要条件及C_n<j_1,j_2,…,j_r,n/2)×K_2(j_r≠n/2)为循环度的充要......
本文证明了:设G是n阶,k(≥3)连通无爪图,且不含同构于B的导出子图,若存在点v0∈V(G),使d(v0)≥n-2k+4则G是Hamilton连通的。......
本文刻画了满足1/3〈λ2(G)〈(√5-1)/2的图G的结构。...
本文所提出关于图谱半径的一个猜想,并对某些特殊情况证明猜想成立....
设G是一个阶为n的图,我们证明了:如果G是2-连通的,并且对G中每个同构于K1,3,P5或P+5的导出图的两个顶点u,v,当dL(u,v)=2时,max{d(u),d(u),d(v)}≥n/2,则G是哈密顿图。这个结果推广了Fan的结论。......
本文证明了:如果G是2连通无爪图且G中不含同构于Z3.D的导出子图.则G是Hamilton图(除G≌G1.G≌G2外)。......
设G是无孤立点的简单图,令m(G)=max{G│存在A=V(G),G「A」≌Kp}。本文给出了m(G)=3且第二特征值等于(√5-1)/2的图G的结构。......
连通图G的一个k-树是指图G的一个最大度至多是k的生成树.对于连通图G来说,其毁裂度定义为r(G)=max{ω(G-X)-|X|-m(G-X)|XV(G),ω(G-X)〉1}其中ω......
证明了下列结果:(1)设G是3连通无爪图,│V(G)│≥6且G的每个导出图A都满足φ(a1,a2)那么对任意u,v∈V(G),若2≤d(u,v)≤5,则对满足d(u,v)≤k≤5的整数k,G中存在(u,v)-k路(2)设G是3连通无爪图,│V(G)│≥......
证明了下述结果:设F是度序列为(1,1,1,3,3,3)的简单图,F中度为1的点记为a1,a2,和a3;G为连通无爪图。若G的每一个与F同构的导出子图均满足性质φ(a1,a2)和φ(a1,a3),或φ(a1,a2)和φ(a1,a3)和φ(a2,a3),则......
G=(V,E)是无向连通图,无环允许有重边.S是V的至少包含两个顶点的子集,S的边连通度λG(S)被定义为使S中的顶点不属于同一连通分支所......
考虑了点赋权图上固定k个顶点的树划分问题.首先证明了点赋树图上固定k个顶点的最小最大树划分问题是NP-难的,然后给出了该问题的一......
本文证明了:如果G是3连通的无爪图且G的每个导出子图A,A都满足ψ(a1,a2)则G是泛连通图(除了当u,v∈(G),d(u,v)=1时,G中可能不存在(u,v)-k路......
根据Gyarfas的猜想,即对于一个给定的森林F,存在一个整数函数f(F,ω(G)),满足对任何一个不含F作为导出子图的图G,有χ(G)≤f(F,ω(......
研究NC≥nδ条件下Cm^n点泛圈图的性质,得到2连通n(n≥)阶图G,若NC≥n-δ,则G是C5^n点泛圈图或Kn/2,n/2,改进Faudree等人的一些结果。......
边数等于顶点个数的连通图称为单圈图.本文修正了文献[1]中关于奇异单圈图的充要条件,并且利用该条件证明了文献[2]中一个关于非奇异......
设G是n阶2-连通图,3≤c≤n.本文给出对于图G的每一个同构于K1,3,或Z1的导出子图L。若d(u)<c/2如果d1(u,w)=2有d(v)=min{c/2,|M^3(u)|/2)......
Gyárfás曾猜想:对于每一个不含森林F作为导出子图的图G,存在整数函数f(F,x)使得χ(G)≤f(F,ω(G)),其中χ(G)和ω(G)分别表示图G的色......
以强完美图定理为基础,通过对不含----HVN(即P3+2K2)和C4为导出子图的图的结构进行分析,得到了该类图色数的关于团数线性函数表达式的......
本文给出了一类大龙虾树为幸福树的构造性证明....
通过对图的奇顶点的导出子图做研究,得到了由奇顶点的导出子图的性质判定图的超欧拉性的方法,即当图的奇顶点的导出子图满足一定性......
设v是图G=(V,E)的顶点,若存在顶点u∈V-{v},使子图G[N(v)∪{u}中任意一对顶点的距离不超过3,则称v是G的弱局部连通顶,点。设G是非平凡的连通无爪图,且它的任一顶点割......