割边,割点,弱罗马控制和六个安全级别

图G的弱罗马控制数γr(G)是图G的所有弱罗马控制函数(WRDF)的最小权.本文介绍了安全级别的概念,考虑了边连通度为1的图去掉割边后对弱罗马控制数的影响和点连通度为1的图去掉割点后对弱罗马控制数的影响.     

Rm-边割存在的充分条件

Rm边割是这样一种边割, 它将连通图分割为各分支的阶都不小于m的不连通图. 设G是一个阶不小于2m的连通图. 用 c(G)表示G的周长 (即G中最长圈的长度)， 如果c(G)≥m+1, 那么G含有Rm边割, 而且周长c的下界在一定程度上是不可改进的.     

正则图m-限制边连通度的存在性

图G的m-限制边割是删除它以后G不连通,且留下的每个分支的阶至少为m的边子集;m-限制边割的最小基数称为m-限制边连通度。设G是连通（k-2）-正则图,阶至少为2k（k≥5）。证明了G的k-限制边连通度存在当且仅当G不属于一种特殊图类G^＊ k-2.     

估计n-连通图中非基本边的数目

利用Atom的概念和Halin定理的几个结果,对n-连通图中非基本的数目做了估计,以γ(G)表示图G中非基本边的数目,得到了关于γ(G)的3个定理,其中定理1是Halin定理的推广。     

kp,q（G）≤λp,p（G）成立的一些充分条件

设G是简单有限无向连通图,p,q是两个正整数.G的一个边割(顶点割)S是一个p-q-边割(p-q-顶点割),如果G-S不连通,且G-S中有一个分支至少含有p个顶点,另一个分支至少含有q个顶点.G称为λp,q-(kp,q-)连通的,如果一个p-q-边割(p-q-)顶点割存在.用λp,q(G)(kp,q(G))表示最小p-q-边割(p-q-顶点割)的基数.文章证明了在kp,q-连通(p≤q)和λp,p-连通图G中,使kp,q(G)≤λp,p(G)成立的一些充分条件及k1.p-连通图的一些性质.     

关于双圈图的Wiener指数

一个连通图G的W iener指数定义为图G中所有点对的距离之和,本文主要研究双圈图去掉一条割边后其W iener指数的下界问题,并刻画了达到下界的极值图。     

线图的邻域完整度的界

利用图的边邻域完整度，讨论了其线图的邻域完整度的界，得到了以下主要结果：①设口(G)为图G的边独立数，则VNI(L(G))≤β(G)；②对于任意连通图G，有VNI(L(G))≥ENI(G)-1，且此下界可达到。     

P2n的边幻和标号算法及超边幻和标号算法

设L为简单无向图G从V（G） ∪E（G）→{1,2,…,｜V（G） ∪E（G）｜}的一个双射函数,若L满足以下条件：对L所有的边xy∈E（G）,x、y∈ V（G）,都有L（x）＋L（y）＋L（xy）=C,C为常数,则L是图G的边幻和标号,图G是边幻和图;若在此基础上,图G的顶点标号满足：L（V（G））={1,2,…,｜X（G）｜},则L为图G的超边幻和标号,图G是超边幻和图;主要研究一类图P2n的边幻和标号以及超边幻和标号,并给出了相应的证明.     

λ5-最优图的邻域交条件

给出了λ5-最优图的邻域交条件:设G是一个阶至少为10的连通图,对G中任意一对不相邻顶点u和v,若u,v均不在三角形中,有|N(u)∩N(v)|≥6,若u或v在三角形中,有|N(u)∩N(v)|≥9,则G是λ5-最优的;若G中任意一对不相邻顶点u和v满足|N(u)∩N(v)|≥7,任意一条边xy满足|N(x)∩N(y)|≤3,则G是λ5-最优的.     

一类特殊的m限制边连通图

设G是一个连通图,F是G的一个边割,若G-F的每个连通分支至少有m个顶点,则称F是G的一个m限制边割.若图G存在m限制边割,则称图G是m限制边连通图.文章刻画了只含一个圈且长度为5的m限制边连通图.     

关于哈密尔顿指数的综述

图G的线图L（ G）是指以G的边集E（ G）为顶点集且L（ G）的2个顶点邻接当且仅当它们在G中有公共顶点。 n次迭代线图Ln（G）递归地定义为L0（G）=G,Ln（G）=L（Ln-1（G））（n∈N=｛0,1,2,…｝）,其中L1（ G）=L（ G）并且假设Ln-1（ G）非空,使得Ln（ G）是哈密尔顿的最小整数n称为哈密尔顿指数,用h（ G）表示。该文综述了（类）哈密尔顿指数的一些结果。     

正则图Cartesian积的线图的秩

设G是一个顶点为n,度为r的正则图,那么它的边为m=1/2nr.G线图是顶点为m,度为（2r-2）,边为1/2nr（r-1）的正则图,本文研究两个正则图或强正则图的Cartesian积图的线图的秩,得到了许多结果,推广了G．J．Davis,G．S．Domke等人的结论．     

两类图的边色数

设G是连通循环图.本文讨论两个与循环图有关的图类的边着色问题,得到了下列结论:①如G是奇素数幂阶循环图,则对G的任意点v,G-v是第一类的;②如G是奇数阶循环图,则G的线图L(G)是1-可因子化的,当且仅当G的边数为偶数。     

图的广义距离谱

基于一些图参数得到了图G及其线图L(G)广义距离谱半径的上下界,并确定了极值图;然后计算了一些合成图的广义距离谱。     

线图求根

给定线图G,如何求得根图H,使G=L(H)?本文就无向图和有向图作出解答.     

完全扩容图的点圈扩张性

目的讨论了完全扩容图的圈扩张性。阿勇嘎在2011年给出了完全扩容图的概念，完全扩容图是G□L（G）唯一的非平凡分支，其中L（G）是G的线图。方法利用归纳法对其进行讨论。结果与结论对于最小度大于2的连通且局部连通的完全扩容图，它的任一点由所在的一个6-圈经过若干次1或2-扩张，最后得到哈密顿圈。     

关于图的拟拉普拉斯特征多项式

设G是一简单无向图,C（G）表示G的无向关联矩阵,Q（G）＝C（G）C（G）^T,det(λI-Q(G)称为图G的拟拉普拉斯特征多项式,该文图的拟拉普拉斯特征多项式的系数进行了研究,给出了图的拟拉普拉斯特征多项式系数的一些性质,得到了正则图的线图,细分图,全图的的拟拉普拉斯特征多项式。     

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

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

没有某些圈的平面图的3可选择性

设G=(V,E)是一个图,对G的每一点v给一颜色集L(v).G称为L列表可染的,如果存在G的点染色f满足:f(u)≠f(v),(u,v)∈E(G),且f(u)∈L(u),u∈V(G).G称为k可选择的,对于任何列表L(v)(这里每一个L(v)恰有k个元素)G都是L列表可染的.本文研究了没有某些圈的平面图的可选择性,证明了没有4,5,7,10圈的平面图是3可选择的.     

无相邻三角形平面图的(4,1)~*-可选性

若对任一顶点给定k种颜色的列表,染色时每个顶点的颜色只能从自身的颜色列表中选择且每个顶点至多有d个邻点染相同的颜色,总存在图G的一个顶点的正常着色,则图G称为(k,d)*-可选色的.文章证明了每个无相邻三角形的平面图是(4,1)*-可选色的.