The backup 2-median problem on block graphs

The backup 2-median problem is a location problem to locate two facilities at vertices with the minimum expected cost where each facility may fail with a given probability. Once a facility fails, the other one takes full responsibility for the services. Here we assume that the facilities do not fail simultaneously. In this paper, we consider the backup 2-median problem on block graphs where any two edges in one block have the same length and the lengths of edges on different blocks may be different. By constructing a tree-shaped skeleton of a block graph, we devise an O（n log n q- m）-time algorithm to solve this problem where n and m are the number of vertices and edges, respectively, in the given block graph.     

The height of multiple edge plane trees

Multi-edge trees as introduced in a recent paper of Dziemiańczuk are plane trees where multiple edges are allowed. We first show that d-ary multi-edge trees where the out-degrees are bounded by d are in bijection with classical d-ary trees. This allows us to analyse parameters such as the height. The main part of this paper is concerned with multi-edge trees counted by their number of edges. The distribution of the number of vertices as well as the height are analysed asymptotically.     

2-noncrossing trees and 5-ary trees

Recently, Gu et al. [N.S.S. Gu, N.Y. Li, T. Mansour, 2-Binary trees: Bijections and related issues, Discrete Math. 308 (2008) 1209-1221] introduced 2-binary trees and 2-plane trees which are closely related to ternary trees. In this note, we study the 2-noncrossing tree, a noncrossing tree in which each vertex is colored black or white and there is no ascent (u,v) such that both the vertices u and v are colored black. By using the representation of Panholzer and Prodinger for noncrossing trees, we find a correspondence between the set of 2-noncrossing trees of n edges with a black root and the set of 5-ary trees with n internal vertices.     

Les hypercartes planaires sont des arbres tres bien etiquetes

R. Cori and B. Vauquelin have constructed (cf[1]) a one to one correspondence from rooted planar maps onto rooted well-labeled trees (trees whose vertices are labeled with natural numbers that differ by at most one on adjacent vertices). This correspondence does not associate other families of planar maps (e.g. planar hypermaps,...) and easily definable families of trees. The main result of this paper (Theorem 1, Section II) is to construct a new one to one correspondence from rooted planar maps onto rooted well-labeled trees which also associates rooted planar hypermaps with n edge-ends (called ‘brin’ in French) and rooted very well-labeled trees (well labeled trees whose adjacent vertices have not the same label) with n edges. This last result is given in Section 3, Theorem 2.The coding of rooting very well-labeled trees by words extending Dyck's words (or parenthesis systems), allows their enumeration, hence the enumeration of rooted planar hypermaps. This side is the subject of a work in progress under B. Vauquelin.     

Two theorems on graceful trees

Let T be a tree on n vertices which are labelled by the integers in N = {1,2,…,n} such that each vertex of T is associated with a distinct number in N. The weight of an edge is defined to be the absolute value of the difference between the two numbers labelled at its end vertices. If the weights of all edges of T are distinct, we call T a graceful tree. In this note, two methods for constructing bigger graceful trees from a given one and a given pair of graceful trees are provided.     

On edge-weighted recursive trees and inversions in random permutations

We introduce random recursive trees, where deterministically weights are attached to the edges according to the labeling of the trees. We will give a bijection between recursive trees and permutations, which relates the arising edge-weights in recursive trees with inversions of the corresponding permutations. Using this bijection we obtain exact and limiting distribution results for the number of permutations of size n, where exactly m elements have j inversions. Furthermore we analyze the distribution of the sum of labels of the elements, which have exactly j inversions, where we can identify Dickman's infinitely divisible distribution as the limit law. Moreover we give a distributional analysis of weighted depths and weighted distances in edge-weighted recursive trees.     

Diagonally convex directed polyominoes and even trees: a bijection and related issues

We present a simple bijection between diagonally convex directed (DCD) polyominoes with n diagonals and plane trees with 2n edges in which every vertex has even degree (even trees), which specializes to a bijection between parallelogram polyominoes and full binary trees. Next we consider a natural definition of symmetry for DCD-polyominoes, even trees, ternary trees, and non-crossing trees, and show that the number of symmetric objects of a given size is the same in all four cases.     

On Family of Graphs with Minimum Number of Spanning Trees

We show that there is a well-defined family of connected simple graphs Λ(n, m) on n vertices and m edges such that all graphs in Λ(n, m) have the same number of spanning trees, and if ${G \in \Lambda(n, m)}$ then the number of spanning trees in G is strictly less than the number of spanning trees in any other connected simple graph ${H, H \notin \Lambda(n, m)}$ , on n vertices and m edges.     

Partitioning complete graphs by heterochromatic trees

A heterochromatic tree is an edge-colored tree in which any two edges have different colors. The heterochromatic tree partition number of an r-edge-colored graph G, denoted by t _r (G), is the minimum positive integer p such that whenever the edges of the graph G are colored with r colors, the vertices of G can be covered by at most p vertex-disjoint heterochromatic trees. In this paper we determine the heterochromatic tree partition number of r-edge-colored complete graphs. We also find at most t _r (K _n ) vertex-disjoint heterochromatic trees to cover all the vertices in polynomial time for a given r-edge-coloring of K _n .     

