A Note on Caterpillar-Embeddings with No Two Parallel Edges

Let G be a set of n points in general position (i.e., no three points are on a line) in the plane, and let C be a caterpillar on n vertices. We show that one can always find a rectilinear embedding of C in the plane such that the vertices of C are the points of G and no two edges of C go to parallel segments. This proves a conjecture of Robert E. Jamison.     

Enumeration of Full Graphs: Onset of the Asymptotic Region

A full graph on n vertices, as defined by Fulkerson, is a representation of the intersection and containment relations among a system of n sets. It has an undirected edge between vertices representing intersecting sets and a directed edge from a to b if the corresponding set A contains B;. Kleitman, Lasaga, and Cowen gave a unified argument to show that asymptotically, almost all full graphs can be obtained by taking an arbitrary undirected graph on the n vertices, distinguishing a clique in this graph, which need not be maximal, and then adding directed edges going out from each vertex in the clique to all vertices to which there is not already an existing undirected edge. Call graphs of this type members of the dominant class. This article obtains the first upper and lower bounds on how large n has to be, so that the asymptotic behavior is indeed observed. It is shown that when n > 170, the dominant class predominates, while when n < 17, the full graphs in the dominant class compose less than half of the total number of realizable full graphs on n vertices.     

The number of rounds needed to exchange information within a graph

In [3] Cederbaum proposes the problem of finding a labelling of a connected graph G which minimizes the number of rounds needed to exchange information between all the points, where a round consists of the vertices of G each broadcasting once in order of their labels. In this paper we give a complete solution to the problem.     

Some Optimization Problems with Bulk-Service Queues

An optimal control problem for a single bulk-service queue is considered. Theorems that characterize the optimal control strategy in some circumstances are proved; they complement earlier results by Deb and Serfozo for a comparable problem. Most of the analysis uses direct probabilistic reasoning rather than specialized methods such as dynamic programming. Some illustrative examples are presented.     

On cross-bandwidth

The notion of cross-bandwidth is introduced, and it is shown that any graph that is suitably contractible to a k-connected graph has cross-bandwidth at least k. The contracted edges must induce in the original graph a subgraph of maximum degree at most one. This is used to resolve a conjecture of Erdös and Chinn on the bandwidth of certain graphs.     

Spanning trees with many leaves in cubic graphs

For a connected graph G let L(G) denote the maximum number of leaves in any spanning tree of G. We give a simple construction and a complete proof of a result of Storer that if G is a connected cubic graph on n vertices, then L(G) ? [(n/4) + 2], and this is best possible for all (even) n. The main idea is to count the number of “dead leaves” as the tree is being constructed. This method of amortized analysis is used to prove the new result that if G is also 3-connected, then L(G) ? [(n/3) + (4/3)], which is best possible for many n. This bound holds more generally for any connected cubic graph that contains no subgraph K₄ - e. The proof is rather elaborate since several reducible configurations need to be eliminated before proceeding with the many tricky cases in the construction.     

Further results on the Aanderaa-Rosenberg conjecture

Some results on the “evasiveness” of graph properties are obtained, extending the work of Rivest and Vuillemin. In particular, it is shown that any nontrivial monotone graph property on n vertices is at least $\text{n}{}^2\text{9}\text{-}\text{evasive}$; particular stronger results are obtained for values of n that are powers of primes less than 14. A new result allowing interpolation among n values is obtained, as are some stronger results on restricted classes of properties.