Unoriented Laplacian maximizing graphs are degree maximal

A connected graph is said to be unoriented Laplacian maximizing if the spectral radius of its unoriented Laplacian matrix attains the maximum among all connected graphs with the same number of vertices and the same number of edges. A graph is said to be threshold (maximal) if its degree sequence is not majorized by the degree sequence of any other graph (and, in addition, the graph is connected). It is proved that an unoriented Laplacian maximizing graph is maximal and also that there are precisely two unoriented Laplacian maximizing graphs of a given order and with nullity 3. Our treatment depends on the following known characterization: a graph G is threshold (maximal) if and only if for every pair of vertices u,v of G, the sets N(u)?{v},N(v)?{u}, where N(u) denotes the neighbor set of u in G, are comparable with respect to the inclusion relation (and, in addition, the graph is connected). A conjecture about graphs that maximize the unoriented Laplacian matrix among all graphs with the same number of vertices and the same number of edges is also posed.     

Reconstructing edge-disjoint paths

For an undirected graph G=(V,E), the edge connectivity values between every pair of nodes of G can be succinctly recorded in a flow-equivalent tree that contains the edge connectivity value for a linear number of pairs of nodes. We generalize this result to show how we can efficiently recover a maximum set of disjoint paths between any pair of nodes of G by storing such sets for a linear number of pairs of nodes. At the heart of our result is an observation that combining two flow solutions of the same value, one between nodes s and r and the second between nodes r and t, into a feasible flow solution of value f between nodes s and t, is equivalent to solving a stable matching problem on a bipartite multigraph.Our observation, combined with an observation of Chazelle, leads to a data structure, which takes O(n^3.5) time to generate, that can construct the maximum number λ(u,v) of edge-disjoint paths between any pair (u,v) of nodes in time O(α(n,n)λ(u,v)n) time.     

Representations of product systems over semigroups and dilations of commuting CP maps

We prove that every pair of commuting CP maps on a von Neumann algebra M can be dilated to a commuting pair of endomorphisms (on a larger von Neumann algebra). To achieve this, we first prove that every completely contractive representation of a product system of C^∗-correspondences over the semigroup N² can be dilated to an isometric (or Toeplitz) representation.     

Connected graphs with a minimal number of spanning trees

The problem studied is the following: Find a simple connected graph G with given numbers of vertices and edges which minimizes the number t_μ(G), the number of spanning trees of the multigraph obtained from G by adding μ parallel edges between every pair of distinct vertices. If G is nearly complete (the number of edges qis ≥(₂^P)?p+2 where p is the number of vertices), then the solution to the minimization problem is unique (up to isomorphism) and the same for all values of μ. The present paper investigates the case whereq<(₂^P)?p+2. In this case the solution is not always unique and there does not always exist a common solution for all values of μ. A (small) class of graphs is given such that for any μ there exists a solution to the problem which is contained in this class. For μ = 0 there is only one graph in the class which solves the problem. This graph is described and the minimum value of t₀(G) is found. In order to derive these results a representation theorem is proved for the cofactors of a special class of matrices which contains the tree matrices associated with graphs.     

The square of a block graph

The square H² of a graph H is obtained from H by adding new edges between every two vertices having distance two in H. A block graph is one in which every block is a clique. For the first time, good characterizations and a linear time recognition of squares of block graphs are given in this paper. Our results generalize several previous known results on squares of trees.     

Large non-planar graphs and an application to crossing-critical graphs

We prove that, for every positive integer k, there is an integer N such that every 4-connected non-planar graph with at least N vertices has a minor isomorphic to K4,k, the graph obtained from a cycle of length 2k+1 by adding an edge joining every pair of vertices at distance exactly k, or the graph obtained from a cycle of length k by adding two vertices adjacent to each other and to every vertex on the cycle. We also prove a version of this for subdivisions rather than minors, and relax the connectivity to allow 3-cuts with one side planar and of bounded size. We deduce that for every integer k there are only finitely many 3-connected 2-crossing-critical graphs with no subdivision isomorphic to the graph obtained from a cycle of length 2k by joining all pairs of diagonally opposite vertices.     

Minimal comparability completions of arbitrary graphs

