关于Alavi猜想的一个结果

Alavi在[1]中提出了图的升分解问题,并猜想:设G是星S_1,S_2,…,S_k的并图,S_1含有a_i条边,n≤a_i≤2n-2, sum from i=1 to k(ai)=((n+1)/2),则G可升分解为星图的并,本文证明了当a_i≥n,且a_(i-1)-a_i=d(d≤5,1≤i≤k-1)时,猜想的结论成立,它可作为[2]的扩展。     

笛卡儿积图P2n×Pm与P2n×Cm的gnd-染色

设简单图G和图H的顶点集分别为V(G)={u1,u2,…,um}和V(H)={v1,v2,…,vn}.所谓G和H的Cartesian积G×H是指这样的一个图,其顶点集和边集分别为V(G×H)={wij|i=1,2,…,m,j=1,2,…,n},E(G×H)={wijwrs|i=r,vjvs∈E(H)或j=s,uiur∈E(G)}.文章讨论了笛卡儿积图P2n×Pm和P2n×Cm的gnd-染色,并给出了相应色数.     

图R(5,1,m,n)的伴随多项式的整除性质

本文仅考虑简单图,所用术语和记号来自文献(1)。设图 G 的生成子图 M 的每个分支都是完全图,则称 M 是 G 的理想子图。用 b(G)表示图 G 的具有 i 个分支的理想子图的个数,则有定:设 G 是 n 阶图,多项式 h(G,x)=N(G,K)x~K     

Hamilton图的一个注记(英文)

n阶图G是Hamilton的,当且仅当其邻接阵A的行列式中含有形如a_(i1i2)a_(i2i3)…a_(inil)的非零项。且,G中Hamilton圈的个数恰好是detA中形如(1)的非零项的项数的一半。     

分数ID-消去图的邻域并条件

若删除G中任意一个独立集后得到的图依然是分数（g,f,m）-消去图,则称G为分数ID-（g,f,m）-消去图．将若干个关于分数消去图邻域并条件的结论推广到分数ID-消去图,证明了如下两个结论：1）阶为n的图G满足n≥12k＋6m-11,6（G）≥n/3＋k＋m,且／NG（x）UG（y）/≥2n/3对G中任意一对不相邻的顶点x,y都成立,则G是分数ID-（k,m）-消去图;2）若δ（G）≥（an/2a＋b）＋（b2（i-1）/a＋2m,n〉（（2a＋b）[i（a＋b）＋2m-2]）/a,且/NG（x1）u…uNG（x1）/≥（a＋b）n/2a＋b,对V（G）的所有独立集{x1,……,xi}都成立．则G是分数ID-（g,f,m）-消去图．     

图的谱半径的下界

设G=（V,E）是n阶简单图,di是图G的顶点vi（i=1,2,……,n）的度且d1≥d2≥…≥dn,Ni是图G的顶点vi的一个邻集,λ1是图G的邻接谱半径．本文证明了λ1≥√d1,等号成立当且仅当图G同构于K1,n-1。最后证明了当v1v2≠E时,λ1≥√d2＋｜N1∩N2;当v1v2∈E时,λ1≥√d2-1＋｜N1∩N2｜.     

Estrada指数的极小树

设G为一个n阶图,G的邻接矩阵A(G)的特征值为λ1,λ2,…,λn,Estrada指数被定义为EE(G)=Σni=1eλi。该文确定了如下树类中Estrada指数的极小图,此类中的树均有n个顶点且恰好包含有两个最大度为△的顶点。进一步提出了一个关于如下树类中Estrada指数的极小图的猜想,此类中的树均有n个顶点且恰好包含有k个最大度为△的顶点。     

几类图的无符号Laplace矩阵的行列式

我们知道n个顶点的图G的无符号Laplace特征多项式为σ(G;λ)=det(λIn-Q(G))=n i =0移(-1)ibiλn-i, Cvetkovic等[6]给出了其系数bi的组合解释.我们发现det(Q(G))的值恰好是常数项系数bn.于是可以根据bn的组合解释来讨论图G的无符号Laplace矩阵的行列式.本文主要研究n个顶点的树、连通单圈图与连通双圈图的无符号Laplace矩阵的行列式的计算问题,给出了计算这些图类的无符号Laplace矩阵的行列式的一般方法,对研究图的无符号Laplace矩阵的行列式有着重要的意义.     

一个五阶图与n个孤立点及路的联图的交叉数

