#### Date of Award

2010

#### Document Type

Campus Access Dissertation

#### Department

Mathematics

#### First Advisor

Laszlo Szekely

#### Abstract

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 (*d _{r}*(

*Π*)) 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:

*d*where

_{r}(Π) = n + 1 - c(Π) + h(Π) + fr(Π),*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

*S*. It was previously conjectured [16] that

_{n}*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}⁄

_{33}

*n*+

^{1}⁄

_{33}.

The Randić index of a graph *G* is defined as the sum of 1⁄(√*d _{u}d_{v}*) over all pairs

*(u, v)*of adjacent vertices of

*G,*where

*d*is the degree of vertex

_{u}*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 ≅ P_{n}*.

We settle the conjecture positively. In fact, we prove a stronger theorem which implies the conjecture. The second order Randić index * ^{2}R(G)* is defined as follows:

*= (Σ over*

^{2}R(G)*uvw∈P*) where

_{2}) 1⁄(√d_{u}d_{v}d_{w}*P*is the set of all paths in

_{2}*G*of length two. We show that for the trees on

*n*vertices, the star

*S*maximizes the second order Randić index and among triple trees the path

_{n}*P*minimize the second-order Randić index .

_{n}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(C _{n}) = n-1* (for

*n*≥ 3) and for

*s ≥ t*,

*rt(K*= ⌊

_{s,t})^{3s}⁄

_{2t}⌋ +

*O(1)*. We also prove

*n+1≤ rt(Q*for

_{n}) ≤ 2n-2*n ≥ 3*. The lower bound

*rt(Q*was previously conjectured by Alon, Chung and Graham [1]. A variation, the so-called fractional routing number, is also considered.

_{n}) ≥ n+1#### Recommended Citation

Yang, Y.(2010). *Genome Rearrangement, Randic Index and Routing Number.* (Doctoral dissertation). Retrieved from http://scholarcommons.sc.edu/etd/425