Cyclic bi‐embeddings of Steiner triple systems on 12s + 7 points

A cyclic face 2‐colourable triangulation of the complete graph K_n in an orientable surface exists for n ≡ 7 (mod 12). Such a triangulation corresponds to a cyclic bi‐embedding of a pair of Steiner triple systems of order n, the triples being defined by the faces in each of the two colour classes. We investigate in the general case the production of such bi‐embeddings from solutions to Heffter's first difference problem and appropriately labelled current graphs. For n = 19 and n = 31 we give a complete explanation for those pairs of Steiner triple systems which do not admit a cyclic bi‐embedding and we show how all non‐isomorphic solutions may be identified. For n = 43 we describe the structures of all possible current graphs and give a more detailed analysis in the case of the Heawood graph. © 2002 Wiley Periodicals, Inc. J Combin Designs 10: 92–110, 2002; DOI 10.1002/jcd.10001     

Random walks on highly symmetric graphs

We consider uniform random walks on finite graphs withn nodes. When the hitting times are symmetric, the expected covering time is at least 1/2n logn-O(n log logn) uniformly over all such graphs. We also obtain bounds for the covering times in terms of the eigenvalues of the transition matrix of the Markov chain. For distance-regular graphs, a general lower bound of (n-1) logn is obtained. For hypercubes and binomial coefficient graphs, the limit law of the covering time is obtained as well.     

生石灰颗粒中温脱硫过程数值计算

本文采用晶粒模型对中温条件下单颗粒石灰石脱硫过程进行数值模拟。利用已有文献数据、电子显微镜及TGA实验数据确定模型中化学反应动力学以及物性参数。计算结果与TGA实验结果符合较好,表明脱硫模型可直接应用于中温条件下石灰石脱硫过程的数值预报与分析。     

A technique for multicoloring triangle-free hexagonal graphs

In order to avoid interference in cellular telephone networks, sets of radio frequencies are to be assigned to transmitters such that adjacent transmitters are allotted disjoint sets of frequencies. Often these transmitters are laid out like vertices of a triangular lattice in a plane. This problem corresponds to the problem of multicoloring an induced subgraph of a triangular lattice with integer demands associated with each vertex. We deal with the simpler case of triangle-free subgraphs of the lattice. [Frédéric Havet, Discrete Math. 233 (2001) 1–3] uses inductive arguments to prove that triangle-free hexagonal graphs can be colored with colors where ω_d is the maximum demand on a clique in the graph. We give a simpler proof and hope that our techniques can be used to prove the conjecture by [McDiarmid and Reed, Networks Suppl. 36 (2000) 114–117] that these graphs are -multicolorable.     

Menger's theorem for infinite graphs with ends

A well‐known conjecture of Erd?s states that given an infinite graph G and sets A, ? V(G), there exists a family of disjoint A ? B paths ?? together with an A ? B separator X consisting of a choice of one vertex from each path in ??. There is a natural extension of this conjecture in which A, B, and X may contain ends as well as vertices. We prove this extension by reducing it to the vertex version, which was recently proved by Aharoni and Berger. © 2005 Wiley Periodicals, Inc. J Graph Theory 50: 199–211, 2005     

EXPRESSION AND SECRETION OF preS CONTAINING HEPATITIS B SURFACE ANTIGEN IN VACCINIA VIRUS SYSTEM

The expression and secretion of preS containing hepatitis B surface antigen in vaccinia virus system was investigated. The human TK~- 143 cells were infected with the recombinant vaccinia viruses vTMS-1 or vTLS-1. Cells infected with vTMS-1, which contains the preS2+S gene, produced preS2 containing middle HBsAg proteins. Similarly, cells produced preS1 containing large HBsAg proteins upon infection with vTLS-1, which carries the preS1+preS2+S gene. The expression products could be secreted and form 22 nm particles. They reacted specifically with anti-preS1 and/or anti-preS2 monoclonal antibodies, and exhibited pHSA-receptor (for polymerized human serum albumin) activity. In addition, the major S components of hepatitis B surface antigen were also present in the products expressed by vTMS-1 and vTLS-1.     

Regular matroid decomposition via signed graphs

The key to Seymour's Regular Matroid Decomposition Theorem is his result that each 3‐connected regular matroid with no R₁₀‐ or R₁₂‐minor is graphic or cographic. We present a proof of this in terms of signed graphs. © 2004 Wiley Periodicals, Inc. J Graph Theory 48: 74–84, 2005     

Polynomial algorithms that prove an NP-Hard hypothesis implies an NP-hard conclusion

A number of results in hamiltonian graph theory are of the form “ implies ”, where is a property of graphs that is NP-hard and is a cycle structure property of graphs that is also NP-hard. An example of such a theorem is the well-known Chvátal–Erd s Theorem, which states that every graph G with κ is hamiltonian. Here κ is the vertex connectivity of G and is the cardinality of a largest set of independent vertices of G. In another paper Chvátal points out that the proof of this result is in fact a polynomial time construction that either produces a Hamilton cycle or a set of more than κ independent vertices. In this note we point out that other theorems in hamiltonian graph theory have a similar character. In particular, we present a constructive proof of a well-known theorem of Jung (Ann. Discrete Math. 3 (1978) 129) for graphs on 16 or more vertices.     

Lagrangian bounds in multiextremal polynomial and discrete optimization problems

Many polynomial and discrete optimization problems can be reduced to multiextremal quadratic type models of nonlinear programming. For solving these problems one may use Lagrangian bounds in combination with branch and bound techniques. The Lagrangian bounds may be improved for some important examples by adding in a model the so-called superfluous quadratic constraints which modify Lagrangian bounds. Problems of finding Lagrangian bounds as a rule can be reduced to minimization of nonsmooth convex functions and may be successively solved by modern methods of nondifferentiable optimization. This approach is illustrated by examples of solving polynomial-type problems and some discrete optimization problems on graphs.     

Circular flows of nearly Eulerian graphs and vertex‐splitting

The odd edge connectivity of a graph G, denoted by λ_o(G), is the size of a smallest odd edge cut of the graph. Let S be any given surface and ? be a positive real number. We proved that there is a function f_S(?) (depends on the surface S and lim_?→0 f_S(?)=∞) such that any graph G embedded in S with the odd‐edge connectivity at least f_S(?) admits a nowhere‐zero circular (2+?)‐flow. Another major result of the work is a new vertex splitting lemma which maintains the old edge connectivity and graph embedding. © 2002 Wiley Periodicals, Inc. J Graph Theory 40: 147–161, 2002