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     

Crossover Critical Behavior in the Three-Dimensional Ising Model

The character of critical behavior in physical systems depends on the range of interactions. In the limit of infinite range of the interactions, systems will exhibit mean-field critical behavior, i.e., critical behavior not affected by fluctuations of the order parameter. If the interaction range is finite, the critical behavior asymptotically close to the critical point is determined by fluctuations and the actual critical behavior depends on the particular universality class. A variety of systems, including fluids and anisotropic ferromagnets, belongs to the three-dimensional Ising universality class. Recent numerical studies of Ising models with different interaction ranges have revealed a spectacular crossover between the asymptotic fluctuation-induced critical behavior and mean-field-type critical behavior. In this work, we compare these numerical results with a crossover Landau model based on renormalization-group matching. For this purpose we consider an application of the crossover Landau model to the three-dimensional Ising model without fitting to any adjustable parameters. The crossover behavior of the critical susceptibility and of the order parameter is analyzed over a broad range (ten orders) of the scaled distance to the critical temperature. The dependence of the coupling constant on the interaction range, governing the crossover critical behavior, is discussed.     

Geometric separation and exact solutions for the parameterized independent set problem on disk graphs

We consider the parameterized problem, whether for a given set  of n disks (of bounded radius ratio) in the Euclidean plane there exists a set of k non-intersecting disks. For this problem, we expose an algorithm running in time that is—to our knowledge—the first algorithm with running time bounded by an exponential with a sublinear exponent. For λ-precision disk graphs of bounded radius ratio, we show that the problem is fixed parameter tractable with a running time  . The results are based on problem kernelization and a new “geometric ( -separator) theorem” which holds for all disk graphs of bounded radius ratio. The presented algorithm then performs, in a first step, a “geometric problem kernelization” and, in a second step, uses divide-and-conquer based on our new “geometric separator theorem.”     

A note on the critical points of equilibrium paths in imperfect structures

In a recent work (Int. J. Solids Struct. 37 (2000) 1561) by one of the authors, an extended system for calculating critical points of equilibrium paths in imperfect structures was presented. However, the extremum nature of these points was not analyzed explicitly in that paper. In this note, we will fill in the gap and establish a sufficient condition for determining the buckling strength of imperfect structures.     

Use of dynamic trees in a network simplex algorithm for the maximum flow problem

Goldfarb and Hao (1990) have proposed a pivot rule for the primal network simplex algorithm that will solve a maximum flow problem on ann-vertex,m-arc network in at mostnm pivots and O(n ² m) time. In this paper we describe how to extend the dynamic tree data structure of Sleator and Tarjan (1983, 1985) to reduce the running time of this algorithm to O(nm logn). This bound is less than a logarithmic factor larger than those of the fastest known algorithms for the problem. Our extension of dynamic trees is interesting in its own right and may well have additional applications.Research partially supported by a Presidential Young Investigator Award from the National Science Foundation, Grant No. CCR-8858097, an IBM Faculty Development Award, and AT&T Bell Laboratories.Research partially supported by the Office of Naval Research, Contract No. N00014-87-K-0467.Research partially supported by the National Science Foundation, Grant No. DCR-8605961, and the Office of Naval Research, Contract No. N00014-87-K-0467.     

Constructing two-weight codes with prescribed groups of automorphisms

We construct new linear two-weight codes over the finite field with q elements. To do so we solve the equivalent problem of finding point sets in the projective geometry with certain intersection properties. These point sets are in bijection to solutions of a Diophantine linear system of equations. To reduce the size of the system of equations we restrict the search for solutions to solutions with special symmetries.Two-weight codes can be used to define strongly regular graphs. We give tables of the two-weight codes and the corresponding strongly regular graphs. In some cases we find new distance-optimal two-weight codes and also new strongly regular graphs.     

θ*r,s,t-图与唯一2-列表染色图的特征化

如果一个图G存在一个k-列表安排使得G具有一个唯一列表染色,则称 G是唯一列表可染色图,简称UkLC图．我们称图G具有M(k)性质当且仅当G不 是UkLC图．本文在借鉴θr,s,t-图概念的基础上引入θr,s,t-图的定义,并证明:除了 r=s=t=2以外,θr,s,t-图都是U2LC图．利用如上结果我们给出M．Mahdian and E．S．Mahmoodian对U2LC图所作特征化的一个简单证明．     

Statistical mechanics of warm and cold unfolding in proteins

We present a statistical mechanics treatment of the stability of globular proteins which takes explicitly into account the coupling between the protein and water degrees of freedom. This allows us to describe both the cold and the warm unfolding, thus qualitatively reproducing the known thermodynamics of proteins. Received: 19 March 1998 / Revised and Accepted: 25 May 1998     

Norms and perfect graphs

The weak Berge hypothesis states that a graph is perfect if and only if its complement is perfect. Previous proofs of this hypothesis have used combinatorial or polyhedral methods.In this paper, the concept of norms related to graphs is used to provide an alternative proof for the weak Berge hypothesis.This is a written account of an invited lecture delivered by the second author on occasion of the 12. Symposium on Operations Research, Passau, 9.–11. 9. 1987.     

Circuit-switching networks with FIFO plus justifying blockout service on infinite graphs

A class of circuit-switching open queueing networks is discussed. The main result of the paper is that if extra message flows are not too intensive and the path distribution is mainly concentrated on the paths of (graph) distance 1 (nearest neighbour connections), then the network has a unique stationary working regime, no matter how large the configuration graph of the network is. Standard properties of this regime are established such as decay of correlation and continuity.