G的立方图G3的上可嵌入性

自从Nordhaus，Stewan和White等引入图的最大亏格以来，图的最大亏格以及图的上可嵌入引起了广泛关注．而图的最大亏格rM(G)是指最大的整数k使得图G的一个2-胞腔嵌入到可定向的曲面Sk上．因为图在任意可定向曲面上的2-胞腔嵌入中至少有一个面，关于图的上可嵌入性，刘彦佩，Xuong和Nebseky分别给出不同形式的充要条件．主要证明下述结果：设G是一个简单图，则G^3是上可嵌入的．特别地，当k≥4时，G^4也是上可嵌入的．     

边连通简单图的独立数与上可嵌入性

文章讨论了边连通简单图的独立数与上可嵌入性的关系，得到了下列结果：(1)设G是一个k-边连通简单图(I=1，2)，若口(G)≤k，则G是上可嵌入的；(2)设G是一个3-边连通简单图，若口(G)≤5，则G是上可嵌入的。     

关于Betti亏数的一个结果的改进

一个连通图G的最大亏格主要由其参数Betti亏数ξ(G)确定，本文推广了黄元秋，赵霆雷在文[4]中关于ξ(G)的结果，从而得到了关于ξ(G)的一个新结果．     

与顶点C-划分有关的上可嵌入图类

图的顶点C-划分是指：G的顶点划分{V1，V2…，Vk}，使得每个G[Vi]为多重完全图(1≤i≤k)。结合图的顶点C-划分的条件，确定了一类点的度在modulo4下值为0或3的上可嵌入图类，综合已有结果，较完整地刻画了这类图的上可嵌入情况。     

边数q≥Cp^2-1-1的（p，q）图的泛圈性研究

泛圈图长期以来是图论中研究的重要课题之一，该文利用图的包装理论研究图的泛圈性，得到。阶（p，q）图G当边数q≥Cp^2-1-1时G为泛圈图的充要条件．     

与支配集有关的上可嵌入图

结合图的支配集与其他相关条件,证明了如下结果:(1)设G是无环连通图,如果G中含有一个子图为轮W,且V(W)={x,y1,y2,,yt}(t≥3)为图G的一个支配集,则图G是上可嵌入的.(2)设G是无环连通图,如果G中含有一个子图为完全二部图D=(X,Y;E),且V(D)=X∪Y为图G的一个支配集(其中|X|≥3,|Y|≥4),则图G是上可嵌入的.     

一类上可嵌入图

本文主要证明了如下结果：设C为3－连通图，若G的顶点集存在一个C－划分{V1,V2,…，Vn},使得对每个1≤i≤n，|Vi|≡0(mod 2)，且对任意的ν∈V(G),dG=(ν)≡1(mod 2),则G是上可嵌入的。     

直径为2与3的符号图的上可嵌入

设Σ=(G,σ)是直径为2和3连通的简单符号图,G是Σ的基础图.若Σ扭转等价Δ_2-图或Δ_3-图,则Σ的Betti亏数ξ(Σ)=2,否则Σ是上可嵌入的,即ξ(Σ)≤1.     

G的立方图G~3的上可嵌入性

自从Nordhaus,Stewart和White[1]等引入图的最大亏格以来,图的最大亏格以及图的上可嵌入引起了广泛关注.而图的最大亏格rM(G)是指最大的整数k使得图G的一个2 胞腔嵌入到可定向的曲面Sk上.因为图在任意可定向曲面上的2 胞腔嵌入中至少有一个面,关于图的上可嵌入性,刘彦佩[2],Xuong[3]和Nebseky[4]分别给出不同形式的充要条件.主要证明下述结果:设G是一个简单图,则G3是上可嵌入的.特别地,当k≥4时,Gk也是上可嵌入的.     

图的顶点划分与图的上可嵌入性

图G的顶点W-划分是指G的一个顶点划分{V1,V2,…,Vs),其中G[Vi]有生成子图轮W[V1](1≤i≤s).结合图的顶点W-划分以及顶点度条件,得到了一类新的上可嵌入图类,推广了已有相关结果.     

边染色临界图主顶点数的一个结果

如果一个连通的第二类图G去掉任意一条边后其边色数都比图G小,则称它是一个临界图.最大顶点度为△的临界图称作△-临界图.1968年,Vizing猜想任意n阶△-临界图G边数m的下界为（nΔ-n＋3）/2.Fiorini不等式和差值转移法被广泛用于研究此猜想.笔者利用Vizing邻接引理和临界图的结构性质给出了Δ-临界图在△≥6且（Δ-1）度顶点至多邻接一个四度顶点时Fiorini不等式的一个新的下界.     

给定控制数的连通二部图的最大边数

研究了n个顶点的连通二部图当控制数γ(G)≥3,最大度Δ(G)≥n-γ(G)-1时的最大边数。     

基于最大平均度的图的无圈边染色

为研究图的无圈边色数与图的最大平均度之间的关系,利用差值转移方法和最小反例图的一些结构性质,证明了最大平均度不小于7/2的简单图G,如果其最大度不小于6,则其无圈边色数不超过Δ(G)+2.     

关于图划分中的一个计算复杂性问题

一个稳定集是一个图的相互不相邻的顶点集,一个仙人掌图是一个任意两个圈都没有公共点的连通图.本文我们考虑如下问题,称之为STABLE CACTUS-问题的计算复杂性:给定一个图G,G中是否存在稳定集S使得G-S是一个仙人掌图.我们证明了STABLE CACTUS-问题是一个NP-完全问题,甚至可以进一步限制给定的图G是最大度不超过4的偶图.这个结果在图的度条件下是最好的了,我们利用图的最大亏格研究中的Xoung-树方法,证明了如果G是一个最大度不超过3的图,则STABLE CACTUS-问题是多项式时间可解的.     

每点都与3度点相邻的最大临界3棱连通图的结构

没G=(V,E)是3棱连通图,若对每个x∈V(G),G-x 不是3棱连通的,则称G 为临界3棱连通图.p 阶临界3棱连通图的全体记为(?)_3(p),G∈(?)_3(p)称为最大的,如果不存在H∈(?)_3(p),使|E(H)|>|E(G)|.本文给出每个点都与3度点相邻的p 阶最大临界3棱连通图的结构.     

图的关联能量的上界

图G的关联能量IE（G）等于关联矩阵I (G)的奇异特征值之和.关联能量与能量关系密切. 本文根据n,m,最大度,最小度以及第一Zagreb 指标,给出关联能量新的上界,即IE（G）≤ 等.     

关于图的带宽与和宽

全文证明了如下结果: 文中B(G)和b(G)分别表示有P(G)个顶点的图G的带宽与和宽,Δ(G)是G的最大度,δ(G)是G的最小度,α=Δ(G~c)—Δ(G)     

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

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

图的点可区别星边色数的一个上界

图\,$G$\,的点可区别星边边色数, 记为\,$\chi'_{\rm vds}{(G)}$, 是图\,$G$\,的点可区别星边染色所用色的最小数目. 得到了一些特殊图的星边染色,
并证明了若图\,$G$\,是一个最小度不小于\,5, 且顶点数不超过\,$\Delta^7$\,的图时, $\chi'_{\rm vds}{(G)}\leqslant {14\Delta^{2}}$, 其中\,$\Delta$\,是图\,$G$\,的最大度.     

一类树的Hosoya指数

图的Hosoya指数是指图中的匹配总数.本文给出了恰有两个最大度顶点的树的最大Hosoya指数,并刻画了取得极值时的图.