A transitive orientation of an undirected graph is an assignment of directions to its edges so that these directed edges represent a transitive relation between the vertices of the graph. Not every graph has a transitive orientation, but every graph can be turned into a graph that has a transitive orientation, by adding edges. We study the problem of adding an inclusion minimal set of edges to an arbitrary graph so that the resulting graph is transitively orientable. We show that this problem can be solved in polynomial time, and we give a surprisingly simple algorithm for it. We use a vertex incremental approach in this algorithm, and we also give a more general result that describes graph classes Π for which Π completion of arbitrary graphs can be achieved through such a vertex incremental approach.     

Distance-restricted matching extension in planar triangulations

A graph G is said to have property E(m,n) if it contains a perfect matching and for every pair of disjoint matchings M and N in G with |M|=m and |N|=n, there is a perfect matching F in G such that M⊆F and N∩F=0?. In a previous paper (Aldred and Plummer 2001) [2], an investigation of the property E(m,n) was begun for graphs embedded in the plane. In particular, although no planar graph is E(3,0), it was proved there that if the distance among the three edges is at least two, then they can always be extended to a perfect matching. In the present paper, we extend these results by considering the properties E(m,n) for planar triangulations when more general distance restrictions are imposed on the edges to be included and avoided in the extension.     

Classification theory for non-elementary classes I: The number of uncountable models ofψ ∈L ω_1, ω. Part A

Assuming that 2^Nn < 2^Nn+1 forn < ω, we prove that everyψ ∈L _{ω_1, ω} has many non-isomorphic models of powerN _n for somen>0or has models in all cardinalities. We can conclude that every such Ψ has at least 2 _N 1 non-isomorphic uncountable models. As for the more vague problem of classification, restricting ourselves to the atomic models of some countableT (we can reduce general cases to this) we find a cutting line named “excellent”. Excellent classes are well understood and are parallel to totally transcendental theories, have models in all cardinals, have the amalgamation property, and satisfy the Los conjecture. For non-excellent classes we have a non-structure theorem, e.g., if they have an uncountable model then they have many non-isomorphic ones in someN _n (provided {ie212-7}).     

Rainbow Connection and Graph Products

A path in an edge colored graph G is called a rainbow path if all its edges have pairwise different colors. Then G is rainbow connected if there exists a rainbow path between every pair of vertices of G and the least number of colors needed to obtain a rainbow connected graph is the rainbow connection number. If we demand that there must exist a shortest rainbow path between every pair of vertices, we speak about strongly rainbow connected graph and the strong rainbow connection number. In this paper we study the (strong) rainbow connection number on the direct, strong, and lexicographic product and present several upper bounds for these products that are attained by many graphs. Several exact results are also obtained.     

Periodic solutions of the N-body problem

This paper proves the existence of six new classes of periodic solutions to the N-body problem by small parameter methods. Three different methods of introducing a small parameter are considered and an appropriate method of scaling the Hamiltonian is given for each method. The small parameter is either one of the masses, the distance between a pair of particles or the reciprocal of the distances between one particle and the center of mass of the remaining particles. For each case symmetric and non-symmetric periodic solutions are established. For every relative equilibrium solution of the (N ? 1)-body problem each of the six results gives periodic solutions of the N-body problem. Under additional mild non-resonance conditions the results are roughly as follows. Any non-degenerate periodic solutions of the restricted N-body problem can be continued into the full N-body problem. There exist periodic solutions of the N-body problem, where N ? 2 particles and the center of mass of the remaining pair move approximately on a solution of relative equilibrium and the pair move approximately on a small circular orbit of the two-body problems around their center of mass. There exist periodic solutions of the N-body problem, where one small particle and the center of mass of the remaining N ? 1 particles move approximately on a large circular orbit of the two body problems and the remaining N ? 1 bodies move approximately on a solution of relative equilibrium about their center of mass. There are three similar results on the existence of symmetric periodic solutions.     

On the maximum number of edges in quasi-planar graphs

A topological graph is quasi-planar, if it does not contain three pairwise crossing edges. Agarwal et al. [P.K. Agarwal, B. Aronov, J. Pach, R. Pollack, M. Sharir, Quasi-planar graphs have a linear number of edges, Combinatorica 17 (1) (1997) 1-9] proved that these graphs have a linear number of edges. We give a simple proof for this fact that yields the better upper bound of 8n edges for n vertices. Our best construction with 7n−O(1) edges comes very close to this bound. Moreover, we show matching upper and lower bounds for several relaxations and restrictions of this problem. In particular, we show that the maximum number of edges of a simple quasi-planar topological graph (i.e., every pair of edges have at most one point in common) is 6.5n−O(1), thereby exhibiting that non-simple quasi-planar graphs may have many more edges than simple ones.     

