双圈图的剖分的有关结果

图G的剖分是指把图G剖分成一些只含孤立点或孤立边的分支,它是有序整数对(x,y),用符号D(G)表示。本文介绍了有关双圈图剖分的一些简单结果。     

三正则平面图与平面三角剖分图

探讨三正则平面图的路与平面三角剖分图 Hamilton圈的关系 ,给出平面三角剖分图 Hamilton圈的一个充分条件及算法     

剖分-点联图和剖分-边联图的Kirchhoff指标

借助图的Laplacian矩阵的{1}-可逆矩阵,给出了剖分-点联图和剖分-边联图的Kirchhoff指标。同时给出了主要结果的两个简单的应用实例,验证了结果的正确性。     

图的圈和路剖分

设G是一个顶点数为n的图,k为任意正整数且k≤n．Hikoe Enomoto和李浩证明了：如果一对不相邻顶点的度和至少为n-k 1,其中k≤n,则除了k=2,G=G5,G能被剖分成k个子图Hi,l≤i≤k,其中Hi是圈或K1或K2．本文中证明了任何一对不相邻顶点的度和至少为n-k,则G能被剖分成k个子图Ki,l≤i≤k,其中Hi是圈或是路．     

3-正则Halin图的剖分图的全色数

研究了3-正则Halin图的剖分图G的全色数,证明了4≤xT(G)≤5,特别是当G的3-度点彼此不相邻时,有xT(G)=4,这里xT(G)表示G的全色数.     

三角剖分图的色多项式

本文给出多项式f(λ)=(λ-i)(λ-j)[λ(λ-1)…(λq)],1≤i≤j≤是 q T-多项式的一个充分必要条件,并给出f(λ)=λ(λ-1)~(n_1)(λ-2)~(n_2)…(λ-q)~(n_q)是 T-多项式的一个必要条件,其中 q≥4.n_1,n_2,…,n_q 是正整数.     

网格图的剖分图的强边染色

研究了3种网格图的剖分图的强边着色.网格图的剖分图是指用一个长为2的路去替换网格图的每条边.具体给出了六边形、四边形、三角形的网格剖分图的一种着色方法,以此为基础证明了Sχ′(Γs6)=4,Sχ′(Γs4)=5,Sχ′(Γs3)=7.     

双圈图最大特征值的上界

本文将所有ｎ阶连通双圈图划分为Ａｎ（ｐ,ｑ）与Ｂｎ（ｓ,ｔ,ｍ）两类,然后分别讨论了在其最大特征值λ１（Ｇ）的上界,并找到了达到上界的极图。     

双圈图的邻接矩阵的奇异性

连通的双圈图（即边数比顶点数多一个的连通简单图）恰有3种类型,其中2种类型的图的邻接矩阵的奇异性问题业已解决．现给出第三种类型的双圈图的邻接矩阵是奇异的充要条件.     

三角剖分图的点面全色数

平面图G(V,E,F)的点面全色数X_e(G)是使得集合V(G)∪F(G)中相邻和相关联的元素均染为不同颜色的最少颜色数。本文证明了:若G是三角剖分图,则4≤X_e(G)≤6。     

Some Results on Arithmetic and Balanced Graphs

首先考虑Ａｃｈａｒｙａ和Ｈｅｇｄｅ关于算术平衡图的三个猜想．其中一个已由他们证明,本文给出它和另一个猜想的简单证明,并指出第三个猜想在一般情形下是不对的,而在一个更强的条件下是正确的．然后讨论本文结果与已知结果之间的关系．     

关于几乎k-可扩图的若干结论

设G是具有奇数个顶点的图,k是非负整数且满足V(G)≥2k+1,若G中任意一个k-匹配都可以扩充为G的一个几乎完美匹配,则称G是几乎k-可扩图.文中证明了连通的几乎1-可扩图与2-连通的几乎k-可扩二部图分别添加一个新边后仍保持原来的可扩性.     

双圈图的Laplacian谱展

设G是一个简单连通图,矩阵L(G)=D(G)-A(G)称为图的Laplacian矩阵,其中D(G)是图的度对角线矩阵,A(G)是G的邻接矩阵.连通图G的Laplacian谱展是图的最大特征值与次小特征值之差.边数等于顶点数加1的连通图叫做双圈图.研究了双圈图的Laplacian谱展,并确定了具有最大Laplacian谱展的双圈图.     

一类双圈图拉普拉斯谱刻画

称图是由谱确定的,如果没有非同构的图具有相同的谱。用Cq标记长度为q的圈。圈图Cq的一个顶点与路图Pr的一个悬挂点相连,圈图Cq的一个顶点与Pr的另一个悬挂点相连,所得的图称为G（Cq,Cq,Pr）。本文将证明图G（Cq,Cq,Pr）由它的Laplacian谱确定。     

关于几类DNA标号图和DNA图的结果

在分子生物学中,DNA链的杂交测序的计算和重构阶段可用DNA图作为数学模型,因此,DNA图得到广泛的研究^[1.2]．为了读取DNA序列,Blazewicz等人提出了可（α,k）-标号有向图的概念,并称有向图D是DNA图,如果D是可（4,k）-标号的．2008年,原军等证明了可（α,k）-标号的有向路和有向圈的充要条件．本文证明了有向路和有向圈可（α,k）-标号的一个性质,并利用有向线图的理论证明了本文所指的伪二部单向完全图D0（A,B）、k部广义路P（V0,V1,…,VK-1）、k部广义圈C（V0,V1,…,Vk-1）以及k部广义树T（V0,V1,…,Vk-1）均是DNA标号图．进而给出并证明了二部单向完全图D（V1,V2）和k部广义路P（V0,V1,…,Vk-1）为DNA图的充要条件．     

3度非对称的点传递图的性质

设X为3度连通的简单无向图,X称为具有非平凡点稳定子群的非对称的点传递图,若X的全自同构群A在X的顶点集合上作用是传递的,而且X的任意顶点在A中的稳定子群在该点的邻域上的作用是非传递的、非平凡的.本文考察了这种图,我们给出了这类图的一些性质.     

关于图谱的几个定理

本文给出了边独立数为q的树(或森林)的第k大正特征值的下界,并且证明这个下界在很多情况下是最好可能的;又给出了一种使得具有完美对集的树最小正特征值递减的变形,从而为一个关于最小正特征值的Sharp下界的猜想给出了一种更有应用前景的新证明.     

几类3-圈图的连续边着色

设G是简单图，用颜色1，2，3，…对G的边正常着色，如果每一顶点表现的颜色构成一个连续的整数集合，那么就称这个连着色是连续的，G的亏度就是加在G上使它可连续边着色的悬挂边的最小数目。本文给出了几类3-圈图的亏度并且讨论了它的连续边着色。     

若干平方图的均匀全色数

讨论了路,圈,星,扇和轮的平方图的均匀全染色问题,得到了其均匀全色数.