Monotone paths in ordered graphs

LetV _fin andE _fin resp. denote the classes of graphsG with the property that no matter how we label the vertices (edges, resp.) ofG by members of a linearly ordered set, there will exist paths of arbitrary finite lengths with monotonically increasing labels. The classesV _inf andE _inf are defined similarly by requiring the existence of an infinite path with increasing labels. We proveE _inf ⫋V _inf ⫋V _fin ⫋E _fin. Finally we consider labellings by positive integers and characterize the class corresponding toV _inf.     

Disjoint shortest paths in graphs

It is an interesting problem that how much connectivity ensures the existence ofn disjoint paths joining givenn pairs of vertices, but to get a sharp bound seems to be very difficult. In this paper, we study how muchgeodetic connectivity ensures the existence ofn disjointgeodesics joining givenn pairs of vertices, where a graph is calledk-geodetically connected if the removal of anyk−1 vertices does not change the distance between any remaining vertices.     

A note on monotone paths in labeled graphs

We characterize countable graphs with the property that every one-to-one labeling of edges by positive integers admits a monotone path.     

Packing paths in planar graphs

A generalization of P. Seymour's theorem on planar integral 2-commodity flows is given when the underlying graphG together with the demand graphH (a graph having edges that connect the corresponding terminal pairs) form a planar graph and the demand edges are on two faces ofG.     

Long paths with endpoints in given vertex-subsets of graphs

Let G=(V,E) be a connected graph of order n, t a real number with t?1 and M⊆V(G) with . In this paper, we study the problem of some long paths to maintain their one or two different endpoints in M. We obtain the following two results: (1) for any vertex v∈V(G), there exists a vertex u∈M and a path P with the two endpoints v and u to satisfy , , d_G(u)+1-t}; (2) there exists either a cycle C to cover all vertices of M or a path P with two different endpoints u₀ and u_p in M to satisfy , where .     

On the sum of the reciprocals of cycle lengths in sparse graphs

For a graphG let ℒ(G)=Σ{1/k contains a cycle of lengthk}. Erdős and Hajnal [1] introduced the real functionf(α)=inf {ℒ (G)|E(G)|/|V(G)|≧α} and suggested to study its properties. Obviouslyf(1)=0. We provef (k+1/k)≧(300k logk)⁻¹ for all sufficiently largek, showing that sparse graphs of large girth must contain many cycles of different lengths.     

Some large deviation results for sparse random graphs

Summary. We obtain a large deviation principle (LDP) for the relative size of the largest connected component in a random graph with small edge probability. The rate function, which is not convex in general, is determined explicitly using a new technique. The proof yields an asymptotic formula for the probability that the random graph is connected. We also present an LDP and related result for the number of isolated vertices. Here we make use of a simple but apparently unknown characterisation, which is obtained by embedding the random graph in a random directed graph. The results demonstrate that, at this scaling, the properties `connected' and `contains no isolated vertices' are not asymptotically equivalent. (At the threshold probability they are asymptotically equivalent.) Received: 14 November 1996 / In revised form: 15 August 1997     

The diameter of random regular graphs

We give asymptotic upper and lower bounds for the diameter of almost everyr-regular graph onn vertices (n → ∞).     

Automorphisms of random graphs with specified vertices

Conditions are found under which the expected number of automorphisms of a large random labelled graph with a given degree sequence is close to 1. These conditions involve the probability that such a graph has a given subgraph. One implication is that the probability that a random unlabelledk-regular simple graph onn vertices has only the trivial group of automorphisms is asymptotic to 1 asn → ∞ with 3≦k=O(n ^1/2−c). In combination with previously known results, this produces an asymptotic formula for the number of unlabelledk-regular simple graphs onn vertices, as well as various asymptotic results on the probable connectivity and girth of such graphs. Corresponding results for graphs with more arbitrary degree sequences are obtained. The main results apply equally well to graphs in which multiple edges and loops are permitted, and also to bicoloured graphs. Research of the second author supported by U. S. National Science Foundation Grant MCS-8101555, and by the Australian Department of Science and Technology under the Queen Elizabeth II Fellowships Scheme. Current address: Mathematics Department, University of Auckland, Auckland, New Zealand.     

