K连通图的k分割多项式算法

图G的K分割问题可描述为:输入(Ⅰ)G=(V,E),G为简单无向图,其中|V|=n,|E|= m;(Ⅱ)a_1,a_2,…,a_k k个G中不同的顶点;(Ⅲ)n_1,n_2,…,n_k k个正整数满足 n_1+n_2+…,+n_k= n.输出(V_1,V_2,…,V_k),对1≤i≤k,满足(Ⅰ)a_i∈V_i;(Ⅱ)G[V_i]是连通图;(Ⅲ)|V_i|=n_i.本文给出时间复杂性为O(knm)通用K连通图的k分割多项式算法.     

判别Hamilton图的一个方法

本文研究寻找Hamilton的圈的一个方法,证明了如下定理:设G是单图,V(G)={V_1,V_2,…,V_n},则G是Hamilton图的充分必要条件是X_(ki)取1或0时,方程组(*)有解,其中sum from i=1 to n sum from j=1 to n x_(ki)x_(k+1)jV_iV_j=1而x(n+1)j=x_(1j) sum from i=1 to n x_(ki)~2=1 sum from i=1 to n x_(ik)~2=1 而V_iV_i=1 当V_i和V_j邻接时, 0 当V_i和V_j不邻接时。     

图的路色数

设G=(V,E)是一个简单图.称V 的一个划分{V_1,V_2,…,V_φ}是一个路着色,如果对任意的i∈{1,2,…,k},〈V_i〉的每个分支都是路.G 的路着色中所需的最少颜色数叫G 的路色数.本文给出了路色数的一个下界;并讨论了两个图的笛卡儿积的路色数,最后,还推广了文[1]的一个定理的结论.     

Corona图P_nｏF_(1,m)、C_nｏC_m与C_nｏF_(1,m)的b-染色数

在图G=(V,E)的一个正常染色{V_1,V_2,…,V_k}中,若i,j,1≤i≠j≤k,■u∈V_i,v∈V_j,使得uv∈E,称该染色为b-染色.令b(G)=max{k|V_1,V_2,…,V_k:i,j,1≤i≠j≤k,■u∈V_i,v∈V_j,uv∈E},称b(G)为图G的b-染色数.一个图G是b-连续的,如果k:χ(G)≤k≤b(G),用k种颜色可实现对G进行b-染色.通过构造特殊染色方案,研究了Corona图P_noF_(1,m)、C_noC_m与CnoF_(1,m)的b-染色数与b-连续性.     

Vertex disjoint cycles in intersection graphs of bases of matroids

The intersection graph of bases of a matroid M=(E, B) is a graph G=G~I(M) with vertex set V(G) and edge set E(G) such that V(G)=B(M) and E(G)={BB′:|B∩B′|≠0, B, B′∈B(M), where the same notation is used for the vertices of G and the bases of M. Suppose that|V(G~I(M))| =n and k_1+k_2+…+k_p=n, where k_i is an integer, i=1, 2,…, p. In this paper, we prove that there is a partition of V(G~I(M)) into p parts V_1 , V_2,…, V_p such that |V_i| =k_i and the subgraph H_i induced by V_i contains a k_i-cycle when k_i ≥3, H_i is isomorphic to K_2 when k_i =2 and H_i is a single point when k_i =1.     

一类OF型图及有关性质

讨论了OF-(-2)型图和OF-(-3)型图的有关性质,得到下列结果:(1)2n阶OF-(-3)型图中含有子图(n—1)K_2;(2)若2n阶OF-(-2)型图G中不存在1—因子,则G具有性质i)V_δ是有n+1个顶点的独立点集,ii)任给w,z∈V_δ,G—{w,z}中存在(n—1)个边不交1—因子,其中V_δ={v∈V(G)|d(v)=δ(G)}.结果(1)部分地改进了J.A.Bondy等人的一个结果。     

K-连通无爪图的最长u-路