Some remarks on the odd hadwiger’s conjecture

We say that H has an odd complete minor of order at least l if there are l vertex disjoint trees in H such that every two of them are joined by an edge, and in addition, all the vertices of trees are two-colored in such a way that the edges within the trees are bichromatic, but the edges between trees are monochromatic. Gerards and Seymour conjectured that if a graph has no odd complete minor of order l, then it is (l ? 1)-colorable. This is substantially stronger than the well-known conjecture of Hadwiger. Recently, Geelen et al. proved that there exists a constant c such that any graph with no odd K _k -minor is ck√logk-colorable. However, it is not known if there exists an absolute constant c such that any graph with no odd K _k -minor is ck-colorable. Motivated by these facts, in this paper, we shall first prove that, for any k, there exists a constant f(k) such that every (496k + 13)-connected graph with at least f(k) vertices has either an odd complete minor of size at least k or a vertex set X of order at most 8k such that G–X is bipartite. Since any bipartite graph does not contain an odd complete minor of size at least three, the second condition is necessary. This is an analogous result of Böhme et al. We also prove that every graph G on n vertices has an odd complete minor of size at least n/2α(G) ? 1, where α(G) denotes the independence number of G. This is an analogous result of Duchet and Meyniel. We obtain a better result for the case α(G)= 3.     

A substitution theorem for graceful trees and its applications

A graceful labeling of a graph G=(V,E) assigns |V| distinct integers from the set {0,…,|E|} to the vertices of G so that the absolute values of their differences on the |E| edges of G constitute the set {1,…,|E|}. A graph is graceful if it admits a graceful labeling. The forty-year old Graceful Tree Conjecture, due to Ringel and Kotzig, states that every tree is graceful.We prove a Substitution Theorem for graceful trees, which enables the construction of a larger graceful tree through combining smaller and not necessarily identical graceful trees. We present applications of the Substitution Theorem, which generalize earlier constructions combining smaller trees.     

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.     

Heterochromatic tree partition numbers for complete bipartite graphs

An r-edge-coloring of a graph G is a surjective assignment of r colors to the edges of G. A heterochromatic tree is an edge-colored tree in which any two edges have different colors. The heterochromatic tree partition number of an r-edge-colored graph G, denoted by t_r(G), is the minimum positive integer p such that whenever the edges of the graph G are colored with r colors, the vertices of G can be covered by at most p vertex-disjoint heterochromatic trees. In this paper we give an explicit formula for the heterochromatic tree partition number of an r-edge-colored complete bipartite graph K_m,n.     

Tree-edges deletion problems with bounded diameter obstruction sets

We study the following problem: given a tree G and a finite set of trees H, find a subset O of the edges of G such that G-O does not contain a subtree isomorphic to a tree from H, and O has minimum cardinality. We give sharp boundaries on the tractability of this problem: the problem is polynomial when all the trees in H have diameter at most 5, while it is NP-hard when all the trees in H have diameter at most 6. We also show that the problem is polynomial when every tree in H has at most one vertex with degree more than 2, while it is NP-hard when the trees in H can have two such vertices.The polynomial-time algorithms use a variation of a known technique for solving graph problems. While the standard technique is based on defining an equivalence relation on graphs, we define a quasiorder. This new variation might be useful for giving more efficient algorithm for other graph problems.     

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.     

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.     

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.     

An iterative approach to graph irregularity strength

An assignment of positive integer weights to the edges of a simple graph G is called irregular if the weighted degrees of the vertices are all different. The irregularity strength, s(G), is the maximal edge weight, minimized over all irregular assignments, and is set to infinity if no such assignment is possible. In this paper, we take an iterative approach to calculating the irregularity strength of a graph. In particular, we develop a new algorithm that determines the exact value s(T) for trees T in which every two vertices of degree not equal to two are at distance at least eight.     

GLOUDS: Representing tree-like graphs

The Graph Level Order Unary Degree Sequence (GLOUDS) is a new succinct data structure for directed graphs that are “tree-like,” in the sense that the number of “additional” edges (w.r.t. a spanning tree) is not too high. The algorithmic idea is to represent a BFS-spanning tree of the graph (consisting of n nodes) with a well known succinct data structure for trees, named LOUDS, and enhance it with additional information that accounts for the non-tree edges. In practical tests, our data structure performs well for graphs containing up to $m=5n$ edges, while still having competitive running times for listing adjacent nodes.     

Depth in bucket recursive trees with variable capacities of buckets

We consider bucket recursive trees of sizen consisting of all buckets with variable capacities1,2,...,b and with a specifc stochastic growth rule.This model can be considered as a generalization of random recursive trees like bucket recursive trees introduced by Mahmoud and Smythe where all buckets have the same capacities.In this work,we provide a combinatorial analysis of these trees where the generating function of the total weights satisfes an autonomous frst order diferential equation.We study the depth of the largest label（i.e.,the number of edges from the root node to the node containing label n）and give a closed formula for the probability distribution.Also we prove a limit law for this quantity which is a direct application of quasi power theorem and compute its mean and variance.Our results for b=1 reduce to the previous results for random recursive trees.