关于哈密顿图的一点注记

如果图G含有一个过G中每个顶点恰好一次的圈,则称G是一个哈密顿图。对于含有两个不相邻顶点a和b的图G,本文给出了一些条件,如果G满足这些条件,且G ab是哈密顿图,则G也是哈密顿图。     

联图和结合图的Menger性质

对两个给定的图G和H，以G H表示G和H的联，以G[H]表示G对图H的结合图，证明了如下结果：(1)G H是Menger图当且仅当G和H均为Menger图；(2)若G和H均为Menger图，且G的任一导出子图也是Menger图，则G[H]必为Menger图。     

若干图的Mycielskian图的边色数

对图G(V,E),μ(G)称为G的Mycielskian图,若V(μ(G))=V(G)∪{v′|v∈V(G)}∪{w}且w V(G),而E(μ(G))=E(G)∪{uv′|uv∈E(G)}∪{wv′}.研究了路、圈、扇、轮图的Mycielskian图的边色数.     

非连通图G1∪G2⊙K1的优美标号

研究了图G1∪G2⊙K1的优美性,其中G1是满足一定条件的交错图,G2是任一优美图,G2⊙K1是优美图G2中优美值为1的顶点粘接1条悬挂边所形成的图.构造了1类新优美图,推广了已有文献的结果.     

6长圈带2条悬边的8阶连通图的图设计

构造了所需的带洞图设计, 再结合一些小阶数的图设计的存在性, 得到了关于图Gi (i=1,2,3,4)的图设计(v, Gi ,1)-GD的存在谱, 其中图Gi (i=1,2,3,4)是给6长圈增加2条悬挂边所得的8阶连通图, 且G1, G2, G3, G4互不同构.     

平方根图

设G是一个简单图及顶点为u1，u2，…，uv，d(vi)是点vi的度，令^～d(G)={[d(u1)]的平方根，[d(u2)]的平方根，…，[d(uv)]的平方根}，称G是一个平方根图，如果^～d(G)是G的邻接矩阵的一个特征向量，猜想：一个连通图G是一个平方根图的充分必要条件是G是一个正则图或半正则图，这个猜想在本文中得到了证明。     

关于H-联图的拉普拉斯特征值

H-联图是在不交图G1,G2,…,Gk的基础上,对于H中的任意两点i,j,若ij∈E(H),则将Gi的每一点与Gj的每一点相连所得到的图,其中,H的顶点集为{1,2,…,k}.特别地,{G1,G2}的P2-联图就是普通联图G1∨G2.本文研究了H-联图的拉普拉斯特征多项式,给出了H-联图的拉普拉斯谱与图G1,G2,…,Gk以及基图H的拉普拉斯谱之间的关系.进一步研究了基图分别为完全图、完全二部图时的H-联图,给出了Kk-联图和Ks,t-联图的拉普拉斯谱以及相应的特征多项式.另外,证明了当基图H是完全图、完全二部图或阶数小于等于4的图(除P4外)时,L-整图{G1,G2,…,Gk}的H-联图也是L-整的.     

分数（k,n＇,m）-临界消去图的领域并条件

设G是一个图,若去掉G中的任意n＇个顶点的剩余子图仍是分数（k,m）-消去图,则称G是一个分数（k,n＇,m）-临界消去图.给出了图G是分数（k,n＇,m）-临界消去图的领域并条件,并说明此条件在一定意义下是最好的.     

2-连通无爪Hamilton图的一个充分条件

本文证明了:设G是n阶2-连通无爪图,△(G)≥n-4,则G是Hamilton图。     

关于跳跃图的注记

证明若G是连通图，则J(G)≌G当且仅当G是G或Cor(K3)．通过引进边度概念，讨论连通图G的跳跃图J(C)是Hamilton图的一些充分条件．     

测地图所包含的八圈及它上的割线构成图的结构形式

如果图G上的任意两点都有唯一的最短路相连，则我们称图G是测地图。测地图的问题最先由O．Ore在[2]中提出，对测地图中出现的偶图，常常需要归纳这种图的结构类型。本给出了测地图包含八圈时，八圈和它上的割线构成图的结构形式。     

关于图运算的测地数

对于图G(或有向图D)内的任意两点u和v,u-v测地线是指在u和v之间(或从u到v)的最短路.I(u;v)表示位于u-v测地线上所有点的集合,对于SV(G)(或V(D)),I(S)表示所有I(u,v)的并,这里u,v∈S.G(或D)的测地数g(G)(或g(D))是使I(S)=V(G)(或I(S)=V(D))的点集S的最小基数.G的下测地数g-(G)=min狖g(D):D是G的定向图狚,G的上测地数g+(G)=max狖g(D):D是G的定向图狚.对于两个图G和H,u∈V(G)和v∈V(H),在u和v之间加一条边,然后再收缩这条边uv所得的图,记为GuHv.本文主要研究图GuHv的测地数和上(下)测地数.     

关于测地图的几种基本结构及特点

给出了测地图中８－圈及其割线的结构形式，并得出了一个图是直径为３的测地块的一个充要条件。     

关于树与完全图的笛卡尔乘积图的连通测地数

给出了两个非平凡图,确定了树与完全图的笛卡尔乘积图的连通测地数.测地数与连通测地数是图的两个重要参数.树与完全图的笛卡尔乘积图的测地数已被确定.     

不含三角形的平面图的无圈边染色

图的无圈边染色是图的染色理论中的一个重要问题.2001年,Alon等猜想任意简单图G的无圈边色数都不超过Δ(G)+2,其中Δ(G)为图G的最大顶点度.为了深入研究该猜想对平面图是否成立,利用差值转移方法并结合最小反例图的一些结构性质,证明了:不包含三角形的平面图G,如果其最大顶点度不小于6,则其无圈边色数不超过Δ(G)+3.     

一类新变换图的基本性质

通过引入符号\,“通过引入符号"0",定义了一类新的变换图.首先对于一般的非空简单无向图G,研究了它的10种新变换图的连通性和正则性.特别对于正则图G,利用图G的谱刻画了其变换图的谱.     

二部图K(m,n)-A中的色正规图类

设Ｐ（Ｇ,λ）表示简单图Ｇ的色多项式。简单图Ｈ称为与Ｇ是色等价的（记作Ｈ￣Ｇ）,如果Ｐ（Ｈ,λ）＝Ｐ（Ｇ,λ）。简单图类Ｌ称为色正规图类,若对任意Ｈ,Ｇ∈Ｌ使Ｈ￣Ｇ都有Ｈ与Ｇ同构。     

几类特殊平面图的圈包装问题

给定一个无向连通图G，圈包装问题就是求G的边不相交圈的最大数目．此问题在一般图下是APX困难问题，在平面图下是NP困难问题．主要证明了在几类特殊的平面图下多项式时间可得到最优解．主要考虑外平面图，系列平行图和平面欧拉图这三类特殊的平面图．     

变换图G~(*xy)的独立数

变换图的概念由全图推广而来。文章在中图的补图M(G)的定义启发下,定义了四类变换图,其中一个恰是(G),并探讨了这些变换图的独立数。研究了变换图G*-+的独立数与原图最大度的关系,以及G*++与G*+-的独立数与原图边独立数的关系。