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 Connectivity

The rainbow connection number, rc(G), of a connected graph G is the minimum number of colors needed to color its edges, so that every pair of vertices is connected by at least one path in which no two edges are colored the same. Our main result is that rc(G) <= inverted right perpendicularn/2inverted left perpendicular for any 2-connected graph with at least three vertices. We conjecture that rc(G) <= n/kappa + C for a kappa-connected graph G of order n, where C is a constant, and prove the conjecture for certain classes of graphs. We also prove that rc(G) < (2 + epsilon)n/kappa + 23/epsilon(2) for any epsilon > 0.

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.

Rainbow connectivity: hardness and tractability

A path in an edge colored graph is said to be a rainbow path if no two edges on the path have the same color. An edge colored graph is (strongly) rainbow connected if there exists a (geodesic) rainbow path between every pair of vertices. The (strong) rainbow connectivity of a graph G, denoted by (src(G), respectively) rc(G) is the smallest number of colors required to edge color the graph such that G is (strongly) rainbow connected. In this paper we study the rainbow connectivity problem and the strong rainbow connectivity problem from a computational point of view. Our main results can be summarised as below: 1) For every fixed k >= 3, it is NP-Complete to decide whether src(G) <= k even when the graph G is bipartite. 2) For every fixed odd k >= 3, it is NP-Complete to decide whether rc(G) <= k. This resolves one of the open problems posed by Chakraborty et al. (J. Comb. Opt., 2011) where they prove the hardness for the even case. 3) The following problem is fixed parameter tractable: Given a graph G, determine the maximum number of pairs of vertices that can be rainbow connected using two colors. 4) For a directed graph G, it is NP-Complete to decide whether rc(G) <= 2.

Rainbow colouring of split and threshold Graphs

A rainbow colouring of a connected graph is a colouring of the edges of the graph, such that every pair of vertices is connected by at least one path in which no two edges are coloured the same. Such a colouring using minimum possible number of colours is called an optimal rainbow colouring, and the minimum number of colours required is called the rainbow connection number of the graph. A Chordal Graph is a graph in which every cycle of length more than 3 has a chord. A Split Graph is a chordal graph whose vertices can be partitioned into a clique and an independent set. A threshold graph is a split graph in which the neighbourhoods of the independent set vertices form a linear order under set inclusion. In this article, we show the following: 1. The problem of deciding whether a graph can be rainbow coloured using 3 colours remains NP-complete even when restricted to the class of split graphs. However, any split graph can be rainbow coloured in linear time using at most one more colour than the optimum. 2. For every integer k ≥ 3, the problem of deciding whether a graph can be rainbow coloured using k colours remains NP-complete even when restricted to the class of chordal graphs. 3. For every positive integer k, threshold graphs with rainbow connection number k can be characterised based on their degree sequence alone. Further, we can optimally rainbow colour a threshold graph in linear time.

Algebraic characterization of rainbow connectivity

The use of algebraic techniques to solve combinatorial problems is studied in this paper. We formulate the rainbow connectivity problem as a system of polynomial equations. We first consider the case of two colors for which the problem is known to be hard and we then extend the approach to the general case. We also present a formulation of the rainbow connectivity problem as an ideal membership problem.

Rainbow Emission from an Atomic Transition in Doped Quantum Dots

Although semiconductor quantum dots are promising materials for displays and lighting due to their tunable emissions, these materials also suffer from the serious disadvantage of self-absorption of emitted light. The reabsorption of emitted light is a serious loss mechanism in practical situations because most phosphors exhibit subunity quantum yields. Manganese-based phosphors that also exhibit high stability and quantum efficiency do not suffer from this problem but in turn lack emission tunability, seriously affecting their practical utility. Here, we present a class of manganese-doped quantum dot materials, where strain is used to tune the wavelength of the dopant emission, extending the otherwise limited emission tunability over the yellow-orange range for manganese ions to almost the entire visible spectrum covering all colors from blue to red. These new materials thus combine the advantages of both quantum dots and conventional doped phosphors, thereby opening new possibilities for a wide range of applications in the future.

Rainbow Connection Number of Graph Power and Graph Products

Rainbow connection number, rc(G), of a connected graph G is the minimum number of colors needed to color its edges so that every pair of vertices is connected by at least one path in which no two edges are colored the same (note that the coloring need not be proper). In this paper we study the rainbow connection number with respect to three important graph product operations (namely the Cartesian product, the lexicographic product and the strong product) and the operation of taking the power of a graph. In this direction, we show that if G is a graph obtained by applying any of the operations mentioned above on non-trivial graphs, then rc(G) a parts per thousand currency sign 2r(G) + c, where r(G) denotes the radius of G and . In general the rainbow connection number of a bridgeless graph can be as high as the square of its radius 1]. This is an attempt to identify some graph classes which have rainbow connection number very close to the obvious lower bound of diameter (and thus the radius). The bounds reported are tight up to additive constants. The proofs are constructive and hence yield polynomial time -factor approximation algorithms.

Rainbow matchings in strongly edge-colored graphs

