Efficient implementation of a shifting algorithm

An efficient implementation of the shifting algorithm [2] for min-max tree partitioning is given. The complexity is reduced from ORk³ + kn) to O(Rk(k + log d) + n) where a tree of n vertices, radius, of R edges, and maximum degree d is partitioned into k + 1 subtrees. The improvement is mainly due to the new junction tree data structure which suggests a succinct representation for subsets of edges, of a given tree, that preserves the interrelation betqween the edges on the tree.     

A bijective enumeration of labeled trees with given indegree sequence

For a labeled tree on the vertex set {1,2,…,n}, the local direction of each edge (ij) is from i to j if i<j. For a rooted tree, there is also a natural global direction of edges towards the root. The number of edges pointing to a vertex is called its indegree. Thus the local (resp. global) indegree sequence λ=e₁¹e₂²… of a tree on the vertex set {1,2,…,n} is a partition of n−1. We construct a bijection from (unrooted) trees to rooted trees such that the local indegree sequence of a (unrooted) tree equals the global indegree sequence of the corresponding rooted tree. Combining with a Prüfer-like code for rooted labeled trees, we obtain a bijective proof of a recent conjecture by Cotterill and also solve two open problems proposed by Du and Yin. We also prove a q-multisum binomial coefficient identity which confirms another conjecture of Cotterill in a very special case.     

On domination and reinforcement numbers in trees

The reinforcement number of a graph is the smallest number of edges that have to be added to a graph to reduce the domination number. We introduce the k-reinforcement number of a graph as the smallest number of edges that have to be added to a graph to reduce the domination number by k. We present an O(k²n) dynamic programming algorithm for computing the maximum number of vertices that can be dominated using γ(G)-k dominators for trees. A corollary of this is a linear-time algorithm for computing the k-reinforcement number of a tree. We also discuss extensions and related problems.     

Sur les zéros des séries d'Eisenstein dans le demi-plan de Drinfeld

Eisenstein series for GL₂(F_q[T]) of weight q^k − 1 have zeroes in the Drinfeld upper half-plane. Let F be a fundamental domain for the GL₂(A)-action. We determine the number of zeroes in F of these series. Our method is essentially based on an assocíation between Eisenstein series and some functions defined on the edges of the Bruhat-Tits tree.     

On the uniform edge-partition of a tree

We study the problem of uniformly partitioning the edge set of a tree with n edges into k connected components, where k?n. The objective is to minimize the ratio of the maximum to the minimum number of edges of the subgraphs in the partition. We show that, for any tree and k?4, there exists a k-split with ratio at most two. For general k, we propose a simple algorithm that finds a k-split with ratio at most three in O(nlogk) time. Experimental results on random trees are also shown.     

A distributional study of the path edge-covering numbers for random trees

We study for various tree families the distribution of the number of edge-disjoint paths required to cover the edges of a random tree of size n. For all tree families considered we can show a central limit theorem with expectation ∼μn and variance ∼νn with constants μ, ν depending on the specific tree family.     

Models of adding relations to an organization structure of a complete K-ary tree

This paper proposes three models of adding relations to an organization structure which is a complete K-ary tree of height H: (i) a model of adding an edge between two nodes with the same depth N, (ii) a model of adding edges between every pair of nodes with the same depth N and (iii) a model of adding edges between every pair of siblings with the same depth N. For each of the three models, an optimal depth N¹ is obtained by maximizing the total shortening path length which is the sum of shortening lengths of shortest paths between every pair of all nodes.     

On edges crossing few other edges in simple topological complete graphs

We study the existence of edges having few crossings with the other edges in drawings of the complete graph (more precisely, in simple topological complete graphs). A topological graphT=(V,E) is a graph drawn in the plane with vertices represented by distinct points and edges represented by Jordan curves connecting the corresponding pairs of points (vertices), passing through no other vertices, and having the property that any intersection point of two edges is either a common end-point or a point where the two edges properly cross. A topological graph is simple if any two edges meet in at most one common point.Let h=h(n) be the smallest integer such that every simple topological complete graph on n vertices contains an edge crossing at most h other edges. We show that Ω(n^3/2)≤h(n)≤O(n²/log^1/4n). We also show that the analogous function on other surfaces (torus, Klein bottle) grows as cn².     

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.     

