正则极大平面图的邻强边染色

设G是一个简单图,若图G的一个k-正常边染色f满足对任意的uv∈E(G),都有C(u)≠C(v),则称f为G的一个邻强边染色,简称k-ASEC,并称x_(as)′(G)=min{k|G存在k-ASEC},为G的邻强边色数.其中C(u)={f(uv)|uv∈E(G)}.该文研究了一类正则极大平面图的邻强边染色,给出了着色方案,求解出其邻强边色数.     

自补图度序列的结构

自补图是图论中对称性很强的一类图,因而它有不少醒目的特点。本文讨论了自补图度序列的结构特性;除了点数是p=1(mod4)的自补图的度序列的中项外,其余的项皆成对出现。当点数是p=0(mod4)时,其所有的项都成对出现。最后给出的自补图度序列前K对和的上界。     

关于丢番图方程2x-2y·3z-2·3u=9k+1

利用初等方法给出了丢番图方程2x-2y·3z-2·3u=9k 1,x,y,k>0,z,u≥0的全部整数解:(x,y,z,u,k)=(4,2,0,0,1),(5,2,0,2,1),(6,2,2,2,1),(8,2,1,4,2),(5,4,0,1,1),(6,4,1,1,1),(9,4,0,5,1),(10,5,2,1,3),(7,6,0,3,1),(8,6,1,3,1).利用此结果给出了与和完全数相关的丢番图方程2a c 1-2c 1·3d f k-2-2·3f k-1=3k 1,a>0,c>0,d≥0,f≥0,k≡0(mod2)的全部整数解:(a,c,d,f,k)=(4,1,1,1,2),(1,3,0,0,2),(2,3,1,0,2).     

蕴含K5-Z4可图序列的刻划

对于给定的图H，称π是蕴含H可图的，如果π有一个实现包含H作为子图．Kk，Ck，Pk分别表示k阶完全图，圈长为k的圈和路长为k的路．Z4表示K4-P2.K5-Z4表示从5阶完全图中删去Z4的4条边．本文刻划了当n≥5时，蕴含K5—Z4的可图序列．     

蕴含（K_4-e）＋C_4可图序列的刻画

对于给定的图H,称π是蕴含H可图的,如果π有一个实现包含H作为子图.Kk,Ck,Pk分别表示k阶完全图,圈长为k的圈和路长为k的路.本文刻画了当n≥6时,蕴含（K4-e）＋C4的可图序列.     

蕴含（K_4-e）＋K_3可图序列的刻划

对于给定的图H,称π是蕴含H可图的,如果π有一个实现包含H作为子图.K k,C k,Pk分别表示k阶完全图,圈长为k的圈和路长为k的路.本文刻划了当n≥6时,蕴含（K 4-e）＋K3的可图序列,其中,（K 4-e）＋K3如下图所示.     

蕴含K5-P2可图序列的刻划

对于给定的图H，称π是蕴含H可图的，如果π有一个实现包含H作为子图．Kk，Ck，Pk分别表示k阶完全图，圈长为k的圈和路长为k的路．K5-P2表示从5阶完全图中删去长为2的路．LuoRong考虑了蕴含Ck可图序列的刻划问题，并刻划了当k=3，4，5时，蕴含Ck的可图序列．此外，Luo等人刻划了蕴含K4的可图序列，Eschen和Niu刻划了蕴含K4-e的可图序列，Yin Jianhua等人刻划了当r=2，S=3和r=2，S=4时，蕴含Kr,s的可图序列，其中Kr,s是r×S完全二部图．Hu Lili等人刻划了蕴含K5-C4，K5-Z4，K5-E3的可图序列，徐正华等人刻划了蕴含K1．4＋e的可图序列，王艳刻划了蕴含K1,4＋P2的可图序列，刘明静等人刻划了蕴含K5-Z5的可图序列．本文刻划了当n≥5时，蕴含K5-P2的可图序列．     

花图的邻点可区别关联色数

轮Wr+1(r≥3)是一个r阶圈加上一个新的顶点,再把圈上每个顶点与新顶点连上边所得到的图,新顶点与圈上顶点之间的边称为辐边,圈上的边称为边缘边。所谓花图Fr,m,n(r≥3,m≥1,n≥2m+1)是在轮Wr+1中,在每条辐边上分别嵌入m-1个新点,在每条边缘边上分别嵌入n-2m-1个新点所得到的图。研究花图Fr,m,n(r≥3,m≥1,n≥2m+1)的邻点可区别关联着色,确定了部分花图的邻点可区别关联色数,并给出了剩余花图的邻点可区别关联色数的上界。     

k-ary n立方体中的测地泛圈

