图的对称分割指数的界

设G为n阶无向图,其顶点集V(G)={v1,v2,…,vn},di为顶点vi的度,边集E(G),图G对称分割指数定义为SDD(G)=∑vivj∈E(G)(di/dj+dj/di),反对称分割指数定义为ISDD(G)=∑vivj∈E(G)di·dj/d2i+d2j.应用图G的边数、最大度Δ、最小度δ等图不变量得到了图的对...     

一类单圈图的度距离

图G=(V,E)表示顶点集为V、边集为E的所有的简单连通图的集合,研究了棒棒糖图L(n,k)的度距离,L(n,k)是将一条长为n-k的路的一个端点连接到圈Ck的一个顶点v上得到的一类特殊的单圈图。     

棒棒糖图的Merrifield—Simmons和Hosoya指数

i（G）表示图G的Merrifield-Simmons指数,定义为图G的独立点集个数;z（G）表示图G的Hosoya指数,m（G,k）表示G的k-匹配数,则z（G）是所有的m（G,k）的总和（1≤k≤[n/2]）,其中n是G的顶点数．给出n阶棒棒糖图Ln．k的Merrifield-Simmons指数和Hosoya指数以及它关Merrifield—Simmons指数和Hosoya指数的一个排序．     

一类单圈图的度基尔霍夫指数

设G是简单连通图,顶点集为V（G）.图G的度基尔霍夫指数定义为图G中所有顶点对的度与顶点之间的电阻距离乘积的和.棒棒糖图Ln,k是路Pn-k的一个端点连接到圈Ck的一个顶点得到的一类特殊的单圈图.给出首先给出Ln,k的度基尔霍夫指数计算公式,然后刻画了相应的极图.     

删边操作下图的Harmonic能量

设G是一个n阶连通图,H(G)是图G的Harmonic矩阵,图G的Harmonic能量定义为矩阵H(G)的所有特征值的绝对值之和。设e=xy是图G的一条边,G-e表示从图G中删除边e=xy得到的图,d_x表示顶点x的度。本文讨论了当删除一条非悬挂边e=xy且N_G(x)∩N_G(y)=?时,连通图G的Harmonic能量的变化。当d_x,d_y≥d时,Harmonic能量变化的上界为■;当d_x,d_y≥2时,Harmonic能量变化的上界为■。     

一类树的Hosoya指数

以z(G)表示图G的Hosoya指数,m(G,k)表示G的k-匹配数,则z(G)表示所有m(G,k)的总和.研究了直径不超过4的树的Hosoya指数,刻画了取得极值时的极图.     

两个双向圈的双色有向图的本原指数

一个双色有向图D是本原的,如果存在非负整数h和k,且h k＞0,使得D中的每一对顶点(i,j)都存在从i到j的(h,k)-途径,则称h k的最小值为D的本原指数.本文考虑了一类特殊的双色有向图,它的未着色图有(2n-1)个顶点,包含4个n-圈和2n个2-圈,给出了本原条件和指数上界,没有给出一个紧上界.     

关于图的(g,f)-因子分解的若干结果

对目前关于图的因子分解研究中的3个问题进行了讨论,得到了以下结果(1)设Z= {x∈V(G) dG(x) - mg(x)≤t(x), 或mf(x) - dG(x)≤t(x);t (x) = f (x)– g (x) > 0}.当Z≠SymbolFCp时,g和f可以不全为偶数,能使(mg, mf)-图有(g, f)-因子分解.(2)G是具有2n个顶点的m-正则图,m ≥n.若(P1,P2,…,Pr)是m的一个划分,则G的边集E(G)能划分成r个部分E1,E2,…,Er,使G[Ei]是G的Pi-因子,其中Pi ≡ 0 (mod 2),I= 2,…, r;P1 ≡m (mod 2).(3)G是具有2n个顶点的m-正则图,m≥n.若G不含有K3,则G有1-因子分解.     

关于不可约布尔矩阵的传递指数

本文证明了n阶非本原布尔矩阵的传递指数的上界为1/2(n-2)~2+2(当n为偶数时)和1/2(n-3)~2+ 4(当n为奇数时),并证明了该上界是可达的。     

对边幻图猜测的一个证明

令简单图G =(V ,E)是有 p个顶点 q条边的图。假设G的顶点和边由 1 ,2 ,3 ,… ,p + q所标号 ,且 f :V∪E { 1 ,2 ,… ,p + q}是一个双射。如果对所有的边xy ,f(x) + f(y) + f(xy)是常量 ,则称图G是边幻图 (edge-magic)。毛毛虫图是一个树 ,移走它的所有端点产生一个路 (称为T的脊或主干 )。例如 ,路和星图是毛毛虫图。证明了毛毛虫图是边幻图 ,从而证明了顶点不超过 8的树是边幻图。     

一类具有大线性复杂度的非线性过滤函数

