Linear Ramsey numbers of sparse graphs

The Ramsey number R(G₁,G₂) of two graphs G₁ and G₂ is the least integer p so that either a graph G of order p contains a copy of G₁ or its complement G^c contains a copy of G₂. In 1973, Burr and Erd?s offered a total of $25 for settling the conjecture that there is a constant c = c(d) so that R(G,G)≤ c|V(G)| for all d‐degenerate graphs G, i.e., the Ramsey numbers grow linearly for d‐degenerate graphs. We show in this paper that the Ramsey numbers grow linearly for degenerate graphs versus some sparser graphs, arrangeable graphs, and crowns for example. This implies that the Ramsey numbers grow linearly for degenerate graphs versus graphs with bounded maximum degree, planar graphs, or graphs without containing any topological minor of a fixed clique, etc. © 2005 Wiley Periodicals, Inc. J Graph Theory     

完全二部图Ka,b的迭线图L^m（Ka，b）的谱特征

本证明了当(a，b)不属于{(1，8)，(2，4)，(3，6)，(4，4)，(2s^2-s，2s^2 s))时，L^m(Ka,b)以谱为特征，其中a≤b，s≥2．     

(a,b,n)-临界图的几个充分条件

设G是一个图 .设g和f是两个定义在V(G)上的整值函数使得对V(G)所有顶点x有g(x) ≤f(x) .图G被称为 (g ,f,n) 临界图 ,如果删去G的任意n个顶点后的子图都含有G的 (g ,f) 因子 .本文给出了图是 (a ,b ,n) 临界图几个充分条件 ,即度和邻域条件 .进一步指出这些条件是最佳的 .     

Large families of mutually embeddable vertex‐transitive graphs

For each infinite cardinal κ, we give examples of 2^κ many non‐isomorphic vertex‐transitive graphs of order κ that are pairwise isomorphic to induced subgraphs of each other. We consider examples of graphs with these properties that are also universal, in the sense that they embed all graphs with smaller orders as induced subgraphs. © 2003 Wiley Periodicals, Inc. J Graph Theory 43: 99–106, 2003     

图的边韧性度

文[1]中,定义图G(V,E)的边韧性度定义为min{(|S|+T(G-S))/(ω(G-S)):S?E(G)},这里,T-(G-S)和ω(G-S)分别表示G-S中最大分支的顶点数和连通分支数.这是一个能衡量网络图稳定性较好的参数,因为它不仅考虑到了图G-S的分支数也考虑到了它的阶数.在以前的工作中,作者得到了边韧性度图的一个充要条件.利用这些结果证明了K-树是严格边韧性度图,并找到了边韧性度与较高阶的边坚韧度和边坚韧度之间的关系.     

网络图在产品配送中的应用

面对多样化的市场需求，企业的销售渠道也变得异常复杂，利用网络图可以简化实际问题，并能形象地描述它。本根据网络知识建立了产品分销模型，探求企业在市场需求固定和随机时的最优收益。最后，章还进行实例验算，并做出相应的结果分析。     

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.