有向图上的随机游动

设G=(V,Г)是有向图,G上的随机游动X(G)定义如下:位于某个顶点上的一个粒子将以等概率转移到该顶点的所有后继顶点.令M(j,n)表示随机游动X(G)在前n步内访问顶点j的平均次数,用W(j)表示随机游动X(G)到达顶点j所需要的平均步效.我们对M(j,n)和W(j)的值进行了估计,证明了M(j,n)=O(n),并给出了W(j)的上界.     

New Results on the Queens_n 2 Graph Coloring Problem

For the Queens_n ² graph coloring problems no chromatic numbers are available for n > 9 except where n is not a multiple of 2 or 3. In this paper we propose an exact algorithm that takes advantage of the particular structure of these graphs. The algorithm works on the independent sets of the graph rather than on the vertices to be colored. It combines branch and bound, for independent set assignment, with a clique based filtering procedure. A first experimentation of this approach provided the coloring number values ranging for n = 10 to n = 14.     

Maximal σ‐polynomials of connected 3‐chromatic graphs

In the set of graphs of order n and chromatic number k the following partial order relation is defined. One says that a graph G is less than a graph H if c_i(G) ≤ c_i(H) holds for every i, k ≤ i ≤ n and at least one inequality is strict, where c_i(G) denotes the number of i‐color partitions of G. In this paper the first ? n/2 ? levels of the diagram of the partially ordered set of connected 3‐chromatic graphs of order n are described. © 2003 Wiley Periodicals, Inc. J Graph Theory 43: 210–222, 2003     

A Characterization of the Optimal p-sum Labellingsof Unit Interval Graphs

1.IntroductionGraphsconsideredinthispaperarefiniteandsimple.FOragraphG,V(G)andE(G)denoteitssetofvenicesandedges,respectively.AbijectionwillbecalledalabellingofG.Letpbeapositiverealnumber.ForagivenlabellingTofagraphG,definethegndiscrepencya.(G,ac)ofTasTheobjectiveoftheminimum-p--sumproblemistofindalabelling7ofagraphGsuchthatac(G,T)isassmallaspossible.ThelabellingTminimizinga.(G,7)iscalledanoptimalHsumlabellingofG.Theminimumvalueiscalledtheminimum-psumofG.ItisshowninI31thattheminimum-…     

关于k—消去图的若干新结果

设G是一个图．k是自然数．图G的一个k-正则支撑子图称为G的一个k-因子．若对于G的每条边e．G—e都存在一个k-因子，则称G是一个k-消去图．该文得到了一个图是k-消去图的若干充分条件，推广了文［2—4］中有关结论．     

图的度序列不等式

用代数的方法证明了有关图度序列的几个不等式，并且得到了其相应的极图。     

ContributionsTriangular embeddings of Kn−Km with unboundedly large m

The author has proposed methods of constructing index 2 and 3 current graphs generating triangular embeddings of graphs K_n−K_m with unboundedly large m (as n increases). As a result, triangular embeddings of graphs of many families of graphs K_n−K_m with unboundedly large m were constructed. The paper gives a survey of these results and a short explanation of the methods.     

分段函数的分类及分离型分段函数与初等函数之间的关系

将分段函数划分为连结型分段函数 ,分离型分段函数和它们的组合形式三种类型 ,得到了分离型分段函数是初等函数的充分必要条件 ,完整地解决了分离型分段函数与初等函数之间的关系 ,并且给出了初等函数在其任一截取集上的限制函数 (截取函数 )仍然是初等函数的结果     

PANCYCLICITY IN LINE GRAPHS

1IntroductionWeuseBondyandMurtyl3]forterminologyand..ta'ti..notdefinedhereandconsidersimpleconnectedgraphsonly.AcircuitCofagraphGisanontrivialconnectedeuleriansubgraphofG.Aspanningcircuit,orbrieflyS-circuit,ofagraphGisacircuitthatcontainsallvenicesofG.AdominatingcircuitorD-circuitofGisacircuitsuchthateveryedgeofGisincidentwithatleastonevertexofthecircuit.AgraphofordernispancyclicifitcontainsallcyclesoflengthIfor3515n.IfCisacircuitofG,thenP(C)denotesthenumberOfedgesofGincidentwithatleas…