Queens-图的构造

一个(0,1)-矩阵A的queens-图的点集对应于A中的“1”,两个点邻接当且仅当它们对应的“1”在A的同一条线上．文献引入此概念并进行了讨论,本文进一步给出queens-图的几个结论,并得到了几类新的queells-图。     

关于Queens-图的若干结果

Queens-图是文献^[1]引入的概念，本文给出了queens-图的几个结论，并找到了几类quees-图。     

图的邻接树图是哈密尔顿的

图G的邻接树图就是这样的图,以图G的生成树为顶点的图,两个顶点之间相邻,当且位当相应的两个生成树是相邻的.1986年蔡茂诚提出猜想:任何简单图的邻接树图都是哈密尔顿图.本文证明了这一猜想,所得的结论比猜想本身还要强.     

积图邻强边色数的注记

给出了积图邻强边色数的两个定理.在此基础上,证明了:对积图T×Wm,T×Fm和T×Sm,当T的最大度点不相邻时,它们的邻强边色数均为Δ(T) m.当T的最大度点相邻时,它们的邻强边色数均为Δ(T) m 1.其中T为n(n≥3)阶树图.Wm,Fm与Sm分别为m 1(m≥4)阶的轮,扇和星图.     

哈密顿类指数的一个注记

证明了若连通图G是1-哈密顿图(有含k(k≥2)个圈的2-因子、点泛圈可序的、有两个边不交的哈密顿圈、泛连通的),那么L(G)也是1-哈密顿图(有含k(k≥2)个圈的2-因子、点泛圈可序的、有两个边不交的哈密顿圈、泛连通的).     

伪Halin-图的结构性质及其色性

对2-连通平面图G，f0为G的一个边界(一个圈)上无弦的面，且V(fo)上的顶点度至少为3．若去掉f0边界上的所有边后得到的图为除V(f0)中的点外，所有点的度不小于3的树T，则称G为一伪Halin-图，称G为Halln-图当且仅当所有V(f0)中的点的度为3．同时讨论了这类图的结构性质及其色性．     

图的符号控制数的下界