文中用归纳假设法证明了结论：当n≥2,k≥3,u和v是Qkn中任意2个顶点,由对称性,不妨设u=（0,0,…,0）,v=（d1,d2,…,dn）,这里0≤di≤k/2,（i=1,…,n）,记d=d1＋d2＋…＋dn≤1,N=kn,则对于每个偶数l适合2d＋2≤l≤N,则Qkn中有过u和v长为l的圈C,且C上u和v的距离为d.若有i和j满足1≤i≤j≤n,使得di≥1且dj≥1,或有且dj=k/2且dj=0,j≠i,1≤j≤n,则又有l=2d;当n≥2,k≥3是奇数,u和v是Qkn中任意2个顶点,由对称性,不妨设u=（0,0,…,0）,v=（d1,d2,…,dn）,这里0≤di≤k/2,,（i=1,…,n）,记d=d1＋d2＋…＋dn≥1,N=kn,r=max{di},则对于每个奇数l适合2d＋k-2r≤l≤N,则Qkn中有过u和v长为l的圈C,且C上u和v的距离为d.     

关于Mbius梯的细分图的k-优美性

一个简单图G =(V ,E)是k 优美的 (k≥ 1为整数 ) ,如果存在单射f:　V(G)→ { 0 ,1,2 ,… ,|E| +k - 1}使得对所有的边uv∈E(G) ,由f (uv) =|f(u) -f(v) |导出的映射f :　E(G)→ {k ,k + 1,… ,|E| +k - 1}是双射 .设G是简单图 ,在G的每相邻两顶点之间都加入一个顶点后所得到的图称为G的细分图文章证明了M bius梯的细分图是k 优美图     

关于St^n∪i=1 mi-C4的优美性

本文就星形树与m—C4并图的优美性进行探讨，证明了当m≥2这类图Stp∪m—C4是优美图．并对星形树St与^n∪i=1 mi-C4并图St^n∪i=1 mi-C4的优美性进行探讨.证明了当max mi≥3 i=1，2……，n这类图St^n∪i=1 mi-C4是优美图.     

关于图P_n~3∪_4的优美性

讨论了形如P_(n³)U_4非连通并图的优美性,用构造性的方法给出了P_(n3)U_4非连通并图的优美性,用构造性的方法给出了P_(n³)U_4的优美标号,并证明P_(n3)U_4的优美标号,并证明P_(n³)U_4是交错图.     

两类联图的优美性

本文给出了两类联图Ｐ１Ｖ（Ｐ１Ｖ＾２Ｐｎ）及Ｓｔ（ｎ）ＶＴ。论证了这两类图都是优美图，由此，推出一些有意义的结论。     

一类自中心图的构造

图G为自中心图，本文给出了一种与结构造了G的一类图，即图2G*nPk，并讨论了该图的一些性质.     

关于四角仙人掌图的优美性

本文讨论了四角仙人掌图的优美性，给出了几类四角仙人掌图是优美的一些结果，从而部分回答了Ａ．Ｒｏｓａ在「１」中提出的猜想。     

补图方法在二部图最大匹配中的应用

图论中的匹配理论无论是在图论本身还是生产实践中都有着重要的作用,特别是在计算机和网络研究等领域中应用更为广泛和深入。利用补图的思想,关于二部图的最大匹配问题,给出一种新的研究方法,并通过实例说明此方法的实用性和有效性。为解决二部图最大匹配问题开辟了新途径。     

关于图P_(6k)~3∪P_n~3的优美性

讨论了P_(6k)~3∪P_n~3非连通并图的优美性,用构造性的方法给出了P_(6k)~3∪P_n~3的优美标号,并证明P_(6k)~3∪P_n~3是交错图.     

一类六点八边图的图设计

设Kv是一个v个点的完全图，G为Kv的一个不含孤立点的简单子图．Kv的一个G-设计，常记为（v，G，I）-GD，是指一个二元组（X，B），其中x为Kv的顶点集，B是Kv的一些子图（亦称为区组）构成的集合，使得每一个区组与G同构，且Kv的任何一条边恰在B的一个区组中出现．文章讨论了一类六点八边图中尚未解决的3个图G（i=1，2，3）的图设计存在性问题，并证明了（v,Gi，1）-GD（i=1，2，3）存在的必要条件v=0，1（mod16）且v≥16也是充分的．从而给出了这类六点八边图图设计存在的完全解．     

一类图中具有最小能量的图

设λ1,λ2,…,λn是图G的特征值,则称E(G)=|λ1| |λ2| … |λn|为图G的能量.用Sl1n,l2表示由两个具有唯一公共顶点u的圈Cl1和Cl2,且其余边均为u上的悬挂边的n阶双圈图.利用Sachs子图证明了在所有含有两个边不相交的圈Cl1和Cl2的n阶双圈连通图中Sl1n,l2是能量最小的.     

关于自中心图的一点注记

本文定义了一种加链替换运算，并证明了定理即两个自中心图通过这种运算所得之图其自中心性保持不变。