Bounds on the number of disjoint spanning trees

It is shown that an n-edge connected graph has at least ?$\text{(n ? 1)}\text{2}$? pairwise edge-disjoint spanning trees. This bound is best possible in general. A maximal planar graph with four or more vertices contains two edge-disjoint spanning trees. For a maximal toroidal graph, this number is three.     

The game of “N questions” on a tree

We consider the minimax number of questions required to determine which leaf in a finite binary tree T your opponent has chosen, where each question may ask if the leaf is in a specified subtree of T. The requisite number of questions is shown to be approximately the logarithm (base &0slash;) of the number of leaves in T as T becomes large, where Ø = 1.61803… is the “golden ratio”. Specifically, q questions are sufficient to reduce the number of possibilities by a factor of $\text{2}\text{F}{}_{\mathrm{q+3}}$ (where F, is the ith Fibonacci number), and this is the best possible.     

The average height of planted plane trees with M leaves

The number of planted plane trees with n nodes, m leaves, and height h is computed. Assuming that all n-node planted plane trees with m leaves are equally likely, it is shown that the average height $\text{h}\text{(n, m)}$ is asymptotically given for all ε > 0 and fixed $\text{? =}\text{m}\text{n}$, 0 < ? < 1, by

$\text{h}\text{(n,m)=(φn(ρ}{}^{-1}\text{? 1))}{}^{\mathrm{<mtext>1</mtext><mtext>2</mtext>}}\text{+ 1.5 ? ρ}{}^{-1}\text{+ O(}\text{ln}\text{(n)}\text{n}{}^{\mathrm{<mtext>1</mtext><mtext>2-\epsilon </mtext>}}\text{)}$

     

On the trace of finite sets

For a family $\text{T}$ of subsets of an n-set X we define the trace of it on a subset Y of X by T_$\text{T}$(Y) = {F∩Y:F?$\text{T}$}. We say that (m,n) → (r,s) if for every $\text{T}$ with |$\text{T| ?m}$ we can find a Y?X|Y| = s such that |T_$\text{T}$(Y)| ? r. We give a unified proof for results of Bollobàs, Bondy, and Sauer concerning this arrow function, and we prove a conjecture of Bondy and Lovász saying $\text{(?}\text{n}{}^2\text{4}\text{? + n + 2,n)→ (3,7)}$, which generalizes Turán's theorem on the maximum number of edges in a graph not containing a triangle.     

On the enumeration of finite maximal connected topologies

A connected topology $\text{T}$ is said to be maximal connected if $\text{U}$ strictly finer than $\text{T}$ implies that $\text{U}$ is disconnected. In this paper, it is shown that the number of homeomorphism classes of maximal connected topologies defined on a set with n points is equal to twice the number of n point trees minus the number of n point trees possessing a symmetry line. An enumeration of a class called critical connected topologies, which includes the maximal connected spaces is then carried out with the help of Pólya's theorem. Another result is that a chain of connected n point T₀ topologies, linearly ordered by strict fineness, can contain a maximum of $\text{1}\text{2}\text{(n}{}^2\text{? 3n + 4)}$ topologies, and, moreover, this number is the best possible upper bound for the length of such a chain.     

The second largest eigenvalue of a tree

Denote by λ₂(T) the second largest eigenvalue of a tree T. An easy algorithm is given to decide whether λ₂(T)?λ for a given number λ, and a structure theorem for trees withλ₂(T)?λ is proved. Also, it is shown that a tree T with n vertices has $\text{λ}{}_2\text{(T)?lsqb}\text{(n?3)}\text{2}\text{rsqb}{}^{\mathrm{<mtext>1</mtext><mtext>2</mtext>}}$; this bound is best possible for odd n.     

Bounds for sorting by prefix reversal

For a permutation σ of the integers from 1 to n, let ?(σ) be the smallest number of prefix reversals that will transform σ to the identity permutation, and let ?(n) be the largest such ?(σ) for all σ in (the symmetric group) S_n. We show that $\text{?(n)?}\text{(5n+5)}\text{3}$, and that $\text{?(n)?}\text{17n}\text{16}$ for n a multiple of 16. If, furthermore, each integer is required to participate in an even number of reversed prefixes, the corresponding function g(n) is shown to obey $\text{3n}\text{2?1}\text{?g(n)?2n+3}$.     

On a conjecture of bondy