摘要：目前已经确定的两个图的联图的交叉数结果比较少,为此讨论了五阶图G18分别与nK1,Pn的联图的交叉数,得到了cr（G18＋nK1）=Z（5,n）＋n＋[n/2],n≥i;cr（G18＋Pn）=Z（5,n）＋n＋[n＋2,n≥2．其中nK1是n个孤立点构成的图,只是Pn个点的路．     

三度循环图的判别

我们知道,即使正则图也可能不是循环图。因此,如何判定一个正则图为循环图就成为研究循环图的一个课题。本文给出了三度正则图是否为循环图的一个判别法,同时也给出了将三度连通循环图的邻接矩阵变换为循环阵的方法。定义1,图 G 是三度连通的循环图,如果它的邻接矩阵(a_(ij))_(n×n)为循环阵,第一行中除a_(1,i)=a_(1,n 2-i)=a_(1,n/2 1)=1外,其它元素均为零,且(n,i-1)~*=1(或2),则称图 G 为三度Ⅰ(或Ⅱ)型循环图。     

自补图和自补循环图的几个性质

利用自补置换的性质,得到4n阶自补图G包含4个点互不相交的子图Gi,i=1,2,3,4,满足：G1≌G3,G2≌G4,且G1≌G2。给出了自补图为过溢图的一个充要条件,对正则自补图和自补循环图的图类进行了讨论。     

2-连通半无爪图的Hamilton性质

满足对于任意x,y∈V(G),并且d(x,y)=2,存在点u∈N(x)∩N(y),使得N[u](∈)N[x]UN[y]的图称为半无爪图.半无爪图是包含无爪图的更大的图类.将2-连通无爪图的结果:若G是2-连通的无爪图,其阶为n,则当n≤3δ 2时,G是Hamilton图,推广至半无爪图时也成立.     

一类G与G相交于一点的图的特征值

图G的特征值是图的一个重要不变量。在量子化学和理论化学中有大量的应用。当图G的顶点数较大时,其邻接矩阵的阶数较大,计算特征值较困难。分块降阶是通常的方法。本文针对一些特殊图的邻接矩阵进行分块降阶求特征值。如果在V(G)上有一个一一映射φ,使得φ(vi)=vn-i 1,i=1,2,…,n,那么G的点v1仅与G的点v1重合的图G G的特征值中有G-V1的特征值。     

随机图的Grundy数

图G=（V,E）的首先适应着色数是在贪婪着色中最坏情形所需要的颜色数,记为xFF（G）。也称之为Grundy数,其等价定义为：V的有序拆分V1,V2,…,Vk的最大分类数为k,其中Vi为独立集且对每个1≤i〈j≤k及x∈Vj存在-y∈Vi使得x和y相连。文章证明了在稀疏随机图中,可以很高的概率满足（1-ε）n/logbnp≤xFF（G（n,P））≤（1＋ε）n/logbnp。其中事件A以很高的概率成立是指对于任意当n→∞时,P（A发生）→1。     

哈密尔顿性、邻域并和无爪图的平方图

设G是一个图, G的平方图G2满足V(G2)=V(G), E(G2)=E(G)∪{uv: distG(u, v)=2}. 本文利用插点方法, 给出了关于 k或(k 1)连通(k≥2)无爪图G是哈密尔顿的、 1-哈密尔顿的或哈密尔顿连通的统一证明.其充分条件是G中关于∑ki=0N(Yi)与n(Y)的不等式, 这里Y={y0, y1, …, yk} 是图G2的任一独立集, 对于i∈{0, 1, …, k}, Yi={yi, yi-1, …, yi-(b-1)}Y (yj的下标将取模k 1); b 是一个整数, 且0＜b＜k 1; n(Y)={v∈V(G): dist(v, Y)≤2}.     

点泛圈偶图的一个充分条件

设G是连通偶图，（X1，X2）是其顶点的二分类，|X1|=|X2|=n，δ（G）≥t≥3。证明了若任意u,v∈Xi蕴含|N(u)∪N(v)|≥n-（t-2），i=1,2，则当t=7时G是点泛圈偶图。     

关于图的笛卡积尔的DOMINATION数

本文证明了:设H是任意图,G是n阶图,若G满足下列条件之一1)△(G)=n-1;2)G是γ-generalized comb;3)△(G)=n-2且(G)>2,则γ(G×H)≥γ(G)·γ(H),即V.G.Vizing猜想成立。     

Lagrange恒等式和Буняковский不等式的行列式证法及其推广

由初等代数学,我们知道下面恒等式是成立的:(sum from n to i=1 a_i~2)(sum from n to i=1 b_i~2)-(sum from n to i=1 a_ib_i)=sum from to (i,f)(a_ib_f-a_fb_i)~Z……(1)此恒等式,通常称为拉格朗日(Lagrange)恒等式。由初等代数学也容易证明下面不等式是成立的:     

简单图中圈的长度

n阶简单图G,满足e∈E(G),e=uv,使得d(u)+d(v)≥n,在这篇文章里我们证明了图G的周长可以用图G的某些参数表示出来;并且当图G不是完全二部图时,证明了图G包含了长度为3到周长的所有圈.     

点泛圈偶图的又一个充分条件

设G是连通偶图，（X1，X2）是其顶点的二分类，|X1|=|X2|=n,δ（G）≥t≥3。证明了若任意,u,v∈Xi，蕴含|N(u)∪N（v)|≥n-（t-2），i＝1，2，则当t=8时G是点泛圈偶图。