Evolutionary trees and the Ising model on the Bethe lattice: a proof of Steel��s conjecture

A major task of evolutionary biology is the reconstruction of phylogenetic trees from molecular data. The evolutionary model is given by a Markov chain on a tree. Given samples from the leaves of the Markov chain, the goal is to reconstruct the leaf-labelled tree. It is well known that in order to reconstruct a tree on n leaves, sample sequences of length ??(log n) are needed. It was conjectured by Steel that for the CFN/Ising evolutionary model, if the mutation probability on all edges of the tree is less than ${p^{\ast} = (\sqrt{2}-1)/2^{3/2}}$ , then the tree can be recovered from sequences of length O(log n). The value p* is given by the transition point for the extremality of the free Gibbs measure for the Ising model on the binary tree. Steel??s conjecture was proven by the second author in the special case where the tree is ??balanced.?? The second author also proved that if all edges have mutation probability larger than p* then the length needed is n ^??(1). Here we show that Steel??s conjecture holds true for general trees by giving a reconstruction algorithm that recovers the tree from O(log n)-length sequences when the mutation probabilities are discretized and less than p*. Our proof and results demonstrate that extremality of the free Gibbs measure on the infinite binary tree, which has been studied before in probability, statistical physics and computer science, determines how distinguishable are Gibbs measures on finite binary trees.     

A polynomial algorithm to compute the minimum degree spanning trees of directed acyclic graphs with applications to the broadcast problem

In this paper, we focus on the directed minimum degree spanning tree problem and the minimum time broadcast problem. Firstly, we propose a polynomial time algorithm for the minimum degree spanning tree problem in directed acyclic graphs. The algorithm starts with an arbitrary spanning tree, and iteratively reduces the number of vertices of maximum degree. We can prove that the algorithm must reduce a vertex of the maximum degree for each phase, and finally result in an optimal tree. The algorithm terminates in O(mnlogn) time, where m and n are the numbers of edges and vertices of the graph, respectively. Moreover, we apply the new algorithm to the minimum time broadcast problem. Two consequences for directed acyclic graphs are: (1) the problem under the vertex-disjoint paths mode can be approximated within a factor of of the optimum in O(mnlogn)-time; (2) the problem under the edge-disjoint paths mode can be approximated within a factor of O(Δ^*/logΔ^*) of the optimum in O(mnlogn)-time, where Δ^* is the minimum k such that there is a spanning tree of the graph with maximum degree k.     

On spanning tree congestion of graphs

Let G be a connected graph and T be a spanning tree of G. For e∈E(T), the congestion of e is the number of edges in G connecting two components of T−e. The edge congestion ofGinT is the maximum congestion over all edges in T. The spanning tree congestion ofG is the minimum congestion of G in its spanning trees. In this paper, we show the spanning tree congestion for the complete k-partite graphs and the two-dimensional tori. We also address lower bounds of spanning tree congestion for the multi-dimensional grids and the hypercubes.     

On the combinatorial structure of Rauzy graphs

Let S _m ⁰ be the set of all irreducible permutations of the numbers {1, ??,m} (m ?? 3). We define Rauzy induction mappings a and b acting on the set S _m ⁰ . For a permutation ?? ?? S _m ⁰ , denote by R(??) the orbit of the permutation ?? under the mappings a and b. This orbit can be endowed with the structure of an oriented graph according to the action of the mappings a and b on this set: the edges of this graph belong to one of the two types, a or b. We say that the graph R(??) is a tree composed of cycles if any simple cycle in this graph consists of edges of the same type. An equivalent formulation of this condition is as follows: a dual graph R*(??) of R(??) is a tree. The main result of the paper is as follows: if the graph R(??) of a permutation ?? ?? S _m ⁰ is a tree composed of cycles, then the set R(??) contains a permutation ?? ₀: i ? m + 1 ? i, i = 1, ??,m. The converse result is also proved: the graph R(?? ₀) is a tree composed of cycles; in this case, the structure of the graph is explicitly described.     

