关于齿顶边星图的优美性

在齿轮图.的每个齿的齿顶分别加上 m_1,m_2,…,m_n,条悬挂边后构成的图称为齿顶边星图,记为,(m_1,m_2,…,m_n).本文给出了、(m_1,m_2…,m_n)的优美标号,从而证明了.(m_1,m_2,…,m_n)是优美图;当m_1=m_2=…,m_n=k 时,(k,k,…k)即为 k 顶边星图,于是解决了“所有的 k 顶边星图都是优美图”这一猜想.     

图的Laplacian谱半径界的可达性

设G为n阶连通的简单图 ,ρ(G)为图G的邻接谱半径 ,μ(G)表示G的Laplacian谱半径。(d1,d2 ,… ,dn) (其中d1≥d2 ≥…≥dn)为G的顶点度序列 ,令r=max{d(u) +d(v) ｜ (u ,v) ∈E(G) } =d(x) +d(y) ,s=max{d(u) +d(v)｜ (u ,v) ∈E(G) - (x ,y) }。该文证明了μ(G)上下界的可达性 :μ(G) =μ≤ 2 + ρ(LG) ,等式成立当且仅当G是偶图。μ(G)≤ 2 + (r- 2 ) (s- 2 ) ,成立等式当且仅当G为半正则偶图或P4 。μ(G)≥d1+ 1,成立等式当且仅当d1=n- 1。     

正则图的第二大特征值的分布

研究了当G是连通正则图时 ,其第二大特征值在区间 [0 ,1)上的分布情况。结果表明 ,若G为连通正则图 ,则λ2 (G) <1,当且仅当G为完全等l部图Kp ,p ,… ,p(lp =n)或G =G1 G2 … Gl,其中 Gi 为奇圈 ,1≤i≤l。     

图的谱半径的一些下界

利用矩阵的相似变换,研究了简单连通图的谱半径的可达下界,得到一个新的下界ρ(G)≥δ1+t-s+√(s+t-δ1)2+4s(δ2-t)/(2),等号成立当且仅当G(～)/(=)G1(～)/▽G2,其中G1为n-I阶(δ1-s)-正则图,G2为I阶t-正则图.     

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

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

具有二分划(A1,A2)的2－连通偶图为(A1,A2)Hamilton连通的一个充分条件

给出具有二分划 (A1,A2 )的n阶 2连通偶图G(A1,A2 )为 (A1,A2 )Hamilton连通的定义 ,其中 |A1|=|A2 |·采用反证法 ,将图G分为若干情形 ,利用图G是 2连通的偶图 ,及 |A1|=|A2 |,证明了 ,若n≤ 2δ +2δ - 2时 ,则G是 (A1,A2 )Hamilton连通图 ,其中δ =min{d(x) |x∈V(G) } ,δ =min{max(d(x) ,d(y) ) |d(x ,y) =2 ,x ,y∈V(G) }·     

HAMILTON图的特征矩阵

讨论了Hamilton图G和它的邻接矩阵A之间的关系，得到如下结果定理1：图G是H－图当且仅当A＝B＋Q，这里B≥0且B≠0，Q＝PCP，C是由互换单矩阵中的第1行和第n行所得到的初等阵，P是置换阵，P是P的转置矩阵，定理：图G是H－图当且仅当A的谱半径ρ（A）是A的单根，且存在正特征向量ξ，使得Aξ＝ρ（A）ξ＞η，这里η是适当调整ξ的分量而得到的向量，满足：当ξ的第i个分量调为η的第j个分量时，A的（i,j)元aij=1.     

^—αKaUβKb,b类整图

设图G是一个简单图,图G的补图记为G.如果G的谱完全由整数组成,就称G是整谱图.讨论了当u1=a+b且a-1>b时,aKa U(3B+2)Kb,b不是整谱图;当u1=a+b且a≤b时,aKa UBKb,b(a=1,B=1,a=3或2,b=6)是整谱图.     

1-可扩偶图的刻划

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

关于图的全荫度和列表全荫度的一些结果

图G的全图T(G)是以V(G)∪E(G)为顶点集的一个图,其中两个顶点相邻当且仅当它们在图G中对应的元素是相邻或关联的.图G的全荫度ρ"(G)是将其全图的顶点集V(T(G))划分为最少的子集数,使得每个子集在全图中的导出子图是一个森林.列表全荫度硝(G)是全荫度概念的列表染色的版本.本文证明了:(1)对完全图‰,ρ"(Kn)=「(n+1)/2];(2)对完全二部图Kn,n,ρ"(Kn,n)=「(n+2)/2];(3)对Halin图G,ρl"(G)≤「(△(G)+2)/2].     

正则图的第二大特征值的分布

