Genome Rearrangement, Randic Index and Routing Number

This dissertation mainly consists of the results of one published [43], three submitted papers [29-31] and two manuscripts [42, 48]. Three kinds of applied problems from discrete mathematics are studied: Genome rearrangements are to represent evolusion of genomes as signed or unsigned permutations of genes and compute their distances based on the minimum number of certain operations (evolutionary events) needed to transform one permutation into another. Reversal and transposition are two well-studied operations in this area. In 1995, Hannenhalli and Pevzner [20] discovered an elegant formula to compute the reversal distance (dr(Π)) between a signed permutation Π and the identity permutation of n elements in terms of some parameters of the breakpoint graph G(Π) associated with Π, as follows: dr(Π) = n + 1 - c(Π) + h(Π) + fr(Π), where c(Π) is the number of cycles, h(Π) is the number of hurdles and fr(Π) takes value 1 or 0 based on whether G(Π) is a fortress or not. We show that the expectation of h(Π) for a randomly and uniformly selected Π is bounded above by 1 + O(1⁄n), which gives a theoretical underpinning to the approximation of the reversal distance with the number n+1-c(Π) in almost all cases. We give a pair of well-matched lower and upper bounds for the expectation of reversal distance under the hypothesis of random gene order by investigating the expected number of cycles in the breakpoint graph of linear signed permutations. We also provide a near-tight upper bound for the variance of reversal distance, which gives information on the distribution of reversal distance. The transposition diameter TD(n) is the maximum of transposition distances among all pairs of permutations in Sn. It was previously conjectured [16] that TD(n) ≤ ⌈n+1⁄2 ⌉. This conjecture was disproved by Elias and Hartman [15] by showing TD(n) ≥ ⌊ n+1⁄2⌋ + 1. We improve the lower bound to TD(n) ≥ 17⁄33n + 1⁄33. The Randić index of a graph G is defined as the sum of 1⁄(√dudv) over all pairs (u, v) of adjacent vertices of G, where du is the degree of vertex u. There is a conjecture in [2] which relates the Randić index R(G) and the diameter D(G). CONJECTURE 0.0.1. For any connected graph of order n ≥ 3 with Randić index R(G) and diameter D(G), R(G) - D(G) ≥ √2 - n+1⁄2 and R(G)⁄D(G) ≥ n-3+2√2⁄2n-2, with equalities if and only if G ≅ Pn. We settle the conjecture positively. In fact, we prove a stronger theorem which implies the conjecture. The second order Randić index 2R(G) is defined as follows: 2R(G) = (Σ over uvw∈P2) 1⁄(√dudvdw) where P2 is the set of all paths in G of length two. We show that for the trees on n vertices, the star Sn maximizes the second order Randić index and among triple trees the path Pn minimize the second-order Randić index . The routing number rt(G) of a connected graph G is the minimum integer r so that every permutation of vertices can be routed in r steps by swapping the numbers at the end points of disjoint edges. We study the routing numbers of cycles, complete bipartite graphs, and hypercubes. We prove that rt(Cn) = n-1 (for n ≥ 3) and for s ≥ t, rt(Ks,t) = ⌊3s⁄2t⌋ + O(1). We also prove n+1≤ rt(Qn) ≤ 2n-2 for n ≥ 3. The lower bound rt(Qn) ≥ n+1 was previously conjectured by Alon, Chung and Graham [1]. A variation, the so-called fractional routing number, is also considered