The interlace polynomial of a graph

Motivated by circle graphs, and the enumeration of Euler circuits, we define a one-variable “interlace polynomial” for any graph. The polynomial satisfies a beautiful and unexpected reduction relation, quite different from the cut and fuse reduction characterizing the Tutte polynomial.It emerges that the interlace graph polynomial may be viewed as a special case of the Martin polynomial of an isotropic system, which underlies its connections with the circuit partition polynomial and the Kauffman brackets of a link diagram. The graph polynomial, in addition to being perhaps more broadly accessible than the Martin polynomial for isotropic systems, also has a two-variable generalization that is unknown for the Martin polynomial. We consider extremal properties of the interlace polynomial, its values for various special graphs, and evaluations which relate to basic graph properties such as the component and independence numbers.     

有向图上的随机游动

设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…