两个完全图的匹配和的L(p,q)-标号

设p,q为两个非负整数,一个图G的L(p,q)-标号是一个从G的顶点集V(G)到一个非负整数集的映射f,使得对于G中的任意两个顶点u,v,当d(u,v)=1时,|f(u)-f(v)|≥p;当d(u,v)=2时,|f(u)-f(v)|≥q;根据p,q之间的关系,给出两个顶点数都是n的完全图的匹配和的L(p,q)-标号数的上界.而当q≤p≤2q时,确定了两个顶点数都是n的完全图的匹配和的L(p,q)-标号数的准确值.     

关于双圈图的拟拉普拉斯谱半径的一个猜想的证明

令q(G)表示图G的拟拉普拉斯谱半径.何春阳和郭曙光(2014)研究了不含三圈的n阶双圈图中拟拉普拉斯谱半径的排序问题,他们猜想"若n≥7,则q(G_(10))q(G_9)",其中图G_9和G_(10)如图1所示.若该猜想成立,则其最终可以确定不含三圈的n≥12阶双圈图中排在前12位的拟拉普拉斯谱半径,该文证明了该猜想.     

图的Sum-connectivity指标与其无符号拉普拉斯谱半径

设G=(V,E)为简单连通图.图G的Sum-connectivity指标被定义为■,其中d_u表示顶点u的度.用q(G)表示图G的无符号拉普拉斯谱半径.本文研究了χ(G)与q(G)之间的关系,证明了对于所有顶点数n≥3的简单连通图G,都有■等式成立当且仅当G?S_n.     

边无关数为q的n阶树的谱半径的第三大值

设G为有限无向简单图,G的邻接矩阵的特征值称为G的特征值,G的最大特征值称为G的谱半径．二分图的特征值在量子化学中有意义，因而研究二分图的特征值有重要的实用价值．K1^l,k(k≥l≥1)记星图K1．k的l个悬挂点各接出一条悬挂边所得的图．Tn(q)表示边无关数为q(≥5)的n阶树的集合．(1．1)T(q-3，n-2q 1)∈Tn(q)为K1^q-2,n-q-l的某个2度顶点上接出一条路P2所得的图．给出了Tn(q)中树的谱半径的第三大值。并证明了：当n-2q=1时,取得该值的唯一的树为K1^q，q；当n-2q≥2时，取得该值的树为(1，1)T(q-3,n-2q 1)．     

直径为n-4谱半径第二小的连通图

采用图形变换和比较图的特征项式等方法,按照图的最小谱半径对具有固定直径和顶点数的图类定序,确定了顶点数为n直径为n-4谱半径是第二小的连通图.     

不含三角形的图的独立数和匹配数关系

设α(G),β(G)和n(G)分别表示图G的独立数、匹配数和阶数.图的独立数和匹配数是图的两个较重要的参数.证明了对于不含三角形且最大度不超过5的图,独立数、匹配数和阶数之间存在两个最优的数量关系.     

下整和图的若干结果

定义了下整和图与图的下整和数，给出下整和图的结构性质，并证明完全三部图Km,n,q（m，n，q≥2）的下整和数为2．     

图的最大匹配个数的下界

设G是一个具有n个顶点且最大匹配为k-匹配的连通图,这里n≥2k+1.证明了G至少有n-2k+1个互不相同的最大匹配,并且刻画了恰好具有n-2k+1个最大匹配的图.     

给定匹配数的图的代数连通度的上界

【目的】确定给定匹配数的n个点图的拉普拉斯代数连通度的上界与该上界所对应的极图。【方法】首先，利用图的匹配数与奇连通分支个数的关系与图的变换等方法刻画了给定匹配数的n个点图的拉普拉斯代数连通度上界所对应的极图；其次，利用具有相同邻点集的图与对应特征值的关系得到给定匹配数的n个点图的拉普拉斯代数连通度上界。【结果】借助图与补图的关系以及拉普拉斯特征方程证明得到给定匹配数的n个点图的拉普拉斯代数连通度的上界与该上界所对应的极图是一一对应且唯一确定的，从而同时确定了给定匹配数的n个点图的拉普拉斯代数连通度的上界以及此上界所对应的极图。【结论】用全新的方法同时确定了给定匹配数的n个点图的拉普拉斯代数连通度的上界以及此上界所对应的极图，克服了以往利用图的最小度，最大连通度与代数连通度的关系只刻画了给定匹配数的图中具有最大代数连通度的图类特征，但无法得到此类图的连通度的上界这一弊端。     

Ramsey数和无三角的Cayley图