Edge-Ramsey theory

LetK be a configuration, a set of points in some finite-dimensional Euclidean space. Letn andk be positive integers. The notationR(K, n, r) is an abbreviation for the following statement: For everyr-coloring of the points of then-dimensional Euclidean space,R ⁿ , a monochromatic configurationL which is congruent toK exists. A configurationK is Ramsey if the following holds: For every positive integerr, a positive integern=n(K, r) exists such that, for allm≥n, R(K, m, r) holds. A configuration is spherical if it can be embedded in the surface of a sphere inn-space, providedn is sufficiently large. It is relatively easy to show that if a configuration is Ramsey, it must be spherical. Accordingly, a good fraction of the research efforts in Euclidean Ramsey theory is devoted to determining which spherical configurations are Ramsey. It is known that then-dimensional measure polytopes (the higher-dimensional analogs of a cube), then-dimensional simplex, and the regular polyhedra inR ² andR ³ are Ramsey. Now letE denote a set of edges in a configurationK. The pair (K, E) is called an edge-configuration, andR _e (K, E, n, r) is used as an abbreviation for the following statement: For anyr-coloring of the edges ofR ⁿ , there is an edge configuration (L, F) congruent to (K, E) so that all edges inF are assigned the same color. An edge-configuration isedge-Ramsey if, for allr≥1, a positive integern=n(K, E, r) exists so that ifm≥n, the statementR _e (K, E, m, r) holds. IfK is a regular polytope, it is saidK isedge-Ramsey when the configuration determined by the set of edges of minimum length is edge-Ramsey. It is known that then-dimensional simplex is edge-Ramsey and that the nodes of any edge-Ramsey configuration can be partitioned into two spherical sets. Furthermore, the edges of any edge-Ramsey configuration must all have the same length. It is conjectured that the unit square is edge-Ramsey, and it is natural to ask the more general question: Which regular polytopes are edge-Ramsey? In this article it is shown that then-dimensional measure polytope and then-dimensional cross polytope are edge-Ramsey. It is also shown that these two infinite families and then-dimensional simplexes are the only regular edge-Ramsey polytopes, with the possible exceptions of the hexagon and the 24-cell.     

Small Hop-diameter Sparse Spanners for Doubling Metrics

Given a metric M=(V,d), a graph G=(V,E) is a t-spanner for M if every pair of nodes in V has a “short” path (i.e., of length at most t times their actual distance) between them in the spanner. Furthermore, this spanner has a hop diameter bounded by D if every pair of nodes has such a short path that also uses at most D edges. We consider the problem of constructing sparse (1+ε)-spanners with small hop diameter for metrics of low doubling dimension. In this paper, we show that given any metric with constant doubling dimension k and any 0<ε<1, one can find (1+ε)-spanner for the metric with nearly linear number of edges (i.e., only O(nlog ^* n+n ε ^−O(k)) edges) and constant hop diameter; we can also obtain a (1+ε)-spanner with linear number of edges (i.e., only n ε ^−O(k) edges) that achieves a hop diameter that grows like the functional inverse of Ackermann’s function. Moreover, we prove that such tradeoffs between the number of edges and the hop diameter are asymptotically optimal. The conference version of the paper appeared in ACM-SIAM SODA 2006. This research of T.-H.H. Chan was done while the author was at Carnegie Mellon University and was partly supported by the NSF grant CCR-0122581 (the ALADDIN project), the NSF CAREER award CCF-0448095, and by an Alfred P. Sloan Fellowship. This research of A. Gupta was partly supported by the NSF grant CCR-0122581 (the ALADDIN project), the NSF CAREER award CCF-0448095, and by an Alfred P. Sloan Fellowship.     

Threshold phenomena in the transient behaviour of Markovian models of communication networks and databases

This paper accompanies a talk given at the Workshop on Mathematical Methods in Queueing Networks held at the Mathematical Sciences Institute at Cornell University in August 1988. In earlier work we had exhibited a threshold phenomenon in the transient behaviour of a closed network of ./M/1 nodes: When there areN customers circulating, and the initial state isx, letd _x ^N (t) denote the total variation distance between the distribution at timet and the stationary distribution. Let d^N(t) = max _x d _x ^N (t). We explicitly founda _N proportional toN such thatd ^N(ta_N)1 forevery t<1, andd ^N(ta_N)0 forevery t>1. Thus it appears that the network has not yet converged to stationarity uptoa _N , but has converged to stationarity aftera _N , soa _N can be naturally interpreted as the settling time of the network. Here we briefly deal with some other similar models — closed networks of ./M/m nodes, a well studied model for circuit switched networks, and a model of Mitra for studying concurrency control in databases. Similar threshold phenomena are established in the transient behaviour of these models.Research supported by the National Science Foundation, Grant No. NCR 8710840.     

