线图的邻域连通度

研究了图G的边邻域连通度λNB（G）和它的线图L（G）的点邻域连通度κNB（L（G））之间的关系,证明了AλB（G）≤κNB（G）．提出了一个新的概念：限制性边邻域连通度λrNB（G）,证明了κNB（L（G））≤λArNB（G）．最后,研究了上述两个不等式成为等式的充分条件．     

广义笛卡尔积图的连通度

本文定义了图G_1、G_2的广义笛卡尔积图G=G_1∫G_2,并且证明了它们的连通度具有关系k(G)≥k(G_1)+k(G_2)。这一结果是对文[1]中关于G_1与G_2直积的结果的推广。此外,本文还讨论了G=G_1∫G_2的直径及Hamilton性。最后,利用G=G_1∫G_2的结果对循环图的连通度进行了讨论。     

关于连通图最长圈的一个结果

设C是k-连通图G（2≤k≤6）的一个最长圈.H是G-C的一个分支.[5]中证明,若L（H）≥k-2,则｜C｜≥kδ-k（k-2）,这里L（H）表示H中最长路的长度,δ表示G的最小度.本文在H满足特定的条件时,对于k∈{3,4,5}改进了上述｜C｜的度下界.     

0—1多面体图连通度猜想的一个反例

本文给出０－１多面体图连通度猜想的一个反例。由此说明０－１多面体图的连通度未必等于最小度。     

有向循环图的连通度

本文给出了有向循环图连通度达到其最小度的一个充要条件.     

单圈图的N-G型的代数连通度的界

对任一个n阶单图G，用α（G）表示G的代数连通度，证明了对任一n阶单圈图G，有1≤α（G）＋α（G）．     

N-G型的代数连通度的界

对任一个n阶单图G,用a(G)表示G的代数连通度,Gc表示它的补图.着重证明了2个图类的代数连通度的N-G型的界:a(G)+a(Gc)≥1.     

无限图的笛卡尔积的哈密顿性和连通性

本文证明了两个连通有向或无向图(至少有一个无限)的笛卡尔积的连通度不小于它们的连通度之和,并讨论了一些特殊图的笛卡尔积的哈密顿分解及哈密顿性。     

两类E~G形图簇的补图的色等价性定理

设G是任意的p阶连通图,用ΨG(i)(k,p)表示把图G的第i个顶点vi与星图Sk+1的k度点重迭后得到的图(1≤i≤p),给出了图ΨG(i)(k,p)与星图Sn+1组合而成的两类EG形图簇,并通过研究这些图簇的伴随多项式的因式分解,进而证明了它们的补图的色等价性定理。     

Cartesian积与邻点可区别着色之间的关系

图G的一个正常k-边着色是指k种颜色1,2,…,k对图G各边的一个分配,使得任意2条相邻边染以不同的颜色.对于图G的一个正常边染色f和G中任何一个顶点x,S_f（x）或S（x）表示与顶点x关联的边在f下的颜色所构成的集合.若对于图G中任意2个相邻顶点u和v,有S（u）≠S（v）,则称f为图G的邻点可区别正常边染色.对图G进行邻点可区别正常边染色所需的最少颜色数,称为G的邻点可区别正常边色数,记为χ'_a（G）.图G的一个正常k-全染色是指k种颜色对图G的顶点和边的一个分配,使得任意2个相邻的或相关联元素染以不同的颜色.对于图G的一个正常全染色g和G中任何一个顶点 x,使用C_g（x）或C（x）来表示顶点x的颜色（在g下）以及与顶点x关联的边在g下的颜色所构成的集合.若对于G中任意2个相邻顶点u和v,有C（u）≠C（v）,则称g为图G的邻点可区别全染色.图G的邻点可区别全染色所需的最少颜色数称为图G的邻点可区别正常全色数,记为χ″_a（G）.主要讨论了Cartesian积和2种邻点可区别染色之间的关系.     

关于四边形连通无爪图的注

文献【1】中,证明了没有1度点的每个四边形连通无爪图G如不包含同构于G1或G2（见图1）的导出子图日使得H中每个4度点x的N1（X,G）是不连通的,那么它是哈密尔顿的．然而,在文献【2】中,命题2．5和定理2．6的叙述和证明中存在一些问题．在本文中,给出了它们的正确表述以及改进了的证明．     

图的带宽的一个树宽上界

本文证明了若Ｇ是一个顶点数为ｎ,树宽为ｋ的图,则图Ｇ的带宽至多为（ｎ＋ｋ／２－１）－１。     

Camina-Gagen定理的一个推广(Ⅳ)

设G是2-(v,k,1)设计D的全自同构群Aut(D)的一个子群,且G是区本原的.若k2=k/(k,v)=17或18,则G也是点本原的.     

关于临界h棱连通图的最大棱数及最大图的结构(Ⅱ)——临界h棱连通图的性质和最大临界3棱连通图类的刻划

设λ(G)表示G的棱连通度,图G称为临界h棱连通的,如果λ(G)=h而且对任何x∈V(G),λ(G-x)≤h-1,具有最大棱数的临界h棱连通图称为最大临界h棱连通图.本文首先证明对h≥3的临界h棱连通图的若干性质,然后证明最大临界3棱连通图的每个顶点都与3度点相邻,并由此给出了此类图的结构刻划和最大棱数.     

化学单圈图的原子键连通性指数

图G的原子键连通性指数的定义如下:ABC(G)=∑uv∈E(G)((du+dv-2)dudv)(1/2).其中du、dv分别表示图G的边uv的2个端点u、v的度数.ABC指数已被证实为研究烷烃的稳定性以及环烷烃的应变能提供了一个很好的模型.讨论了n阶化学单圈图,给出了其ABC指数的可达的下界及其相应的极图     

图Ψ*S*（4δ,nδ）∪tSδ*的伴随多项式的分解及色等价性分析

设Pn是具有n个顶点的路,Ψ*(4,n)表示把2P3的两个2度点分别与Pn的两个1度点重迭后得到的图,Sδ*(δ=rm+1)表示把rPm+1的每个分支的一个1度点重迭在一起得到的图。用PnSδ*表示把Pn的n个顶点与nSδ*的每一个分支的r度顶点依次重迭后得到的图,并用Ψ*S*(4δ,nδ)表示把图Ψ*(4,n)的n+4个顶点与(n+4)Sδ*的每一个分支的r度顶点依次重迭后得到的图。运用图的伴随多项式的性质,证明了图PnSδ*∪tSδ*与Ψ*S*(4δ,nδ)∪tSδ*的伴随多项式的因式分解定理,进而得到了这类图的补图的色等价图的结构特征。     

循环图的预解Estrada指标

Circulant graphs are an important class of network topology. Let G be a simple graph with n vertices, let A be the adjacency matrix of G, and λ₁,λ₂,…,λ_n be the eigenvalues of graph G. As a kind of centrality of complex networks, the resolvent Estrada index of G is defined as EE_r(G)=((1-λ_i)/(n-1))^-1. By Ramanujan's sum, using the Euler function and Mobius function, we characterize the lower bound of resolvent Estrada index of circulant graph, and obtain some computational formulas of integral circulant graphs.     

关于Menger图的几种运算

设Ｇ是一个简单连通图，若分离Ｇ的余一独立集Ｓ的最小点数等于连接Ｓ的点之间的内部不相交路的最大个数，则称Ｇ是Ｍｅｎｇｅｒ图。我们考虑了图的几种运算并给出了运算后的图是Ｍｅｎｇｅｒ图的条件。