Schemes of involving dual variables in inverse barrier functions for problems of linear and convex programming

With any stable map from a 3-manifold to ℝ³, we associate a graph with weights in its vertices and edges. These graphs are A-invariants from a global viewpoint. We study their properties and show that any tree with zero weights in its vertices and aleatory weights in its edges can be the graph of a stable map from S ³ to ℝ³.     

A bijection for covered maps, or a shortcut between Harer-Zagier?s and Jackson?s formulas

We consider maps on orientable surfaces. A map is called unicellular if it has a single face. A covered map is a map (of genus g) with a marked unicellular spanning submap (which can have any genus in {0,1,…,g}). Our main result is a bijection between covered maps with n edges and genus g and pairs made of a plane tree with n edges and a unicellular bipartite map of genus g with n+1 edges. In the planar case, covered maps are maps with a marked spanning tree and our bijection specializes into a construction obtained by the first author in Bernardi (2007) [4].Covered maps can also be seen as shuffles of two unicellular maps (one representing the unicellular submap, the other representing the dual unicellular submap). Thus, our bijection gives a correspondence between shuffles of unicellular maps, and pairs made of a plane tree and a unicellular bipartite map. In terms of counting, this establishes the equivalence between a formula due to Harer and Zagier for general unicellular maps, and a formula due to Jackson for bipartite unicellular maps.We also show that the bijection of Bouttier, Di Francesco and Guitter (2004) [8] (which generalizes a previous bijection by Schaeffer, 1998 [33]) between bipartite maps and so-called well-labeled mobiles can be obtained as a special case of our bijection.     

On covering graphs by complete bipartite subgraphs

We prove that, if a graph with e edges contains m vertex-disjoint edges, then m²/e complete bipartite subgraphs are necessary to cover all its edges. Similar lower bounds are also proved for fractional covers. For sparse graphs, this improves the well-known fooling set lower bound in communication complexity. We also formulate several open problems about covering problems for graphs whose solution would have important consequences in the complexity theory of boolean functions.     

An approximate version of the tree packing conjecture

We prove that for any pair of constants ? > 0 and Δ and for n sufficiently large, every family of trees of orders at most n, maximum degrees at most Δ, and with at most (_n²) edges in total packs into \({K_{(1 + \varepsilon )n}}\). This implies asymptotic versions of the Tree Packing Conjecture of Gyárfás from 1976 and a tree packing conjecture of Ringel from 1963 for trees with bounded maximum degree. A novel random tree embedding process combined with the nibble method forms the core of the proof.     

On the second point-to-point undirected shortest simple path problem

We address the determination of the second point-to-point shortest simple path in undirected networks. The effective reduced cost concept is introduced to compute the second best solution. This concept is used to prove that a path tree containing the second point-to-point shortest simple path is adjacent to any shortest path tree. Therefore, this result immediately implies a method requiring O(m) time once that the shortest path tree is obtained on an undirected network with n nodes and m edges.     

On the Structure of Contractible Vertex Pairs in Chordal Graphs

An edge/non-edge in a k-connected graph is contractible if its contraction does not result in a graph of lower connectivity. We focus our study on contractible edges and non-edges in chordal graphs. Firstly, we characterize contractible edges in chordal graphs using properties of tree decompositions with respect to minimal vertex separators. Secondly, we show that in every chordal graph each non-edge is contractible. We also characterize non-edges whose contraction leaves a k-connected chordal graph.     

Potential Theory on Trees,Graphs and Ahlfors-regular Metric Spaces

We investigate connections between potential theories on a Ahlfors-regular metric space X, on a graph G associated with X, and on the tree T obtained by removing the “horizontal edges” in G. Applications to the calculation of set capacity are given.