A rainbow matching of an edge-colored graph G is a matching in which no two edges have the same color. There have been several studies regarding the maximum size of a rainbow matching in a properly edge-colored graph G in terms of its minimum degree 3(G). Wang (2011) asked whether there exists a function f such that a properly edge-colored graph G with at least f (delta(G)) vertices is guaranteed to contain a rainbow matching of size delta(G). This was answered in the affirmative later: the best currently known function Lo and Tan (2014) is f(k) = 4k - 4, for k >= 4 and f (k) = 4k - 3, for k <= 3. Afterwards, the research was focused on finding lower bounds for the size of maximum rainbow matchings in properly edge-colored graphs with fewer than 4 delta(G) - 4 vertices. Strong edge-coloring of a graph G is a restriction of proper edge-coloring where every color class is required to be an induced matching, instead of just being a matching. In this paper, we give lower bounds for the size of a maximum rainbow matching in a strongly edge-colored graph Gin terms of delta(G). We show that for a strongly edge-colored graph G, if |V(G)| >= 2 |3 delta(G)/4|, then G has a rainbow matching of size |3 delta(G)/4|, and if |V(G)| < 2 |3 delta(G)/4|, then G has a rainbow matching of size |V(G)|/2] In addition, we prove that if G is a strongly edge-colored graph that is triangle-free, then it contains a rainbow matching of size at least delta(G). (C) 2015 Elsevier B.V. All rights reserved.

Nutrient digestibility and growth response of rainbow trout (Salmo gairdneri ) fed different carbohydrate types

Seven groups of fingerling rainbow trout (S. gairdneri ) were fed for 10 weeks on 0%, 10%, 20% and 30% of cassava or rice in isonitrogenous diets. Optimum growth and food utilization was at 20% dietary cassava. High fiber content of the control diet did not suppress protein digestibility in this group. Rather, at all levels, protein digestibility was good and remained between 84.4% and 90.1%. However, in the control group, carbohydrate digestibility was very poor. The cassava diets which had the highest digestible energy as carbohydrate produced the best growth performance, food utilization and protein sparing. At the levels studied, the dietary carbohydrates produced no hyperglycamic effect on the fish

Modulation of the effectiveness of 17-alpha-hydroxy-20-beta-dihydroprogesterone or of a gonadotrophic extract on the in vitro intrafollicular maturation of oocytes of the rainbow trout Salmo gairdnerii by various non-maturing steroids [Translation from: Compte Rendu Hebdomadaire des Seances de l'Academie des Sciences, Paris, Series D 281, 811-814, 1975]

The effectiveness of 17 α-hydroxy-20 β-dihydroprogesterone (17 α-20 β Pg) or of a trout hypophyseal gonadotrophic extract on the in vitro intrafollicular maturation of trout oocytes can be modulated by steroids which do not have a direct maturing effect; the effectiveness of the gonadotrophic extract is lowered by oestradiol and oestrone and increased by testosterone. As these steroids have no significant effect on maturation induced by 17 α-20 β Pg, the site of their activity is probably in the follicular envelopes. Corticosteroids, and Cortisol and cortisone in particular increase the effectiveness of the gonadotrophic extract, but increase the effectiveness of 17 α-20 β Pg even more strongly, suggesting that this 'progestagen' has a direct effect on oocyte sensitivity.

The effect of oxygen concentration in water on the growth and nitrogen metabolism in the fry of rainbow trout [Translation from: Rybnoe Khoziaistvo,V.33, 74-75, 1957]

To ascertain the effect of various concentrations of oxygen in water on the fry of rainbow trout experiments were made with aquaria at various concentrations of oxygen. The food supplied was chironomid larvae (Chironomus plumosus). A surplus of food was supplied to the fry. Indices are given of the reaction of the fry to different temperatures.

The effects of environmental stress on the physiology of growth in rainbow trout, Salmo gairderi Richardson

There is little doubt that both mammalian and teleost growth hormones can accelerate growth and increase food conversion efficiency in all commonly-reared species of salmonid fish. In those vertebrates that have been closely studied (predominantly mammals), the pituitary hormone somatotropin (GH or growth hormone) is a prime determinant of somatic growth. The hormone stimulates protein biosynthesis and tissue growth, enhances lipid utilization and lipid release from the adipose tissues (a protein-sparing effect) and suppresses the peripheral utilization of glucose. The present study is a prerequisite for future work on growth hormone physiology in salmonids and should contribute to our understanding of the mechanisms of growth suppression in stressed fish. Plasma growth hormone (GH) levels were measured in rainbow trout using a radioimmunoassay developed against chinook salmon growth hormone.

Conservation of the Nilgiri rainbow trout in India

Rainbow trout is one of the important exotic species that is well established in the upland waters of India. This paper presents the historical background of its introduction and the present status of the fish in the streams of he Nilgiri peninsula of India. The rainbow trout inhabits natural reservoirs and streams of the region as a self-recruiting population. The growth rate is reported to be relatively low and conflicting views about its taxonomic status have been reported. Successful crossbreeding of the Nilgiri rainbow trout with trout stocks from the Indian State of Himachal Pradesh has indicated the scope for utilizing cryopreserved milt as a mode of introducing new genetic material into the Nilgiri rainbow trout population. This paper outlines the requirement of ecological and genetic data to develop a strategy for management and reintroduction fresh stocks.