Constructing disjoint paths on expander graphs

In a typical parallel or distributed computation model processors are connected by a spars interconnection network. To establish open-line communication between pairs of processors that wish to communicate interactively, a set of disjoint paths has to be constructed on the network. Since communication needs vary in time, paths have to be dynamically constructed and destroyed.We study the complexity of constructing disjoint paths between given pairs of vertices on expander interconnection graphs. These graphs have been shown before to possess desirable properties for other communication tasks.We present a sufficient condition for the existence ofKn ^Q edge-disjoint paths connecting any set ofK pairs of vertices on an expander graph, wheren is the number of vertices and<1 is some constant. We then show that the computational problem of constructing these paths lies in the classes Deterministic-P and Random-P C.Furthermore, we show that the set of paths can be constructed in probabilistic polylog time in the parallel-distributed model of computation, in which then participating processors reside in the nodes of the communication graph and all communication is done through edges of the graph. Thus, the disjoint paths are constructed in the very computation model that uses them.Finally, we show how to apply variants of our parallel algorithms to find sets ofvertex-disjoint paths when certain conditions are satisfied.Supported in part by a Weizmann fellowship and by contract ONR N00014-85-C-0731.     

The longest path in a random graph

A random graph with (1+ε)n/2 edges contains a path of lengthcn. A random directed graph with (1+ε)n edges contains a directed path of lengthcn. This settles a conjecture of Erdõs.     

Sandwiching random graphs: universality between random graph models

The goal of this paper is to establish a connection between two classical models of random graphs: the random graph G(n,p) and the random regular graph G_d(n). This connection appears to be very useful in deriving properties of one model from the other and explains why many graph invariants are universal. In particular, one obtains one-line proofs of several highly non-trivial and recent results on G_d(n).     

The asymptotic behaviour of lovász’ ϑ function for random graphs

We show that for a random graph Lovász’ ϑ function is of order √n.     

Longest paths in digraphs

In this paper, we give a sufficient condition on the degrees of the vertices of a digraph to insure the existence of a path of given length, and we characterize the extremal graphs.     

The Markov chain asymptotics of random mapping graphs

In this paper the limit behavior of random mappings with n vertices is investigated. We first compute the asymptotic probability that a fixed class of finite non-intersected subsets of vertices are located in different components and use this result to construct a scheme of allocating particles with a related Markov chain. We then prove that the limit behavior of random mappings is actually embedded in such a scheme in a certain way. As an application, we shall give the asymptotic moments of the size of the largest component.     

An algorithm for finding hamilton paths and cycles in random graphs

This paper describes a polynomial time algorithm HAM that searches for Hamilton cycles in undirected graphs. On a random graph its asymptotic probability of success is that of the existence of such a cycle. If all graphs withn vertices are considered equally likely, then using dynamic programming on failure leads to an algorithm with polynomial expected time. The algorithm HAM is also used to solve the symmetric bottleneck travelling salesman problem with probability tending to 1, asn tends to ∞. Various modifications of HAM are shown to solve several Hamilton path problems. Supported by NSF Grant MCS 810 4854.     

Cycles in weighted graphs

A weighted graph is one in which each edgee is assigned a nonnegative numberw(e), called the weight ofe. The weightw(G) of a weighted graphG is the sum of the weights of its edges. In this paper, we prove, as conjectured in [2], that every 2-edge-connected weighted graph onn vertices contains a cycle of weight at least 2w(G)/(n–1). Furthermore, we completely characterize the 2-edge-connected weighted graphs onn vertices that contain no cycle of weight more than 2w(G)/(n–1). This generalizes, to weighted graphs, a classical result of Erds and Gallai [4].