关于一类立方图的可圈性研究

设G为无向图,如果对G的每一个定向D,都存在S（D）包含V（G）使在D中改变所有恰与S（D）中一个顶点相关联的弧的方向后所得的图为有向哈密尔顿图,则称G为可圈图．Klostermeyer和Soltes证明了P4k^3（k≥1）是不可圈图,现证明对任意整数n≥3,Pn^3是可圈图当且仅当n为奇数．     

棒棒糖图的Merrifield-Simmons和Hosoya指数

i（G）表示图G的Merrifield-Simmons指数,定义为图G的独立点集个数;z（G）表示图G的Hosoya指数,m（G,k）表示G的k-匹配数,则z（G）是所有的m（G,k）的总和（1≤k≤[n/2]）,其中n是G的顶点数．给出n阶棒棒糖图Ln．k的Merrifield-Simmons指数和Hosoya指数以及它关Merrifield—Simmons指数和Hosoya指数的一个排序．     

关于恒等式e^x=∑n≥0LnJn（2x）的证明

关于恒等式e^x=∑n≥0LnJn（2x）已有组合证明，本文将用微积分的方法证明该恒等式，其中L0=1,L1=1,L2=3,Ln＋1=Ln＋Ln-1（n≥2）,Jn（2x）=∑k≥0（-1）^kx^n＋2k/k!（n＋k）!.     

立方图的可圈性

图的可圈性是哈密尔顿性的一个推广.设G是有向图,如果对G的每一个定向D,都存在S(D) V(G)使在D中改变所有恰与S(D)中一个顶点相关联的弧的方向后所得到的图为有向哈密尔顿图,则称G为可圈图.证明至少含5个顶点的连通图G的立方图是可圈图当且仅当G不同构于任何一条偶路.该结果改进了Klostermeyer的3个定理.     

无哈密尔顿路图的某些图

图G的路图P_k(G)是依下述方法得出的图:以G中的有k个顶点的路P_k作为顶点,且两个顶点相邻当且仅当对应的P_k的并是G中的路P_(k-1)或圈C_k。本文给出了下列结论:1)不存在最大度大于3且具有哈密尔顿P_(3-)图的树;2)不存在最大度大于3且具有哈密尔顿P_(3-)图的单圈图;3)给出了最大度为4且有哈密尔顿P_(3-)图的单圈圉的特征,因而证明了由H.J.Broersma和C.Hoede提出的两个猜测。     

哈密顿线图的一个充分条件

本文得到如下结果:设G是几乎无桥P≥2阶简单连通图,且G(?)K_(1,p-1),若对任意相距为1的两边e_0和e_1,d(e_0) d(e_1)≥2P-5,则G有一个D一闭迹,从而G的线图L(G)是哈密尔顿的。     

一类三角系统的匹配数与点独立集数

给出了一类三角系统的匹配数和点独立集数的一种计算方法和计算公式,证明了：定理1（a）μ（Ln）=（μLn-1）＋μ（Ln-2）＋μ（Ln-3）＋μ（Ln-4）;（b）σ（Ln）=σ（Ln-1）＋σ（Ln-3）.定理2 设ri（i=1,2,3,4）为非负整数,则（a）μ（Ln）=2∑r1＋2r2＋3r3＋4r4=n（r1＋r2＋r3＋r4）!/r1!r2!r3!r4!＋2∑r1＋2r2＋3r3＋4r4=n-1（r1＋r2＋r3＋r4）!/r1!r2!r3!r4!＋2∑r1＋2r2＋3r3＋4r4=n-2（r1＋r2＋r3＋r4）!/r1!r2!r3!r4!＋2∑r1＋2r2＋3r3＋4r4=n-3（r1＋r2＋r3＋r4）!/r1!r2!r3!r4!;定理3设r1,r2为非负整数,n（n≥4）为偶数,则（a）m（Ln）=m（Ln-2）＋m（Ln-4）;（b）m（Ln）=∑2r1＋4r2=n（r1＋r2）!/r1!r2!＋∑2r1＋4r2=n-2（r1＋r2）!/r1!r2!.     

哈密尔顿性和部分平方图的独立集

设G是一个图,G的部分平方图G^＊满足V（G^＊）=V（G）,E（G^＊）=E（G）∪{uv：uv∈E（G）,且J（u,v）≠φ},这里J（u,v）={w∈N（u）∩N（v）,N（w）（∈）N[u]∪N[v]}.本文利用插点方法,给出了关于k,或（k＋1）-连通（k≥2）图G是哈密尔顿的,1-哈密尔顿的或哈密尔顿连通的统一证明.其充分条件是在图G中关于^k∑i=1｜N（Yi）｜＋b｜N（y0）｜与n（Y）的不等式,这里Y是图G的部分平方图G^＊的任一独立集,对于i∈{1,2,…,k},Yi={yi,yi-1,…,yi-（b-1）}（∈ ）Y（yj的下标将取模k）;b是一个整数,且0＜b＜k＋1;n（Y）=｜{v∈V（G）,dist（v,Y）≤2}｜.     

哈密顿图的邻域交和邻域并条件