研究了当G是连通正则图时,其第二大特征值在区间[0,1)上的分布情况,结果表明,若G莱连通正则图,则λ2（G)＜1,当且仅当G为完全等l部图Kp,p,…,p（lp=n）或G＝G1△↓G2△↓…△↓,其中G^-i为奇图,1≤i≤l.     

1-可扩偶图的刻划(英文)

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

具有二分划(A_1;A_2)的2-连通偶图为(A_1;A_2)Hamilton连通的一个充分条件

给出具有二分划(A1,A2)的n阶2连通偶图G(A1,A2)为(A1,A2)Hamilton连通的定义,其中|A1|=|A2|·采用反证法,将图G分为若干情形,利用图G是2连通的偶图,及|A1|=|A2|,证明了,若n≤2δ+2δ-2时,则G是(A1,A2)Hamilton连通图,其中δ=min{d(x)|x∈V(G)},δ=min{max(d(x),d(y))|d(x,y)=2,x,y∈V(G)}·     

图的第二个最小特征值的界

设 G 是 n 个顶点的简单图,λ_(n-1)(G)为 G 的第二个最小特征值。G 的非孤立点形成的图记为 G_1,V(G_1)=s,(3≤s≤n)。本文主要证明了:a.若 G_1不是完全偶图,则λ_(n-1)(G)≤λ_(s-1)(K_(2,s-2)-(?)),等式成立(?)G_1(?)K_(2,s-2)-e。其中图 K_(2,s-2)-e 为完全偶图 K_(2,s-2)去掉一边 e而得到的图 b.若 G_1既不是完全偶图.又不是 K_(2,s-2)-e,则λ_(n-1)(G)<-2~(1/2)/2。     

无爪图的泛连通性

证明了如果G是 3连通无爪图 ,且G的每个导出子图A、子图T都满足(a1,a2 ) ,则G是泛连通图 (当u、v∈V(G) ,d (u ,v) =1时 ;G中可能不存在 (u ,v) -k路 ,k =2 ,3,4除外 )。     

单圈图谱的界

设G是有n个点的连通单圈图(即恰含一个圈的连通图)。λ_1(G)是G的最大特征值。G_n是n个点的圈。S_n~3是由星图K_(1,n-1)连接它的两个度为1的点而得到的图,则下列不等式成立λ_1(C_n)=2≤λ_1(G)≤λ_1(S_n~3)左边等号成立,当且仅当G≌D_n。右边等号成立,当且仅当G≌S_n~3。     

关于链路P_n(m_1,m_2,…,m_(n-2))的k-优美性

图G的标号是指G的顶点集到一个整数集的映射g,且对e=uv∈E(G)由g(u)和g(v)诱导出边e的标号.本文给出了链路P_n(m_1,m_2,…,m_(n-2))的k-优美标号.即证明了图P_n(m_1,m_2,…,m_(n-2))是k-优美图.进而推广了原有的一些结果.     

单圈图谱的界

设G是有n个点的连通单圈图(即恰含一个圈的连通图)。λ_1(G)是G的最大特征值。C_n是n个点的圈。S_n~3是由星图K_(1,n-1)连接它的两个度为1的点而得到的图,则下列不等式成立左边等号成立,当且仅当G■C_n。右边等号成立,当且仅当G■S_n~3。     

路并的匹配等价图数

两个图G和H的匹配多项式相等,则称它们匹配等价.用δ(G)表示图G的所有不同构的匹配等价图的个数.计算了一些路的并图的匹配等价图的个数.首先将整数m(≥2)按它所含的最大奇因数分成3-系和2k(k=1.2,…)-系,再按它所含2的方幂分为级.设A是不小于2的整数组成的可重集,B_i(i=1,2,…,t)是同系整数构成的可重集,且A=B_1∪B_2∪…∪B_t,则δ(■P_i)=■δ(■P_i),若x∈B_i,y∈B_j(i≠j),则x与y是互不相同系的整数.设B={m_1~(k_1),m_2~(k_2),…,m_n~(k_n)}是同系整数构成的可重集,其中m_i(≥2)是第i级的,有k_i(≥0)个,则n =1,δ(■P_i)=1;n≥2,δ(■P_i)=sum from i_m-0 to k_n sum from i_(m-1)-0 to k_(n-1) i_m…sum from i_2-0 to k_2 i_3 1.作为推论,计算了路并补图的匹配等价图的个数.     

n阶单圈图的边平均Wiener指标

对于n阶单圈图的边平均Wiener指标,证明了当n≥6时,W’e(G)≤112(2n3-32n+69),等号成立当且仅当G≌C3(Pn-2);W’e(G)≥14(2n2-9),等号成立当且仅当G≌C3(Sn-2)。