文章指出了论文“A wide family of nonlinear filter functions with a large linear span”存在的问题,给出一个反例,同时得到如下结论:设a是F2上以f(x)为极小多项式的n级m-序列,α为f(x)的一个根,αδ为F2n在F2上的正规元,1≤δ<2n-1。设2≤k≤n-2,令Γ,δk={xδxδ2dxδ22d…xδ2(k-1)d G(x0,x1,…,x2n-2)|deg(G(x0,x1,…,x2n-2))相似文献   

严格有向图Hamilton路的研究

利用图论的基本方法及其思想,结合相关定义、定理提出了两个严格有向图含有向Hamilton路的两个充分条件,即D为具有n(≥2)个顶点的严格强连通有向图:1)如果对任意具有共同的内邻点或者具有共同的外邻点的非邻接顶点对{x,y},都有d(x) d(y)≥2n 1,且min{d (x) d-(y),d-(x) d (y)}=n-2,则有向图D含有向Hamilton路;2)如果对任意具有共同内邻点或者具有共同的外邻点的非邻接顶点对{x,y},都有d(x) d(y)≥(5/2)n-5,则有向图D含有向Hamilton路.     

πn(x)零点上的几类(0,1,…,m-2,m)插值

对n为偶数和奇数时分别给出了πn(x)=(1-x2)P′n-1(x)零点上一类正则和一类奇异的(0,1…,m-2,m)插值,其中Pn-1表示n-1次Legendre多项式.     

一类含有三个圈的双色有向图本原指数上界

一个双色有向图D是本原的,如果存在非负整数h和k,且h+k>0,使得D中的每一对顶点(i,j)都存在从i到j的(h,k)-途径,则称h+k的最小值为D的本原指数.考虑了一类含有三个圈的双色有向图,它的未着色图有n个顶点,包含一个n-圈和两个(n-2)-圈.给出了本原条件和指数上界,并对极图进行了刻划.     

有向图中爪的一个重要性质

若u1,…,up和x为有向图D的顶点,记数列(P1,P2,…,Pp)为满足[x→u1,u2,…,up]的有向路,使得每个ui都是不同的,b(Pi)=x,e(Pi)=ui且Pi除在点x外内部顶点均不相交,则称[x→u1,u2,…,up]为有向图D中的一个爪。我们证明了以下结论:如果[x→v1,…,vp-1,y]和[y→vp,…,v2p-1](p≥1),那么存在一组整数1≤i1…ip≤2p-1,使得[x→vi1,…,vip]。     

一类含三个圈的本原有向图的m-competition指数

设D为n阶本原有向图,m和n为正整数.对于D中任意顶点x和y,都存在m(1≤m≤n)个不同的顶点v1,v2,…,vm∈V(D),使得x→kvi,y→kvi,(1≤i≤m).称满足上述条件的最小正整数k为D的mcompetition指数.本文研究了一类含有一个n长圈,两个n-3长圈的本原有向图,确定了此类本原有向图的m-competition指数.     

一类序列树的构造

图G的标号指f是V（G）到整数集合的一个映射,然后边xy∈E（G）由f（x）,f（y）导出标号,仿照优美图中平衡标号的概念,定义图的序列平衡标号的概念,利用一类具有序列平衡标号的树构造更多顶点的序列树。     

一类含有两个圈的双色有向图本原指数

一个双色有向图D是本原的,如果存在非负整数h和k,且h k＞0,使得D中的每一对顶点(i,j)都存在从i到j的(h,k)-途径,则称h k的最小值为D的本原指数.本文考虑了一类特殊的双色有向图,它的未着色图有(m n)个顶点,包含一个m-圈和一个n-圈,给出了本原条件和指数上界,并对达到指数上界的极图进行了刻划.     

H-联图的拟拉普拉斯能量

设图H的顶点集为{1,2,...,k},不交图G1,G2,...,Gk的H-联图(记作G=∨H(G1,G2,...,Gk))是指在Gi(i=1,2,...,k)的基础上,对于H中的任意顶点i、j,若i,j∈E(H),则将Gi的所有点与Gj的每一个点相连所得到的图。特别地,若H=P2,则∨P2(G1∨G2)就是G1与G2的普通联图G1∨G2[4,5]。本文借助H-联图的拉普拉斯谱的性质,刻画了H为完全图以及Gi(i=1,2,...,k)均为n阶图时,∨H(G1,G2,...,Gk)的拟拉普拉斯能量的界。     

图与其补图Q谱半径之和的上界

设G为n阶简单图,利用边数m,最小、最大顶点度δ和Δ以及色数k给出了G与其补图-G的Q谱半径之和的上界,当G不含孤立点时有:2(n-1)≤ρ(Q(G))+ρ(Q(-G))≤2(Δ-δ+n-1)和ρ(Q(G))+ρQ(-G))≤2n-3+2-12(n-1)n,其中t=min{k,-k}。当-G含l个孤立点时有:ρ(Q(G))+ρ(Q(-G))≤2n-3+2-1k(n-1)2+l,同时给出了图G与其补图-G的拉普拉斯谱半径之和的一个上界。