1-可扩偶图的刻划

设G是一个具有二分类(X，Y)的偶图且M是G的一个完美对集。文章证明：G是1—可扩图当且仅当G有如下耳朵分解G=e P1 P2 … Pr使得e∈M并且每个只是起始和终止边都在E(G)＼M中的M-交错路。文章还给出一个有效算法判定一个偶图是否1—可扩图并找出该图的耳朵分解。     

蛛网图的偶匹配可扩性(英文)

图G的匹配M是偶匹配,如果G[V(M)]是偶图.图G是k-偶匹配可扩的(1≤k≤(V(G)-2)/2),如果G的每一个基数不大于k的偶匹配都可以扩充为G的一个完美匹配.研究蛛网图的偶匹配可扩性得出的结论是:蛛网图不具有偶匹配可扩性和2-偶匹配可扩性.     

循环图C_(2n)(1,3)的2-偶匹配可扩性

设图G是一简单的且有完美匹配的连通图,称图G是k-偶匹配可扩的,是指G的每一个基数不大于k(1≤k≤(│V(G)│-2)/2)的偶匹配M都可以扩充为G的一个完美匹配.刻画了循环图C2(n1,3)的2-偶匹配可扩性,得到结论:对于任意的n(n≥3),C2(n1,3)是2-偶匹配可扩性的.     

循环图C_(2n)(1,4)的偶匹配可扩性

称图G是偶匹配可扩的,是指G的每一个偶匹配M都可以扩充为G的一个完美匹配.判定图是否是偶匹配可扩的是co-NP-完全问题,根据图的k-偶匹配可扩性完全刻画了循环图C2n(1,4)的偶匹配可扩性.     

Cn×P2的2-偶匹配可扩性

称图G的匹配M是偶匹配,如果M中的边关联的点集在G中的导出子图是偶图,即G[V（M）]是偶图称图G是偶匹配可扩的,如果G的每一个偶匹配M都包含在G的一个完美匹配中为了进一步地研究图的偶匹配可扩性,我们考虑图G的偶匹配数,即图G中最大偶匹配所含的边数,记为BM（G）,我们证明了Cn×P2是2-偶匹配可扩的。     

分数n-可扩图的若干结果

如果图G中有n-匹配并且对任意一个n-匹配M，G中都有一个分数完美匹配f使得对于任意e∈M，f（e）=1成立，那么G被称为是分数n-可扩图．马英红等首先引出此概念，并给出分数n-可扩图和极大分数n-可扩图的刻画．本文分别刻画了分数n-可扩二部图和极小分数n-可扩图，研究了k-因子临界图和分数n-可扩图之间的关系并利用图的binding数和最小度给出了分数n-可扩图的两个充分条件．     

准可扩图的一些性质质

设 G是一个有限的简单连通图及其具有一个最大匹配 M*。 G称为是 n-可扩的 (1≤ n≤ |M*|- 1)如果 G的任一基数为 n的匹配都能扩充到 G的一个最大匹配 .特别地 ,当 G没有完美匹配时 ,我们把 G称为 n-准可扩的 .在这篇文章里 ,我们研究了 n-准可扩图的一些性质     

偶图与多重完全图谱半径的界

G为连通简单图,A是G的邻接矩阵,ρ(A)是A的谱半径。当G为偶图时,ρ(A)≤e~(1/2)(e是G中边的个数),等号成立当且仪当G为完全偶图;当G为完全多重图即G=K_(m_1,m_2,…,m_n)时,等号成立当且仅当m_1=m_2=…=m_n。     

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

利用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)等八个定理     

直径为2的无爪图的导出匹配可扩性

研究直径为2的无爪图的导出匹配可扩性,得出结论:直径为2的无爪图G是导出匹配可扩的,当且仅当对图G的任意的导出匹配M,|M|≤3,G-V(M)没有奇分支,从而,直径为2的无爪图的导出匹配可扩性是多项式时间可解的.     

3－W_n图的优美性

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

关于Km，n并图的优美性

对于自然数k，m，n，本文给出一类非连通图↑k∪↓i=1Kmi.ni；通过构造标号函数的方法，证明了当max{mi，ni}≥3，min{mi，ni}≥2(i=1，2，…，k)时这类图既是优美图，也是交错图；从而给出构造一类任意个图的并图是优美图的一种方法，拓宽了优美图及其应用的道路。     

图U∧C_(4,m_i)from i=1 to n的优美性

优美图是图论中的一个重要分支,至今对非连通优美性的研究并不多,特别是对n个图的并图的优美性研究就更少.本文证明了一类任意n个二分图∧C4,m的并图4,1inmiC=U∧是优美图,且是交错图.     

再论图Pn^3的优美性

给出图Pn3的另一种优美标号,证明其图是优美图且是交错图.另外指出文献[1]中的一个错误和给出了相应正确的结果,同时证明了严谦泰,张忠辅给出的标号以及我们改正的标号都是交错的.     

Hamilton图的代数刻划

运用矩阵方法,给出了连通图是Ｈａｍｉｌｔｏｎ图的一个代数刻划     

任意n个完备二分图的并图的优美性

优美图是图论中的一个重要分支,至今对非连通优美性的研究并不多,特别是对n个图的并图的优美性研究就更少.本文证明了任意n个完备二分图的并图是优美图,且是交错图.     

一类串图的优美性

给出了一些图的优美标号,特别给出了串图ωm1,m2,mn,mn＋1当m1,m2,…,mn≡0（mod4）,mn＋1≡3（mod4）的优美标号,以及串图ωm1,m2,,m2n当mi≡2（mod4）（i=1,2,…,2n）,m2k-1＜m2k,（k=1,2,…,n）时的优美标号.     

图∪ from i=1 to n(F_(mi,4))的优美性

给出图∪ni=1Fmi,4 的一类非连通图 ,并证明这类图是优美图 ,且也是交错图 .     

几类7点7边图的图设计与最优填充

设λKv是λ重ν点完全图，G是无孤立点的有限简单图。将G－设计（G－填充）记作（ν，G，λ）－GD（（ν，G，λ）－PD）是指一个序偶（X，B），其中X是完全图Kν的顶点集，B是Kν中间构于G的子图（区组）的集合，使得Kν中每条边恰好（至多）出现在B的λ个区组中。讨论了3类7点7边图Gi(i=1,2,3)的图设计及最优填充问题，并给出了（ν，Gi,1)-GD及（ν，Gi,1)-OPD(i=1,2,3)存在的谱。     

图C4∪St(m)的k优美性及算术性

给出一类非连通图C4∪St(m). 论证当k>1(k∈N)时, 该图是k优美图; 当k>d+1(d>1, d∈N)时, 图C4∪St(m)是(k,d)算术图.