本文证明了如下结果:设G是p阶K一连通的无爪图,K>2.G中任意K+1个顶点的独立集{V_1,V_2,…V_(k+1),有又设u∈V(G),为G中最长的u一路,则G[R]中不含(K-2)一路连通子图,从而不含K_(k-1),这里R=V(G)\V(P)。     

图和n维复形的连通剖分

在1977年前后,L.Lovász用组合拓扑方法,E.Gyori用初等方法均证明了下述定理:设G=(V,E)是一个k连通的简单图,v_1,…,v_b ∈V,n_1,…,n_k是k个正整数,其和等于G的顶点数|V|那么就存在G的顶点集V的一个部分使得v_1 ∈V_i,|V_i|=n_i并且每个V_i支撑一个连通子图G[V_i](i=1,…,k)。Gyori对这个定理的证法是论证解的存在性且较复杂。本文把Gyori的证法改写为用一个算法作出的构造性的证明,同时将此定理推广到n维复形上去。     

三角化图的团划分数

在本文,我们证明了下述结果:(1)如果G=(V,E)是72个顶点的三角化图,则K(G)=α(G)≤cc(G)≤cp(G),cc(G)≤n-1,其中图G顶点独立数为α(G),它可在O(|V|+|E|)时间内求出;(2)如果G=(V,E)是n个顶点的特殊三角化图,V=S∪K,具有度序列为n-1≥d_1≥d_2≥…≥d_n,若对于S中任意顶点对x_i,x_j有|Adj(x_i)∩Adj(x_i)|≤1,则α(G)≤cp(G)≤α(G)+δ,其中,m=w(G)是图G的最大团的顶点个数。     

广义奇圈的同构因子分解

广义圈是一个简单图G =(V ,E) ,其中点集V =V0 ∪…∪Vn - 1 ,|V0 | =… |Vn - 1 | ,边集Euν|u∈Vi,ν∈Vi 1 ,i=0 ,…n -1,i 1=mod(n) .证明了广义奇圈可以分解为t个同构因子的充要条件是t可以整除该广义奇圈的边数     

3－W_n图的优美性

证明了在齿轮图ｎ个齿的顶端各加上三条长度为１的边所得的图是优美的，从而对齿轮图的优美性作了推广．     

关于单圈图的路图的Hamilton性问题

用图的三度顶点的收缩方法，刻画了单圈图的路图的Ｈａｍｉｌｔｏｎ性的特征，并具体给出了Ｈａｍｉｌｔｏｎ圈的构造。     

线图求根

给定线图G,如何求得根图H,使G=L(H)?本文就无向图和有向图作出解答.     

广义轮型完全多部图的生成树数

证明了如下结论:设KWk,n是由轮图集W={Wn1,Wn2,…,Wnk}生成的n阶广义轮型完全k-部图,其中n={n1,n2,…,nk},n=|n|=n1+n2+…+nk,1≤k≤n.那么KWk,n的生成树数目为t(KWk,n)=n2k-2∏ki=1αni-1i+βni-1i-2n-ni+1,其中αi=(di+d2i-4)/2,βi=(di-d2i-4)/2,di=n-ni+3.     

关于链路P_n~（2＊）的优美性

定义了链路，探讨了其优美性，同时，得到该链路是交错二分图。     

完全图迭线图的1—因子分解

证明了完全图片K_n的K(≥1)次迭线图L~k(K_n)有1-因子分解当且仅当L~k(K_n)的点数为偶数。     

自补图的平面性讨论

分析探讨了所有自补图的平面性及外可平面性，得出了v≤8的自补因是可平面的；v≤5的自补图是外可平面的。     

一类复合图的niche数上界

研究证明：在一定条件下,两个有限ｎｉｃｈｅ图Ｇ１和Ｇ２的两点粘接图的ｎｉｃｈｅ数ｎ（Ｇ１：Ｇ２（ｕ１＝ｖ１,ｕ２＝ｖ２）≤ｎ（Ｇ１）＋ｎ（Ｇ２）－ｒ,其中ｒ＝０,１,２。     

准补图的紧性和超紧性

推广了补图的概念,找到了另一类紧图和紧超紧图,对于（ｍ,ｋ）圈的准补图是否为紧图或超紧图作了详尽的讨论。