On CCE graphs of doubly partial orders

Let D be a digraph. The competition-common enemy graph (CCE graph) of D has the same set of vertices as D and an edge between vertices u and v if and only if there are vertices w and x in D such that (w,u), (w,v), (u,x), and (v,x) are arcs of D. We call a graph a CCE graph if it is the CCE graph of some digraph. In this paper, we show that if the CCE graph of a doubly partial order does not contain C₄ as an induced subgraph, it is an interval graph. We also show that any interval graph together with enough isolated vertices is the CCE graph of some doubly partial order.     

Distributive lattices of numberings

We study into a semilattice of numberings generated by a given fixed numbering via operations of completion and taking least upper bounds. It is proved that, except for the trivial cases, this semilattice is an infinite distributive lattice every principal ideal in which is finite. The least upper and the greatest lower bounds in the semilattice are invariant under extensions in the semilattice of all numberings. Isomorphism types for the semilattices in question are in one-to-one correspondence with pairs of cardinals the first component of which is equal to the cardinality of a set of non-special elements, and the second — to the cardinality of a set of special elements, of the initial numbering. Supported by INTAS grant No. 00-429. __________ Translated from Algebra i Logika, Vol. 46, No. 1, pp. 83–102, January–February, 2007.     

LA RECONSTRUCTION DES TOURNOIS SANS DIAMANT

We prove that if T is a tournament of order n > 6 in which any 4-sub-tournament is hamiltonian or transitive, then T is reconstructible in the sense of Ulam.     

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     

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-树是严格边韧性度图,并找到了边韧性度与较高阶的边坚韧度和边坚韧度之间的关系.     

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

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

A general Hsu-Robbins-Erdős Type estimate of tail probabilities of sums of independent identically distributed random variables

Periodica Mathematica Hungarica - Let X 1,X 2,... be a sequence of independent and identically distributed random variables, and put % MATHTYPE!MTEF!2!1!+-%...     

有向图上的随机游动

设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)的上界.