关于图是(r,n)-临界图的一个邻域条件

设n，m和r是满足r≥2，n≥0，m≥3的整数，且当r是奇数时，假设r≥m-1．称一个图为K1,m-free，如果它不包含以Kt,m为导出的子图．称一个图G为一个（r,n）-临界图，如果在删去G的任意n个点后，剩下G的子图都有一个r-因子,设G是一个Kl,m-free的（n＋1）-连通图，且阶为｜G｜以及r（｜G｜≥n）是偶数,证明了：如果G的最小度至少是r＋n＋m-1，阶｜G｜≥8r5＋n，并且对V（G）的任意独立点集{x1，x2}都有｜NG（x1）∪NG（x2）｜≥（｜G｜＋n）／2，那么G是一个（r,n）-临界图．关于G的最小度和｜NG（x1）∪NG（X2）｜的下界是紧的。     

SG类图簇的伴随多项式的因式分解及色性分析

设G是任意的P阶连通图，V(G)={V1，V2，…，Vp}，Sn 1是具有度序列(n，1，1，…，1)的．n 1阶星图．令(ψ)^G(i）(n，P)表示图G的第i个顶点与Sn 1的n度点重迭后得到的图；Srp 1^G（i）表示rG的每个分支的第i个顶点依次与Sr 1的r个1度点重迭后得到的图，这里n≥1，P≥2，1≤i≤P．我们通过研究图的伴随多项式的因式分解，证明了两个图簇Srp 1^G(i）U（r-1)K1与(r-1)GUψG(i)(r,P)的补图是色等价的，但它们均不是色唯一的，从而推广了张秉儒证明的文[14]中的定理1。     

仙人掌图的L（2，1）-标号

一个图G的L（2，1）-标号是给图G上的顶点分配非负整数标号，使得G上相邻的两个点的标号至少相差2，距离为2的两个点的标号则不同．G的L（2，1）-标号数λ（G）是所有能使图G正常标号的最小标号．如果一个图的任何两个圈不含有公共边，则称这个图为仙人掌图．显然树是它的一个子图类．对于任何树T，有△（T） ＋ 1 ≤λ（T） ≤△A（T）＋2．本文中我们证明了在一些条件下，这个界也适用于仙人掌图．     

最大Randid指标的k悬挂点化学树的性质

化学分子图G的Randie指标为R（G）=∑wv（dG（u）dG（v））^2/1．其中uv是G的边，dG（u）表示的顶点u的度．本文刻画了具有最大Randie指标的k悬挂点化学树的一些性质．     

恰含两个圈的二部图的能量

设λ1,λ2,…,λn是n阶图G的特征值,图G的能量是E(G)=|λ1| |λ2| … |λn|,设G(n)是n个顶点n 1条边的恰有两个圈的连通二部图的集合,Z(n;4,4)是G(n)中的一个图,它的两个长为4的圈恰有一个公共点,其余n-7个点都是悬挂点且均与这个公共点相邻．文中证明了Z(n;4,4)是G(n)中具有最小能量的图。     

利用计算机计算n阶图的特征多项式的方法

1引言设G=（V,E）为n阶无向的简单连通图.记N（v）为v的所有相邻点的集合,则d（v）=|N（v）|称为顶点v的度.若d（v）=1,则称v为G的一个悬挂点.设D（G）=diag（d（v₁）,d（v₂）,…,d（v_n））和A（G）分别表示图G的度对角矩阵和邻接矩阵,则L（G）=D（G）-A（G）称为图G的Laplace矩阵,而Q（G）=D（G）+A（G）称为图G的SignlessLaplace矩阵.用符号N_m×n表示一个m行n列的矩阵,M_n表示一个n阶的方阵.特     

图的谱半径与拟悬挂点数

设G（n,k）为含有k个拟悬挂点的n阶图所构成的集合.本文刻画了在G（n,k）中无符号Laplace谱半径达到最大的图,同时给出了当k=0,1,2,3时,在G（n,k）中无符号Laplace谱半径达到最小的图.     

3-调和的5-圈图

设v1，v2，v3，…，vn是图G的n个顶点，（d（v1），d（u2），d（u3），…，d（vn））^T是图G邻接矩阵A的特征向量，则称G是调和图，其中d（vi）表示顶点弘的度．1—4圈的调和图已经确定，本文确定了所有的3-调和的5-圈调和图．     

五类特殊图的三种距离矩阵的特征多项式

设G是一个具有顶点集V(G)={v_1,v_2,…,u_n}的n阶简单图.设d_(i,j)=d(v_i,v_j)表示图G中任意两个顶点v_i与v_j的距离.矩阵D(G)=[d_(i,j)]_(n×n)定义为图G的距离矩阵.定义Tr(v)=∑_(ueV(G))d(u,u)为图G中顶点u的点传递度.Diag(Tr)表示以G中顶点的点传递度为主对角线上元素的对角矩阵.则矩阵D~L(G)=Diag(Tr)一D(G)和D~Q(G)=Diag(Tr)+D(G)分别定义为图G的距离拉普拉斯矩阵和距离无符号拉普拉斯矩阵.分别得到五类特殊图的距离,距离拉普拉斯,距离无符号拉普拉斯的特征多项式的一般表达式.     

图Gn的优美表示

将给出三个结果：（i）如果图G是SZ（｜S｜=n≥2）上的整数和图,那么0∈S当且仅当图G至少有一个（n-1）度顶点;（ii）图G（G≠K2）是至少有两个零点的整数和图当且仅当G■K2·Gn;（iii）设图G（G≠K2）是SZ上的整数和图,｜S｜=n＋2,n∈N＋.若图G至少有两个零点,则S={mx｜m=-1,0,1,2,…,n;x∈Z且x≠0}.     

一类直径为2的极大平面图的Mostar指数

图G的Mostar指数定义为Mo(G)=∑uv∈Ε(G)|nu-nv|,其中nu表示在G中到顶点u的距离比到顶点v的距离近的顶点个数,nv表示到顶点v的距离比到顶点u的距离近的顶点个数.若一个图G的任两点之间的距离至多为2,且不是完全图,则称G是一个直径为2的图.已知直径为2点数至少为4的极大平面图的最小度为3或4.本文研究了直径为2且最小度为4的极大平面图的Mostar指数.具体说,若G是一个点数为n,直径为2,最小度为4的极大平面图,则(1)当n≤12时,Mostar指数被完全确定;(2)当n≥13时,4/3n2-44/3n+94/3≤Mo(G)≤2n2-16n+24,且达到上,下界的极图同时被找到.     

一类三圈图的Wiener指数

图G的Wiener指数是指图G中所有顶点对间的距离之和,即W（G）=∑dc（u,u）,{u,u}CG其中de（u,u）表示G中顶点u,u之间的距离.三圈图是指边数与顶点数之差等于2的连通图,任意两个圈至多只有一个公共点的三圈图记为T_n~3.研究了三圈图T_n~3的Wiener指数,给出了其具有最小、次小Wiener指数的图结构.     

具有最大度距离的单圈图

设U (n)是具有n个顶点的所有单圈图的集合,G(3; n- 3)是由一个三角形C3粘上一条悬挂路P_(n-3)得到的单圈图.本文将证明当n 5时具有最大度距离的单圈图是G(3; n - 3).     

On Domination and Independence Numbers of Graphs

A set S of vertices of a graph G is dominating if each vertex x not in S is adjacent to some vertex in S, and is independent if no two vertices in S are adjacent. The domination number, γ(G), is the order of the smallest dominating set in G. The independence number, α(G), is the order of the largest independent set in G. In this paper we characterize bipartite graphs and block graphs G for which γ(G) = α(G).     

On the Hosoya index of graphs

Let G be a (molecular) graph. The Hosoya index Z(G) of G is defined as the number of subsets of the edge set E(G) in which no two edges are adjacent in G, i.e., Z(G) is the total number of matchings of G. In this paper, we determine all the connected graphs G with n + 1 ≤ Z(G) ≤ 5n ? 17 for n ≥ 19. As a byproduct, the graphs of n vertices with Hosoya index from the second smallest value to the twenty first smallest value are obtained for n ≥ 19.     

外平面图的有界染色

图G的k-有界染色是图G的一个最多有k个顶点染同一种颜色的顶点染色．图 G的k-有界染色数Xk(G)是指对G进行k-有界染色用的最少颜色数．本文给出了n个顶点的外平面图能用[n/k]种颜色k-有界染色的一些充分条件．     

线图上的团染色问题

设G=(V,E)为简单图, G的每个至少有两个顶点的极大完全子图称为G的一个团. 图的团染色定义为给图的点进行染色使得图中没有单一颜色的团, 也就是说每一个团具有至少2种颜色.图的一个k-团染色 是指用k 种颜色给图的点着色使得图G 的每一个团至少有2种颜色.图G的团染色数\chi_{C}(G)是指最小的数k使得图G 存在k-团染色. 首先指出了完全图的线图的团染色数与推广的Ramsey 数之间的一个联系, 其次对于最大度不超过7的线图给出了一个最优团染色的多项式时间算法.     

黑白顶点数目相等的无完美匹配四角系统

四角系统是一个二部图，二部图有完美匹配的一个必要条件是对其顶点进行正常着色后，两个色类所含的顶点数相等，然而这一条件并不充分，本文利用构造法证明了两个色类所含顶点数相等却无完美匹配的四角系统的最小阶数是14，并且只有3种非同构的形状，由本文的方法还可以进一步构造出15阶和16阶无完美匹配四角系统的所有非同构形状，它们的数目分别是22与155。     

关于图的3-条件色数

For integers k0,r0,a(k,r)-coloring of a graph G is a proper k-coloring of the vertices such that every vertex of degree d is adjacent to vertices with at least min{d,r}diferent colors.The r-hued chromatic number,denoted byχr(G),is the smallest integer k for which a graph G has a(k,r)-coloring.Define a graph G is r-normal,ifχr(G)=χ(G).In this paper,we present two sufcient conditions for a graph to be 3-normal,and the best upper bound of 3-hued chromatic number of a certain families of graphs.     

路可扩图的一个充分条件

通过讨论图中任意一对不相邻顶点的度和,对路可扩图的充分条件进行研究,得到了如下结果：设图G的阶是n,如果G中任意一对不相邻顶点的度和至少为3/2n-1,则图G是路可扩的.并且说明了这里两不相邻顶点的度和的下界3/2n-1是最好可能的.