3,4-连通图G中的连通性

引进T-三角形的概念,证明了,对于k(k=3或4)连通图G,若G无T-三角形,则是2连通的,从而改进了N.Dean的结论。另外举例说明了,对于k(k≥5)连通图,此结论是不成立的.     

Harary图的k-偶匹配可扩性

设图G是一简单的且有完美匹配的连通图.称图G是k-偶匹配可扩的,是指G的每一个基数不大于k(1≤k≤(V(G)-2)2)的偶匹配M都可以扩充为G的一个完美匹配.本文主要刻画了Harary图的k-偶匹配可扩性:对于任意的n,如果r(r>4)是偶数,那么Hr,2n是2-偶匹配可扩的等等.     

哈密尔顿性、邻域并和无爪图的平方图

设G是一个图, G的平方图G2满足V(G2)=V(G), E(G2)=E(G)∪{uv: distG(u, v)=2}. 本文利用插点方法, 给出了关于 k或(k 1)连通(k≥2)无爪图G是哈密尔顿的、 1-哈密尔顿的或哈密尔顿连通的统一证明.其充分条件是G中关于∑ki=0N(Yi)与n(Y)的不等式, 这里Y={y0, y1, …, yk} 是图G2的任一独立集, 对于i∈{0, 1, …, k}, Yi={yi, yi-1, …, yi-(b-1)}Y (yj的下标将取模k 1); b 是一个整数, 且0＜b＜k 1; n(Y)={v∈V(G): dist(v, Y)≤2}.     

圈长为3的k圈图laplacian矩阵谱的界

设G为n阶的连通k(k 3)圈图,λ1(G)是图G的laplacian矩阵的最大特征值.本文讨论了圈长为3的k圈图的最大特征值与其顶点数及各顶点的悬挂边个数之间的关系.     

本质集的邻域并和无爪图的哈密尔顿性

设G是一个图 ,G的独立集Y称为本质集 ,如果存在 {y1,y2 } Y ,使得dist(y1,y2 ) =2 .本文利用插点方法 ,给出了关于k或 (k + 1)连通 (k≥ 2 )无爪图G是哈密尔顿的或 1哈密尔顿的统一的证明 .2个结果的充分条件是关于 ∑ki=0N(Yi) 与n(Y)的不等式 ,这里Y是图G的任一本质集 ,对于i∈ { 0 ,1,… ,k} ,Yi={y1,yi- 1,… ,yi- (b- 1) } Y(yj 的下标将取模k + 1) ;b是一个整数 ,且 0 相似文献   

关于△(G)=6的2-连通外平面图的邻点可区别全染色

设G是阶数不小于2的简单连通图,G的k-正常全染色,f称为是邻点可区别的,如果对G的任意相邻的两顶点其点的颜色及关联边的颜色构成的集合不同.这样的k中最小者称为是G的邻点可区别全色数.本文得到了△(G)=6的2-连通外平面图的邻点可区别全色数.     

连通图和不连通图的维纳指数W（G）

一个连通图的维纳指数W(G)等于图中所有无序点对的距离之和。本文研究了连通图和不连通图的维纳指数W(G),得到了上界图;以及研究了W(G) W(G)的上界和下界。     

给定控制数的树的代数连通度

一个图G(V,E)的控制数γ(G)是V的这样一个子集S的最小基数,使得G中每一个顶点或者在S中或者和S中的一些顶点邻接.讨论给定控制数1,2,n/2的树的代数连通度,得出树T*=K1,y-1°K1具有最大的代数连通度;同时利用移接变形刻画出给定控制数2的树中具有最小代数连通度的极图,得出树T=T3(s3,t3)具有最小的代数连通度.     

包含连通度的Hamilton图

设G是一个 2连通简单图 ,具有阶n和连通度k .Bauer等人已证明 :如果对任意三点独立集S =u ,v ,w ,都有d(u) +d(v) +d(w)≥n +k ,则G是Hamilton图 .本文改进了这个结果 .如果一个独立集S中存在距离为 2的 2点 ,则称S是一个 2独立集 .本文证明了如下结果 :如果对任意 3点 2独立集S =u ,v ,w ,都有d(u) +d(v) +d(w)≥n +k .则G是Hamilton图 .这个结果意味我们仅需要检查所有 2独立集是否满足条件     

广义Mycielskian图的超连通性

Mycielski引入了对于图G的一类新的变换图μ（G）,称为G的Mycielskian.这类变换图的推广是广义Mycielskian图μm（G）,m是正整数.如果每个最小点割（最小边割）孤立G的一个点,则称图G是超连通的或超-κ（超边连通的或超-λ）.证明结果显示：设G是连通图且｜V（G）｜≥3条件下,μm（G）是超-κ的充要条件是δ（G）＜（m＋1）κ（G）;μm（G）是超-λ的充要条件是G（≠）K2,即G不是一条边.