Constant memory routing in quasi-planar and quasi-polyhedral graphs

We address the problem of online route discovery for a class of graphs that can be embedded either in two or in three-dimensional space. In two dimensions we propose the class of quasi-planar graphs and in three dimensions the class of quasi-polyhedral graphs. In the former case such graphs are geometrically embedded in R² and have an underlying backbone that is planar with convex faces; however within each face arbitrary edges (with arbitrary crossings) are allowed. In the latter case, these graphs are geometrically embedded in R³ and consist of a backbone of convex polyhedra and arbitrary edges within each polyhedron. In both cases we provide a routing algorithm that guarantees delivery. Our algorithms need only “remember” the source and destination nodes and one (respectively, two) reference nodes used to store information about the underlying face (respectively, polyhedron) currently being traversed. The existence of the backbone is used only in proofs of correctness of the routing algorithm; the particular choice is irrelevant and does not affect the behaviour of the algorithm.     

Paths, trees and matchings under disjunctive constraints

We study the minimum spanning tree problem, the maximum matching problem and the shortest path problem subject to binary disjunctive constraints: A negative disjunctive constraint states that a certain pair of edges cannot be contained simultaneously in a feasible solution. It is convenient to represent these negative disjunctive constraints in terms of a so-called conflict graph whose vertices correspond to the edges of the underlying graph, and whose edges encode the constraints.We prove that the minimum spanning tree problem is strongly NP-hard, even if every connected component of the conflict graph is a path of length two. On the positive side, this problem is polynomially solvable if every connected component is a single edge (that is, a path of length one). The maximum matching problem is NP-hard for conflict graphs where every connected component is a single edge.Furthermore we will also investigate these graph problems under positive disjunctive constraints: In this setting for certain pairs of edges, a feasible solution must contain at least one edge from every pair. We establish a number of complexity results for these variants including APX-hardness for the shortest path problem.     

A functional limit theorem for random graphs with applications to subgraph count statistics

We consider a random graph that evolves in time by adding new edges at random times (different edges being added at independent and identically distributed times). A functional limit theorem is proved for a class of statistics of the random graph, considered as stochastic processes. the proof is based on a martingale convergence theorem. the evolving random graph allows us to study both the random graph model K_{n, p}, by fixing attention to a fixed time, and the model K_{n, N}, by studying it at the random time it contains exactly N edges. in particular, we obtain the asymptotic distribution as n → ∞ of the number of subgraphs isomorphic to a given graph G, both for K_{n, p} (p fixed) and K_{n, N} (N/(ⁿ₂)→ p). the results are strikingly different; both models yield asymptotically normal distributions, but the variances grow as different powers of n (the variance grows slower for K_n, N; the powers of n usually differ by 1, but sometimes by 3). We also study the number of induced subgraphs of a given type and obtain similar, but more complicated, results. in some exceptional cases, the limit distribution is not normal.     

A note on the cubical dimension of new classes of binary trees

The cubical dimension of a graph G is the smallest dimension of a hypercube into which G is embeddable as a subgraph. The conjecture of Havel (1984) claims that the cubical dimension of every balanced binary tree with 2 ⁿ vertices, n ? 1, is n. The 2-rooted complete binary tree of depth n is obtained from two copies of the complete binary tree of depth n by adding an edge linking their respective roots. In this paper, we determine the cubical dimension of trees obtained by subdividing twice a 2-rooted complete binary tree and prove that every such balanced tree satisfies the conjecture of Havel.     

An optimal sequential algorithm for the uniform approximation of convex functions on [0,1]2

In this paper an algorithm is given for the sequential selection ofN nodes (i.e., measurement points) for the uniform approximation (recovery) of convex functions over [0, 1]², which has almost optimal order global error, (≦c ₁ N ^?1 lgN), over a naturally defined class of convex functions. This shows the essential superiority of sequential algorithms for this class of approximation problems because any simultaneous choice ofN nodes leads to a global error >c ₀ N ^?1/2. New construction and estimation methods are presented, with possible (e.g., multidimensional) generalizations.