记δ和α分别为图G=（V,E）的最小度和独立数,1991年Faudree等人和尹家洪分别得到：“若2连通n阶图G的不相邻的任意两点x、y均有｜N（x）∪N（y）｜≥n-δ,则G是哈密尔顿图”和“若2连通n阶图G的长为2的任意两点x、y均有｜N（x）∪N（y）｜≥n-δ,则G是哈密尔顿图”。这里得到结果：若2连通n阶图G的满足1≤｜N（x）∩N（y）｜≤α-1的不相邻的任两点x、y均有｜N（x）∪N（y）｜≥n-δ,则G是哈密尔顿图。此结果推广Faudree等人和尹家洪的结果。     

Fibonacci数列和Lucas数列的卷积

设Fn表示Fibonacc／数列．Fn=Fn-1＋Fn-2,F1=F2=1,Ln表示Lucas数列,Ln=Ln-1＋Ln-2,本文给出了F-L数列的卷积表达式∑k=0nFkLn-k和∑k=0n（-1）^kFkLn-k.     

哈密尔顿图的局部化临域并条件

采用图的局部化临域并条件 ,本文证明了下述结果 :设G是一个p阶 2 -连通图 ,Li- 相似文献   

一类哈密顿图的控制数的上界

设G=(V,E)是一个简单图,D是V的一个子集,如果集合V-D的任意点都与D中的点相邻,则称D为图G的一个控制集.图G的最小控制集中的点数称为G的控制数.本文对哈密顿图的控制数进行了研究,证明了命题:如果n阶图G是一个最小度为5的哈密顿图,则图G的控制数就不大于5n/14.     

图的代数连通度及其点连通度

G是一个简单图.a(G),k(G)分别为G的代数连通度和点连通度,该文刻画了满足a(G)=k(G)的图.G=(V,E)是一个n阶简单图,点连通度为k(G)≤[n/2].H是G的任意最小点割集,则a(G)=k(G)当且仅当对任意u∈H和v∈V\H,有uv∈E.     

正则图的代数连通度

设G=(V,E)是一个具有n个顶点的简单图,A(G)是G的邻接矩阵,D(G)表示G的度对角矩阵,图G的拉普拉斯矩阵定义为L(G)=D(G)-A(G).若矩阵L(G)的特征值为μ1≥μ2≥…≥μn-1≥μn=0,则称μn-1为G的代数连通度.研究了正则图的代数连通度,得到了下列结论:μn-1≤(nrln(n-l))/(6n-8-4r-nln(n-1))这里,r表示正则图的度.     

舵轮图都是强协调图

一个有e条边的简单图G称为是强协调的,若有V(G)到{0,1,…,e-1}的单射h,使导出映射h~*:h~*(uv)=h(u)+h(v)是由E(G)到{1,2,…,e}的一个双射。舵轮图H_n是由含n个顶点的圈C_n内添加一个与C_n的每个顶点都相邻的顶点,且再在C_n的每个顶点上都添上一条悬挂边而得到的图。本文中证明了,所有舵轮图都是强协调图,因而回答了[2]中一个open问题。     

具有给定稳定数和连通性的极值图

如果n阶图G的稳定数为a，连通数为k，则称之为一个（n,a,k)图，chvatal和Edos证明如果a≤k，则G是一个哈密尔顿图，如果a-1≥k≥2，图G多大才能保证存在一个哈密尔顿圈？本文回答了这个问题，进一步特征化极大数目的边的图，即给出了极图（n,a,k)的特征。     

4元n方体的匹配图的若干性质

一个图G的匹配图M(G)的顶点集是G的所有完美匹配的集合,两个顶点相邻当且仅当对应的两个完善匹配的并构成G的一个Hamilton圈.文章给出了4元n方体Qn4的匹配图M(Qn4)的一些性质.     

关于近似二部图边覆盖染色的一个充分条件

设G是一个简单图，其顶点集为V(G) 而边集为E(G) . S∈E(G)称为G 的一个边覆盖，如果由S 导出的子图是G 的一个生成子图. G 的边覆盖色数χ’c(G) 是E(G) 所能划分成的最大边覆盖数. 已知 δ-1≤χ’c(G)≤δ ，由此将 χ’c(G)=δ的图称为CⅠ类图，否则称为CⅡ类图. 显然，图的边覆盖染色分类问题是NP-完全的. 给出了近似二部图是CⅠ类图的一个充分条件，而且该条件中的下界是最好的。     

两类图的边色数

设G是连通循环图.本文讨论两个与循环图有关的图类的边着色问题,得到了下列结论:①如G是奇素数幂阶循环图,则对G的任意点v,G-v是第一类的;②如G是奇数阶循环图,则G的线图L(G)是1-可因子化的,当且仅当G的边数为偶数。     

几类特殊图的一般指标集

令G=(V(G),E(G))为一简单连通图,V(G)和E(G)分别是图G的顶点集和边集.一个顶点标号函数f:V(G)→Z2诱导出一个边标号函数f*:E(G)→Z2,其中?v1 v2∈E(G),有f*(v1v2)=f(v1)+f(v2).当标1和标0的顶点数相差m(m<|V(G)|)时,标号为1和0的边数差的集合称为图G...