Bondy conjectured [1] that: if G is a k-connected graph, where k ≥ 2, such that the degree-sum of any k + 1 independent vertices is at least m, then G contains a cycle of length at least: $\text{Min}\text{(}\text{2m}\text{(k + 1)}\text{, n)}$ (n denotes the order of G). We prove here that this result is true.     

On a set puncturing problem

It is established that the maximum number of points required to puncture 3n sets of probability $\text{2}\text{3n}$ is 2n, as had been conjectured. In fact, for 1 ≤ m ≤ n, a family of m sets of probability $\text{2}\text{n}$ can be punctured using no more than $\text{min}\text{(m,[}\text{(n + m)}\text{3}\text{])}$ points. The more general statement that (k + 1)n sets of probability $\text{k}\text{(k + 1)n}$ require at most 2n points for puncturing is shown to be false already for k = 3.     

On the average shape of monotonically labelled tree structures

Let $\text{B}$_k denote one of the families of binary trees, t-aray trees (t> 2) or ordered trees with nodes labelled monotonically by elements of {1 < 2 < ? < k}. The average height of the j-th leaf of the trees of $\text{B}$_k with exactly n nodes is shown to converge to a finite limit (depending on k and j) for n → ∞. The limit is determined explicitly for small values of k and its asymptotic behaviour in j and k is investigated. Some recent results on the average shape of rooted tree structures appear as special cases.     

On subgraph number independence in trees

For finite graphs F and G, let N_F(G) denote the number of occurrences of F in G, i.e., the number of subgraphs of G which are isomorphic to F. If $\text{F}$ and $\text{G}$ are families of graphs, it is natural to ask then whether or not the quantities N_F(G), F∈$\text{F}$, are linearly independent when G is restricted to $\text{G}$. For example, if $\text{F}$ = {K₁, K₂} (where K_n denotes the complete graph on n vertices) and $\text{F}$ is the family of all (finite) trees, then of course N_K1(T) ? N_K2(T) = 1 for all T∈$\text{F}$. Slightly less trivially, if $\text{F}$ = {S_n: n = 1, 2, 3,…} (where S_n denotes the star on n edges) and $\text{G}$ again is the family of all trees, then Σ_n=1^∞(?1)ⁿ⁺¹N_Sn(T)=1 for all T∈$\text{G}$. It is proved that such a linear dependence can never occur if $\text{F}$ is finite, no F∈$\text{F}$ has an isolated point, and $\text{G}$ contains all trees. This result has important applications in recent work of L. Lovász and one of the authors (Graham and Lovász, to appear).     

The voltage and current transfer ratios of RLC operator networks

The subject of this work is the voltage and current transfer ratios of three-terminal networks having no mutual coupling and whose impedances are analytic functions taking their values in an abelian self-adjoint algebra of bounded linear operators on a Hilbert space. Each such value is also assumed to be invertible. It is shown that these ratios have the form [I + A(ζ)]^?1, where, for each ζ in a sufficiently small open cone in the right-half complex plane with apex at the origin and the real axis as its bisector, the numerical range of A(ζ) is contained in a compact subset of the open right-half plane. This implies that the ratios are strictly contractive for each ζ in the cone. The angle of the cone is $\text{π}\text{(2k + 2)}$, where k is the number of internal nodes of a certain “surrogate” network; this result is best possible. For two-terminal-pair networks the ratios are shown to be strictly contractive for each ζ in a similar cone with angle $\text{π}\text{(2k + 4)}$.     

Extremal values of the interval number of a graph,II

It is shown that the interval number of a graph on n vertices is at most $\text{[}\text{1}\text{4}\text{(n+1)]}$, and this bound is best possible. This means that we can represent any graph on n vertices as an intersection graph in which the sets assigned to the vertices each consist of the union of at most $\text{[}\text{1}\text{4}\text{(n+1)]}$ finite closed intervals on the real line. This upper bound is attained by the complete bipartite graph K_[n/2],[n/2].     

A Euler-Poincaré characteristic for the open set lattices of finite topologies

