色多项式与图的平面性

设图G的色多项式为P（G，λ），α1(G)是P（G，λ）中λ项的系数的绝对值，本文证明了：若1≤α1(G)≤23，则图G是连通的平面图。     

关于色多项式一次系数与简单图特征的若干结论

利用Whitnoy的著名结果：P（G,λ）=∑^n-1i=1(-1)^ibiλ^n=i给出并证明了：①G为连通偶图,当bn-1为奇数;②G为树,当bn-1=1;③分支数为k的图是偶图,当bn-k是奇数且bi=0(n-k 1≤i≤n-1)等八个定理。     

关于两类图的圈唯一性

设 C(G;)是图 G 的圈多项式,如果对任何图 H,C(G;)=C(H;导出 G 同构于 H,则称 G 为圈唯一的。在本文证明了下面的两类图 i)T_(p,r,t ii)P_(p-1)+K_1是圈唯一的。     

一类稠密图色唯一的充要条件

设n≥1,T(1,1,n,4,1)表示从Pn+1的两个端点分别引出两条长为1,1和4,1的路所得到的图.在图G伴随唯一当且仅当-G色唯一的基础上,利用图的特征标、伴随多项式的代数性质及最小实数根的规律,证明了一类稠密图T(1,1,n,4,1)色唯一的充要条件是n≠1,4,7.     

悬挂点数固定的图的Estrada指标

图G的Estrada指标定义为EE(G)=n∑i = 1eλi,其中λ1,λ2,…,λn是图G的邻接矩阵的特征值,主要刻画了悬挂点数固定的一般图中具有最大Estrada指标的唯一图.     

满足一定条件的正则图的k-消去性质

设n和r为偶数,k为奇数,n＞r＞k＞0,λ≥2为整数.G是有n个顶点、边连通度为λ的r-正则图.若λ和n满足下列条件(1)当r≥2k时,r-λk＞0且n＜1十(1+r)k;(2)当r＜2k时,r+λk-λr＞0且n＜1+(1+r)(r-k),则G是k-消去的.     

几乎外平面图的边染色

若图G存在边e使G -e为外平面图 ,则称G为几乎外平面图 .本文证明了 ,连通几乎外平面图G是第二类的当且仅当G是奇圈或Δ(G) =3且G有一个 2 连通子图G′含有唯一的 2 度点 .同时 ,Fiorni关于外平面图边色数的结论得以推广 .     

有约束条件的正则图的k-覆盖性质

n和r为偶数,k为奇数,n>r>k>0,λ≥2为整数.G是有n个顶点、边连通度为λ的r-正则图.若λ和n满足下列条件(1)当r≥2k时,r-λk>0且n<1+(1+r)k;(2)当r<2k时,r+λk-λr>0且n<1+(1+r)(r-k),则G是k-覆盖的.     

有约束条件的正则图的k—覆盖性质

设n和r为偶数,k为奇数,n＞r＞k＞0,λ≥2为整数。G是有n个顶点、边连通度λ的r——正则图。若λ和n满足下列条件：⑴当r≥2k时,r-λk＞0且n＜1 (1 r)k;⑵当r＜2k时,r λk-λr＞0且n＜1 (1 r)(r-k),则G是k——覆盖的。     

H-联图的拟拉普拉斯能量

设图H的顶点集为{1,2,...,k},不交图G1,G2,...,Gk的H-联图(记作G=∨H(G1,G2,...,Gk))是指在Gi(i=1,2,...,k)的基础上,对于H中的任意顶点i、j,若i,j∈E(H),则将Gi的所有点与Gj的每一个点相连所得到的图。特别地,若H=P2,则∨P2(G1∨G2)就是G1与G2的普通联图G1∨G2[4,5]。本文借助H-联图的拉普拉斯谱的性质,刻画了H为完全图以及Gi(i=1,2,...,k)均为n阶图时,∨H(G1,G2,...,Gk)的拟拉普拉斯能量的界。     

图的(g,f)—因子分解

设Ｇ是一个图，ｇ和ｆ是定义在图Ｇ的顶点集上的两个整数值函数，且ｇ≤ｆ．图Ｇ的一个（ｇ，ｆ）—因子是Ｇ的一个支撑子图Ｈ，使对任意ｘ∈Ｖ（Ｈ）有ｇ（ｘ）≤ｄＨ（ｘ）≤ｆ（ｘ）．若图Ｇ的边集能划分为若干个边不相交的（ｇ，ｆ）—因子，则称Ｇ是（ｇ，ｆ）—可因子化的．给出了一个图是（ｇ，ｆ）—可因子化的一个充分条件，改进了有关结果．     

有关某类图色惟一性的注

本文给出文 [1 ]定理 1 8中论证的两类色惟一图H5(j,k ,l)及H6(p ,q)的反例。这两类色惟一图最早出现在文 [2 ]和 [3]中。     

图与它的补图的匹配多项式

指出了图G是匹配唯一的当且仅当它的补图G是匹配唯一的 并给出了一个二分图G与它的完全二分补图G的匹配多项式之间的关系     

梯图的线图的 Tutte唯一性

如果任意与图 G有相同 Tutte多项式的图都同构于图 G,那么,称图 G是满足 Tutte唯一性的,简称为 T-唯一的.本论文研究了梯图的线图的 T-唯一性     

On the ｛P2,P3｝-Factor of Cubic Graphs

Ler G = （ V, E） be a finite simple graph and Pn denote the path of order n. A spanning subgraph F is called a { P2, P3 }-factor of G if each component of F is isomorphic to P2 or P3. With the path-covering method, it is proved that any connected cubic graph with at least 5 vertices has a { P2, P3 }-factor F such that｜P3（F）｜P2（F）｜, where P2（F） and P3（F） denote the set of components of P2 and P3 in F, respectively.     

高度不正则图的全着色

图G的正常k全着色是指用k种颜色对G的点和边着色,使相邻或相关联的元素(点或边)着不同色。其中最小的k称为G的全色数,记为χT(G)。设G是一个简单图,υ是G的任意一个顶点,若与υ相邻的顶点的度互不相同,则称G为高度不正则图。对高度不正则图G,文中证明了χT(G)=Δ(G)+1,同时也给出了着色的算法,其中Δ(G)为G的最大度数且Δ(G)≥ 2。     

边色临界图的1-因子和几乎1-因子的存在性

根据Vizing邻接引理和关于临界图和二分图的3个结论,利用图的1-因子和几乎1-因子存在的充要条件,采用结构图论的方法证明了:1)若G是2n阶临界图,且δ(G)≥n-3,则G存在1-因子;2)若G是2n+1阶临界图,且δ(G)≥n-4,则G存在几乎1-因子.     

双外平面图的全染色

双外平面图是一个平面图，它可以嵌入到平面上并使得它的顶点出现在两个面的边界上。设G是一个双外平面图，V（G），E（G），F（G）分别为双外平面图G的点集，边集和面集。G的全色数XT（G）是使得V（G）UE（G）中的任意两个相邻或相关联的元素间均染不同颜色的最少颜色数。本文证明了对最大度为6的双外平面图，全色数是△（G）＋1，其中△（G）为G的最大度数。