设G是一个图,一个函数,f.V→{-1,+1}如果∑v∈N[u]f(v)≥1对于每个点u∈V成立,则称f为图G=(V,E)的一个符号控制函数.一个图G的符号控制数定义为γs(G)=min｛∑v∈V(G)f(v)|f为图G的符号控制函数｝.该文主要给出了一个图G的符号控制教γs,(G)的若干新下限,并刻划了满足γs,(G...     

整数流的若干问题

设G（V，E）是2一边连通无向简单图，D（V，A）是G的一个定向图，A（D）为D的弧集，若映射f:A(D)→{…，－n,-(n-1),…,-1,0,1,…,n,…}满足Au∈V（D）有f^ (u)=f^-(u),则称＜D，f＞为一流图。其中f^ (u)=∑vu∈A(D)f(vu),f^-(u)=∑uv∈A(D)F(UV)。对Aa∈A（D），当f(a)≠0时，称＜D，f＞为非零流图，对非零流图。对非零流图＜D，f＞，称所有｜f(a)｜和最小值的流f为D的最小流。本文研究了这类流的若干问题。     

多重联图全染色的一点注

研究了多个点边不交简单图的联图的全色数.     

关于连通图的IC-着色

文[2]中引入了图的IC-着色和IC-指数概念,本文考虑了两个图的和图IC-指数,证明了:对任意连通图G和H,均有M(G H)(M(G) 1)(M(H) 1)-1,并给出了星的任意细分图IC-指数的一个下界,推广了文[2]中的两个结果.     

若干合成图的星全染色

简单图G和H的合成图是指具有顶点集V（G）×V（H）的简单图G[H],它的顶点（u,v）和另一个顶点（u,v＇）相邻当且仅当或者uu＇∈E（G）,或者“u=u’且vv’∈E（H）．文中研究了n＋1阶简单图G与m阶简单图H的合成图的星全染色,其中G为Wn。,扇Fm或星Sn．得到以下结果：（1）若△（H）=2且n≥4,m≥5,则G[H]的星全色数为（2n＋1）m;（2）若x（H）=△（H）=m-1且n,m≥4,则G[H]的星全色数为2（n＋1）m-1．     

关于图的反符号星控制数

引入了图的反符号星控制的概念,设G=（V,E）是一个没有孤立点的图,一个函数f：E→＋{1,-1}对一切点v∈V（G）所在的星中的边e有∑f（e）≤0成立,则称,为图G的一个反符号星控制函数．而γ’rss（G）=max{∑f（e）｜f为图G的反符号星控制函数,e∈E（G）}称为图G的反符号星控制数．我们主要给出了图的反符号星控制数的上界,并确定了完全图与完全二部图的反符号星控制数．     

关于图的Grundy着色

设G=(V,E)为一个图,函数f:V→{1,2,…,k}被称为图G的一个Grundyk-着色函数,如果f为图G的一个真k-着色函数且对于任何两种颜色i和j(1≤i≤j≤k),每个j色点的邻域中至少有一个i色点。图G的Grundy色数定义为Γ(G)=max{k|存在图G的Grundyk-着色函数}。给出了图的Grundy色数的若干上界,并确定了几类特殊图的Grundy色数。     

The Dimensions of Graphs and Constructions of Their Bases

IntroductionGraph G,considered in this paper,is finiteand simple with vertex set V ( G) and edge setE( G) .Let d( x,y) denote the distance between xand y in G and W={w1,w2 ,…,wk}denote the or-dered set of V( G) .For any given v∈V( G) ,therepresentation of v with respect to W is the k- vec-tor:r( v| W) ={d( v,w1) ,d( v,w2 ) ,…,d( v,wk) }.The ordered set W is called a resolving set of G ifr( u| W) =r( v| W) implies that u=v for all pairs{u,v}of vertices of G. A resolving set of G with…     

图的反符号星k控制数

设G=(V,E)是一个图,一个函数f:E→-1,+1如果∑f(e)≤0 e∈E[v]对于至少k个顶点v∈V(G)成立,则称f为图G的一个反符号星k控制函数,其中E(v)表示G中与v点相关联的边集.图G的反符号星k控制数定义为γrkss(G)=max{∑f(e) e∈E│f为图G的反符号星k控制数}。得到了一般图的反符号星k控制数的若干上界,对文[6]中的结果进行了推广,还确定了路Pn和圈Cn的反符号星k控制数。     

单圈图的邻强边染色

设G是阶数不小于3的简单连通图,G的k-正常边染色称为是邻强的,如果G的任意相邻的两顶点的关联边的颜色构成的集合不同.对一个图G进行邻强边染色所需要的最少的颜色数称为是G的邻强边色数.本文研究了单圈图的邻强边染色.     

关于图的反减圈控制数

设G=（V,E）是一个图,C为G的导出圈,函数厂：E→｜＋1,0,-1｜,如果对任意e∈E（C）均有∑f（e）≤0成立,则称f为图G的一个反减圈控制函数,称ymc（G）=max{∑f（e）｜f为G的反减圈控制函数,e∈E（G）}为图G的反减圈控制数．本文给出了图的反减圈控制数的上界和极大平面图及几类特殊图的反减圈控制数．     

图的反符号全控制数

设G=(VE)是一个无孤立顶点的图,一个函数f:V{-1,+1}称为图G的一个反符号全控制函数,如果f(N(v))≤1对任何点v V(G)成立。图G的反符号全控制数记为γrst(G)=max{f(V)|f为图G的一个反符号全控制函数}。该文对图的反符号全控制函数进行了研究,获得了一般图的反符号全控制数的若干界限,确定了完全图和完全二部图的反符号全控制数。     

Self-dual Codes Defined on Factor Graphs

A definition of a self-dual code on graph and a procedure based on factor graphs to judge a self-dual code were presented. Three contributions of this paper were described as follows. To begin with, transform T_ R→L were defined, which was the basis of self-dual codes defined on graphs and played a key role in the paper. The second were that a self-dual code could be defined on factor graph, which was much different from conventional algebraic method. The third was that a factor graph approach to judge a self-dual code was illustrated, which took advantage of duality properties of factor graphs and our proposed transform T_ R→L to offer a convenient and geometrically intuitive process to judge a self-dual code.