Let $\text{T}$ be a finite topology. If P and Q are open sets of $\text{T}$ (Q may be the null set) then P is a minimal cover of Q provided Q ? P and there does not exist any open set R of $\text{T}$ such that Q ? R ? P. A subcollection $\text{D}$ of the open sets of $\text{T}$ is termed an i-discrete collection of $\text{T}$ provided $\text{D}$ contains every open O ∈ $\text{T}$ with the property that ? $\text{D}$ ? O ? ? $\text{D}$, $\text{D}$ contains exactly i minimal covers of ? $\text{D}$, and provided ?$\text{D}$ = ?{O | O ∈ $\text{D}$ and O is a minimal cover of ? $\text{D}$}. A single open set is a O-discrete collection. The number of distinct i-discrete collections of $\text{T}$ is denoted by p($\text{T}$, i). If there does not exist any i-discrete collection then p($\text{T}$,i) = 0, and this happens trivially for the case when i is greater than the number of points on which $\text{T}$ is defined. The object of this article is to establish the theorem: For any finite topology $\text{T}$, the quantity E($\text{T}$) = Σ_{i = 0}^∞ (?1)ⁱp($\text{T}$, i) = 1.     

On the maximum cardinality of a consistent set of arcs in a random tournament

For any tournament T on n vertices, let h(T) denote the maximum number of edges in the intersection of T with a transitive tournament on the same vertex set. Sharpening a previous result of Spencer, it is proved that, if T_n denotes the random tournament on n vertices, then, $\text{P}$$\text{(h(T}{}_{\mathrm{n}}\text{) ≤}\text{1}\text{2}\text{(}{}_2{}^{\mathrm{n}}\text{) + 1.73n}{}^{\mathrm{<mtext>3</mtext><mtext>2</mtext>}}\text{) → 1}$ as n → ∞.     

On the number of conjugacy classes in SL(2,Z)

Let $\text{H}\text{(t)}$ be the number of conjugacy classes of elements in SL(2, $\text{L}$) with trace t, and let $\text{h}\text{(n)}$ be the number of equivalence classes of binary quadratic forms with discriminant n. Then for t≠±2, $\text{H}\text{(t)=}\text{h}\text{(t}{}^2\text{?4)}$. For all real θ > 0 there is a T(θ) such that whenever |t|>T(θ), $\text{H}\text{(t)>|t|}{}^{\mathrm{1?\theta }}$. There is a c>0 such that for those t such that t²?4 is squarefree, $\text{H}\text{(t)≤c|t|}$.     

Degrees and cycles in digraphs

In this article, we give conditions on the total degrees of the vertices in a strong digraph implying the existence of a cycle of length at least $\text{?}\text{(n?1)}\text{h}\text{? + 1}$, where n is the number of vertices of the graph and h an integer, 1?h?n?1. The same conditions imply the existence of a path of length $\text{?}\text{(n?1)}\text{h}\text{? + ?}\text{(n?2)}\text{h}\text{?}$. In the case of strong oriented graphs (antisymmetric digraphs) we improve these conditions. In both cases, we show that the given conditions are the best possible.     

Tutte polynomials for trees

We define two two-variable polynomials for rooted trees and one two-variable polynomial for unrooted trees, all of which are based on the coranknullity formulation of the Tutte polynomial of a graph or matroid. For the rooted polynomials, we show that the polynomial completely determines the rooted tree, i.e., rooted trees T₁ and T₂ are isomorphic if and only if f(T₁) = f(T₂). The corresponding question is open in the unrooted case, although we can reconstruct the degree sequence, number of subtrees of size k for all k, and the number of paths of length k for all k from the (unrooted) polynomial. The key difference between these three polynomials and the standard Tutte polynomial is the rank function used; we use pruning and branching ranks to define the polynomials. We also give a subtree expansion of the polynomials and a deletion-contraction recursion they satisfy.     

On monotone functions of tree structures

Let T be a rooted tree structure with n nodes a₁,…,a_n. A function f: {a₁,…,a_n} into {1 < ? < k} is called monotone if whenever a_i is a son of a_j, then f(a_i) ≥ f(a_j). The average number of monotone bijections is determined for several classes of tree structures. If k is fixed, for the average number of monotone functions asymptotic equivalents of the form c · ?^?nn^{?$\text{3}\text{2}$} (n → ∞) are obtained for several classes of tree structures.     

Spheres tangent to all the faces of a simplex

There are at most 2ⁿ spheres tangent to all n + 1 faces of an n-simplex. It has been shown that the minimum number of such spheres is $\text{2}{}^{\mathrm{n}}\text{? c(n,}\text{1}\text{2}\text{(n + 1))}$ if n is odd and $\text{2}{}^{\mathrm{n}}\text{? c(n,}\text{1}\text{2}\text{(n + 1))}$ if n is even. The object of this note is to show that this result is a consequence of a theorem in graph theory.