记Zn={0,1,…,n}为模n的整数加群,Z*n=Zn\{0}.对一个Z*n逆元封闭的子集A,定义Cayley图Gn(A)为:其点集为Zn,而{x,y}是一条边当且仅当|x-y|∈A.计算了这些Cayley图的独立数至n≤258,改进了Ramsey数r(3,q)的的下界,27≤q≤38.     

偶圈的Turán数和Wenger图

设G是一个图,G的Turán数记作ex(n;G),是指阶数为n的不含G作为子图的图的最大边数.根据Erds在1965年给出的偶圈C2m的Turán数ex(n;C2m)的上界10mn1 1/m和Wenger在1991年构造的偶图Hm(q),并由这种图得到的ex(n;C2m)(m=2,3,5)的下界cn1 1/m(其中c为一个与n无关的常数),可以知道,当n→ ∞时,ex(n;C2m)=O(n1 1/m)(m=2,3,5).n1 1/m就是ex(n;C2m)的准确阶.给出了Wenger图Hm(q)的一些一般性质,并分别构造了Hm(q)中长为8的圈(m≥4)和Hm(q)中长为12的圈(m≥6),从而证明了不可能由图Hm(q)得到ex(n;C2m)的所有准确阶.     

偶圈的Turán数和Wenger图

设G是一个图,G的Tur(a)n数记作ex(n;G),是指阶数为n的不含G作为子图的图的最大边数.根据Erd(o)s在1965年给出的偶圈C2m的Tur(a)n数ex(n;C2m)的上界10mn1+1/m和Wenger在1991年构造的偶图Hm(q),并由这种图得到的ex(n;C2m)(m=2,3,5)的下界cn1+1/m(其中c为一个与n无关的常数),可以知道,当n→+∞时,ex(n;C2m)=O(n1+1/m)(m=2,3,5).n1+1/m就是ex(n;C2m)的准确阶.给出了Wenger图Hm(q)的一些一般性质,并分别构造了Hm(q)中长为8的圈(m≥4)和Hm(q)中长为12的圈(m≥6), 从而证明了不可能由图Hm(q)得到ex(n;C2m)的所有准确阶.     

给定独立数的双圈图的最大拟拉普拉斯谱半径

设(B)(n,α)是独立数为α的n阶双圈图,(B)1(n,α)是由(B)(n,α)中含有两个边不交的圈构成的双圈图子集,(B)2(n,α)=(B)(n,α)＼(B)1(n,α).文中分别研究了(B)1(n,α)和(B)2(n,α)中具有最大拟拉普拉斯谱半径的极图.进一步地,得到了(B)(n,α)中拟拉普拉斯谱半径的上界...     

一类双圈图的谱半径

针对双圈图中的一类,研究了其如何变形才能使变形后的谱半径大于变形前的谱半径,并且保证变形前后的匹配数不变。     

L*n,p图的全匹配数

设Kp是p阶完全图。 取Kp的任意r个顶点分别点粘接r颗树,所得到的n阶图集记为L*n,p。 确定了L*n,p中具有最大和最小,第二大和第三大全匹配数的图。     

一类稠密图的匹配唯一性

讨论简单无向图G的匹配唯一性,利用匹配多项式的特征标、最大实数根及其代数性质证明了:当n≥1时,T(1,1,n,4,1)匹配唯一的充要条件是n≠1,4,7,解决了该类图的匹配唯一性.     

偶圈的Tur(a)n数和Wenger图

设G是一个图，G的Turan数记作ex（n；G），是指阶数为n的不含G作为子图的图的最大边数．根据Erdos在1965年给出的偶圈C2m的Turan数ex（n；C2m）的上界10mn^1＋1/m和Wenger在1991年构造的偶图Hm（q），并由这种图得到的ex（n；C2m）（m=2，3，5）的下界cn^1＋1/m（其中c为一个与n无关的常数），可以知道，当n→＋∞时，ex（n；C2m）=O（n^1＋1/m）（m=2，3，5）．n^1＋1/m就是ex（n；C2m）的准确阶．给出了Wenger图Hm（q）的一些一般性质，并分别构造了Hm（q）中长为8的圈（m≥4）和Hm（q）中长为12的圈（m≥6），从而证明了不可能由图Hm（q）得到ex（n；C2m）的所有准确阶．     

给定独立数的树的最大拉普拉斯谱半径

图的拉普拉斯矩阵最大特征值定义为图的拉普拉斯谱半径,它是刻画图结构性质的重要参数。本文主要介绍了在所有给定独立数为α的n阶树中具有最大拉普拉斯谱半径的唯一极图,其中[|n/2|]≤α≤(n-1)。     

一类图匹配唯一的充要条件

利用匹配多项式的特征标和最大实数根的分布规律证明了:当n≥1时,T(1,1,n,5,1)匹配唯一的充要条件是n≠1,2,4,5,8.     

准可扩图的一些性质质

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