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]

Particle dynamics in the channel flow of a turbulent particle-gas suspension at high Stokes number. Part 1. DNS and fluctuating force model

The fluctuating force model is developed and applied to the turbulent flow of a gas-particle suspension in a channel in the limit of high Stokes number, where the particle relaxation time is large compared to the fluid correlation time, and low particle Reynolds number where the Stokes drag law can be used to describe the interaction between the particles and fluid. In contrast to the Couette flow, the fluid velocity variances in the different directions in the channel are highly non-homogeneous, and they exhibit significant variation across the channel. First, we analyse the fluctuating particle velocity and acceleration distributions at different locations across the channel. The distributions are found to be non-Gaussian near the centre of the channel, and they exhibit significant skewness and flatness. However, acceleration distributions are closer to Gaussian at locations away from the channel centre, especially in regions where the variances of the fluid velocity fluctuations are at a maximum. The time correlations for the fluid velocity fluctuations and particle acceleration fluctuations are evaluated, and it is found that the time correlation of the particle acceleration fluctuations is close to the time correlations of the fluid velocity in a `moving Eulerian' reference, moving with the mean fluid velocity. The variances of the fluctuating force distributions in the Langevin simulations are determined from the time correlations of the fluid velocity fluctuations and the results are compared with direct numerical simulations. Quantitative agreement between the two simulations are obtained provided the particle viscous relaxation time is at least five times larger than the fluid integral time.

Particle dynamics in the channel flow of a turbulent particle-gas suspension at high Stokes number. Part 2. Comparison of fluctuating force simulations and experiments

The particle and fluid velocity fluctuations in a turbulent gas-particle suspension are studied experimentally using two-dimensional particle image velocimetry with the objective of comparing the experiments with the predictions of fluctuating force simulations. Since the fluctuating force simulations employ force distributions which do not incorporate the modification of fluid turbulence due to the particles, it is of importance to quantify the turbulence modification in the experiments. For experiments carried out at a low volume fraction of 9.15 x 10(-5) (mass loading is 0.19), where the viscous relaxation time is small compared with the time between collisions, it is found that the gas-phase turbulence is not significantly modified by the presence of particles. Owing to this, quantitative agreement is obtained between the results of experiments and fluctuating force simulations for the mean velocity and the root mean square of the fluctuating velocity, provided that the polydispersity in the particle size is incorporated in the simulations. This is because the polydispersity results in a variation in the terminal velocity of the particles which could induce collisions and generate fluctuations; this mechanism is absent if all of the particles are of equal size. It is found that there is some variation in the particle mean velocity very close to the wall depending on the wall-collision model used in the simulations, and agreement with experiments is obtained only when the tangential wall-particle coefficient of restitution is 0.7. The mean particle velocity is in quantitative agreement for locations more than 10 wall units from the wall of the channel. However, there are systematic differences between the simulations and theory for the particle concentrations, possibly due to inadequate control over the particle feeding at the entrance. The particle velocity distributions are compared both at the centre of the channel and near the wall, and the shape of the distribution function near the wall obtained in experiments is accurately predicted by the simulations. At the centre, there is some discrepancy between simulations and experiment for the distribution of the fluctuating velocity in the flow direction, where the simulations predict a bi-modal distribution whereas only a single maximum is observed in the experiments, although both distributions are skewed towards negative fluctuating velocities. At a much higher particle mass loading of 1.7, where the time between collisions is smaller than the viscous relaxation time, there is a significant increase in the turbulent velocity fluctuations by similar to 1-2 orders of magnitude. Therefore, it becomes necessary to incorporate the modified fluid-phase intensity in the fluctuating force simulation; with this modification, the mean and mean-square fluctuating velocities are within 20-30% of the experimental values.

Group Actions and Elementary Number Theory

Abstract | In this article the shuffling of cards is studied by using the concept of a group action. We use some fundamental results in Elementary Number Theory to obtain formulas for the orders of some special shufflings, namely the Faro and Monge shufflings and give necessary and sufficient conditions for the Monge shuffling to be a cycle. In the final section we extend the considerations to the shuffling of multisets.

Mathematical Model of Viral Kinetics In Vitro Estimates the Number of E2-CD81 Complexes Necessary for Hepatitis C Virus Entry

Interaction between the hepatitis C virus (HCV) envelope protein E2 and the host receptor CD81 is essential for HCV entry into target cells. The number of E2-CD81 complexes necessary for HCV entry has remained difficult to estimate experimentally. Using the recently developed cell culture systems that allow persistent HCV infection in vitro, the dependence of HCV entry and kinetics on CD81 expression has been measured. We reasoned that analysis of the latter experiments using a mathematical model of viral kinetics may yield estimates of the number of E2-CD81 complexes necessary for HCV entry. Here, we constructed a mathematical model of HCV viral kinetics in vitro, in which we accounted explicitly for the dependence of HCV entry on CD81 expression. Model predictions of viral kinetics are in quantitative agreement with experimental observations. Specifically, our model predicts triphasic viral kinetics in vitro, where the first phase is characterized by cell proliferation, the second by the infection of susceptible cells and the third by the growth of cells refractory to infection. By fitting model predictions to the above data, we were able to estimate the threshold number of E2-CD81 complexes necessary for HCV entry into human hepatoma-derived cells. We found that depending on the E2-CD81 binding affinity, between 1 and 13 E2-CD81 complexes are necessary for HCV entry. With this estimate, our model captured data from independent experiments that employed different HCV clones and cells with distinct CD81 expression levels, indicating that the estimate is robust. Our study thus quantifies the molecular requirements of HCV entry and suggests guidelines for intervention strategies that target the E2-CD81 interaction. Further, our model presents a framework for quantitative analyses of cell culture studies now extensively employed to investigate HCV infection.

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.

Real-time monitoring of critical nodes with minimal number of Phasor Measurement Units

This paper presents a method for placement of Phasor Measurement Units, ensuring the monitoring of vulnerable buses which are obtained based on transient stability analysis of the overall system. Real-time monitoring of phase angles across different nodes, which indicates the proximity to instability, the very purpose will be well defined if the PMUs are placed at buses which are more vulnerable. The issue is to identify the key buses where the PMUs should be placed when the transient stability prediction is taken into account considering various disturbances. Integer Linear Programming technique with equality and inequality constraints is used to find out the optimal placement set with key buses identified from transient stability analysis. Results on IEEE-14 bus system are presented to illustrate the proposed approach.

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.

Cubicity, degeneracy, and crossing number

A $k$-box $B=(R_1,...,R_k)$, where each $R_i$ is a closed interval on the real line, is defined to be the Cartesian product $R_1\times R_2\times ...\times R_k$. If each $R_i$ is a unit length interval, we call $B$ a $k$-cube. Boxicity of a graph $G$, denoted as $\boxi(G)$, is the minimum integer $k$ such that $G$ is an intersection graph of $k$-boxes. Similarly, the cubicity of $G$, denoted as $\cubi(G)$, is the minimum integer $k$ such that $G$ is an intersection graph of $k$-cubes. It was shown in [L. Sunil Chandran, Mathew C. Francis, and Naveen Sivadasan: Representing graphs as the intersection of axis-parallel cubes. MCDES-2008, IISc Centenary Conference, available at CoRR, abs/cs/ 0607092, 2006.] that, for a graph $G$ with maximum degree $\Delta$, $\cubi(G)\leq \lceil 4(\Delta +1)\log n\rceil$. In this paper, we show that, for a $k$-degenerate graph $G$, $\cubi(G) \leq (k+2) \lceil 2e \log n \rceil$. Since $k$ is at most $\Delta$ and can be much lower, this clearly is a stronger result. This bound is tight. We also give an efficient deterministic algorithm that runs in $O(n^2k)$ time to output a $8k(\lceil 2.42 \log n\rceil + 1)$ dimensional cube representation for $G$. An important consequence of the above result is that if the crossing number of a graph $G$ is $t$, then $\boxi(G)$ is $O(t^{1/4}{\lceil\log t\rceil}^{3/4})$ . This bound is tight up to a factor of $O((\log t)^{1/4})$. We also show that, if $G$ has $n$ vertices, then $\cubi(G)$ is $O(\log n + t^{1/4}\log t)$. Using our bound for the cubicity of $k$-degenerate graphs we show that cubicity of almost all graphs in $\mathcal{G}(n,m)$ model is $O(d_{av}\log n)$, where $d_{av}$ denotes the average degree of the graph under consideration. model is O(davlogn).

Coulomb-hole summations and energies for GW calculations with limited number of empty orbitals: a modified static remainder approach

Ab initio GW calculations are a standard method for computing the spectroscopic properties of many materials. The most computationally expensive part in conventional implementations of the method is the generation and summation over the large number of empty orbitals required to converge the electron self-energy. We propose a scheme to reduce the summation over empty states by the use of a modified static remainder approximation, which is simple to implement and yields accurate self-energies for both bulk and molecular systems requiring a small fraction of the typical number of empty orbitals.