Mitochondrial and nuclear markers suggest Hanuman langur (Primates: Colobinae) polyphyly: Implications for their species status

Recent molecular studies on langurs of the Indian subcontinent suggest that the widely-distributed and morphologically variable Hanuman langurs (Semnopithecus entellus) are polyphyletic with respect to Nilgiri and urple-faced langurs. To further investigate this scenario, we have analyzed additional sequences of mitochondrial cytochrome b as well as nuclear protamine P1 genes from these species. The results confirm Hanuman langur polyphyly in the mitochondrial tree and the nuclear markers suggest that the Hanuman langurs share protamine P1 alleles with Nilgiri and purple-faced langurs. We recommend provisional splitting of the so-called Hanuman langurs into three species such that the taxonomy is consistent with their evolutionary relationships.

Molecular phylogeny and biogeography of langurs and leaf monkeys of South Asia (Primates: Colobinae)

The two recently proposed taxonomies of the langurs and leaf monkeys (Subfamily Colobinae) provide different implications to our understanding of the evolution of Nilgiri and purple-faced langurs. Groves (2001) [Groves, C.P., 2001. Primate Taxonomy. Smithsonian Institute Press, Washington], placed Nilgiri and purple-faced langurs in the genus Trachypithecus, thereby suggesting disjunct distribution of the genus Trachypithecus. [Brandon-Jones, D., Eudey, A.A., Geissmann, T., Groves, C.P., Melnick, D.J., Morales, J.C., Shekelle, M., Stewart, C.-B., 2003. Asian primate classification. Int. J. Primatol. 25, 97–162] placed these langurs in the genus Semnopithecus, which suggests convergence of morphological characters in Nilgiri and purple-faced langurs with Trachypithecus. To test these scenarios, we sequenced and analyzed the mitochondrial cytochrome b gene and two nuclear DNA-encoded genes, lysozyme and protamine P1, from a variety of colobine species. All three markers support the clustering of Nilgiri and purple-faced langurs with Hanuman langur (Semnopithecus), while leaf monkeys of Southeast Asian (Trachypithecus) form a distinct clade. The phylogenetic position of capped and golden leaf monkeys is still unresolved. It is likely that this species group might have evolved due to past hybridization between Semnopithecus and Trachypithecus clades.

Rainbow Connection Number and Radius

Rainbow connection number, rc(G), of a connected graph G is the minimum number of colours needed to colour its edges, so that every pair of vertices is connected by at least one path in which no two edges are coloured the same. In this note we show that for every bridgeless graph G with radius r, rc(G) <= r(r+2). We demonstrate that this bound is the best possible for rc(G) as a function of r, not just for bridgeless graphs, but also for graphs of any stronger connectivity. It may be noted that, for a general 1-connected graph G, rc(G) can be arbitrarily larger than its radius (K_{1,n} for instance). We further show that for every bridgeless graph G with radius r and chordality (size of a largest induced cycle) k, rc(G) <= rk. Hitherto, the only reported upper bound on the rainbow connection number of bridgeless graphs is 4n/5 - 1, where n is order of the graph [Caro et al., 2008]

Rainbow connection number and connected dominating sets

The rainbow connection number of a connected graph is the minimum number of colors needed to color its edges, so that every pair of its vertices is connected by at least one path in which no two edges are colored the same. In this article we show that for every connected graph on n vertices with minimum degree delta, the rainbow connection number is upper bounded by 3n/(delta + 1) + 3. This solves an open problem from Schiermeyer (Combinatorial Algorithms, Springer, Berlin/Hiedelberg, 2009, pp. 432437), improving the previously best known bound of 20n/delta (J Graph Theory 63 (2010), 185191). This bound is tight up to additive factors by a construction mentioned in Caro et al. (Electr J Combin 15(R57) (2008), 1). As an intermediate step we obtain an upper bound of 3n/(delta + 1) - 2 on the size of a connected two-step dominating set in a connected graph of order n and minimum degree d. This bound is tight up to an additive constant of 2. This result may be of independent interest. We also show that for every connected graph G with minimum degree at least 2, the rainbow connection number, rc(G), is upper bounded by Gc(G) + 2, where Gc(G) is the connected domination number of G. Bounds of the form diameter(G)?rc(G)?diameter(G) + c, 1?c?4, for many special graph classes follow as easy corollaries from this result. This includes interval graphs, asteroidal triple-free graphs, circular arc graphs, threshold graphs, and chain graphs all with minimum degree delta at least 2 and connected. We also show that every bridge-less chordal graph G has rc(G)?3.radius(G). In most of these cases, we also demonstrate the tightness of the bounds.