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.

Continuum theory of edge states of topological insulators: variational principle and boundary conditions

We develop a continuum theory to model low energy excitations of a generic four-band time reversal invariant electronic system with boundaries. We propose a variational energy functional for the wavefunctions which allows us to derive natural boundary conditions valid for such systems. Our formulation is particularly suited for developing a continuum theory of the protected edge/surface excitations of topological insulators both in two and three dimensions. By a detailed comparison of our analytical formulation with tight binding calculations of ribbons of topological insulators modelled by the Bernevig-Hughes-Zhang (BHZ) Hamiltonian, we show that the continuum theory with a natural boundary condition provides an appropriate description of the low energy physics.

Catalysis of tRNA Aminoacylation: Single Turnover to Steady-State Kinetics of tRNA Synthetases

Aminoacyl-tRNA synthetases (aaRS) catalyze the bimolecular association reaction between amino acid and tRNA by specifically and unerringly choosing the cognate amino acid and tRNA. There are two classes of such synthetases that perform tRNA-aminoacylation reaction. Interestingly, these two classes of aminoacyl-tRNA synthetases differ not only in their structures but they also exhibit remarkably distinct kinetics under pre-steady-state condition. The class I synthetases show initial burst of product formation followed by a slower steady-state rate. This has been argued to represent the influence of slow product release. In contrast, there is no burst in the case of class H enzymes. The tight binding of product with enzyme for class I enzymes is correlated with the enhancement of rate in presence of elongation factor. EF-TU. In spite of extensive experimental studies, there is no detailed theoretical analysis that can provide a quantitative understanding of this important problem. In this article, we present a theoretical investigation of enzyme kinetics for both classes of aminoacyl-tRNA synthetases. We present an augmented kinetic scheme and then employ the methods of time-dependent probability statistics to obtain expressions for the first passage time distribution that gives both the time-dependent and the steady-state rates. The present study quantitatively explains all the above experimental observations. We propose an alternative path way in the case of class II enzymes showing the tRNA-dependent amino acid activation and the discrepancy between the single-turnover and steady-state rate.

Directional motion of impacting drops on dual-textured surfaces

In this work, we analyze the directional movement of impacting liquid drops on dual-textured solid surfaces comprising two different surface morphologies: a textured surface and a smooth surface. The dynamics of liquid drops impacting onto the junction line between the two parts of the dual-textured surfaces is studied experimentally for varying drop impact velocity. The dual-textured surfaces used here featured a variation in their textures' geometrical parameters as well as their surface chemistry. Two types of liquid drop differing in their surface tension were used. The impact process develops a net horizontal drop velocity towards the higher-wettability surface portion and results in a bulk movement of the impacting drop liquid. The final distance moved by the impacting drop from the junction line decreases with increasing impacting drop Weber number We. A fully theoretical model, employing a balance of forces acting at the drop contact line as well as energy conservation, is formulated to determine the variation, with We, of net horizontal drop velocity and subsequent movement of the impacting drop on the dual-textured surfaces.

Electrical properties of buckled multiwalled carbon nanotube arrays in the diffusive regime

We report the geometrical effect of graded buckled multiwalled carbon nanotube arrays on the electrical transport properties in the diffusive regime, via successive breakdown caused by the Joule heating. This breakdown occurs in the straighter region. Empirical relations involving the current-carrying ability, resistance, breakdown power, threshold voltage, diameter and length of carbon nanotube arrays are discussed on the basis of an extensive set of experimental data along with justification. The experimental results are corroborated by the density functional tight-binding calculations of electronic band structure. The band gap decreases as buckleness increases leading to the enhancement in the current-carrying ability and elucidating the role of buckleness in carbon nanotubes. Copyright (c) EPLA, 2012

Role of Specific Cations and Water Entropy on the Stability of Branched DNA Motif Structures

DNA three-way junctions (TWJs) are important intermediates in various cellular processes and are the simplest of a family of branched nucleic acids being considered as scaffolds for biomolecular nanotechnology. Branched nucleic acids are stabilized by divalent cations such as Mg2+, presumably due to condensation and neutralization of the negatively charged DNA backbone. However, electrostatic screening effects point to more complex solvation dynamics and a large role of interfacial waters in thermodynamic stability. Here, we report extensive computer simulations in explicit water and salt on a model TWJ and use free energy calculations to quantify the role of ionic character and strength on stability. We find that enthalpic stabilization of the first and second hydration shells by Mg2+ accounts for 1/3 and all of the free energy gain in 50% and pure MgCl2 solutions, respectively. The more distorted DNA molecule is actually destabilized in pure MgCl2 compared to pure NaCl. Notably, the first shell, interfacial waters have very low translational and rotational entropy (i.e., mobility) compared to the bulk, an entropic loss that is overcompensated by increased enthalpy from additional electrostatic interactions with Mg2+. In contrast, the second hydration shell has anomalously high entropy as it is trapped between an immobile and bulklike layer. The nonmonotonic entropic signature and long-range perturbations of the hydration shells to Mg2+ may have implications in the molecular recognition of these motifs. For example, we find that low salt stabilizes the parallel configuration of the three-way junction, whereas at normal salt we find antiparallel configurations deduced from the NMR. We use the 2PT analysis to follow the thermodynamics of this transition and find that the free energy barrier is dominated by entropic effects that result from the decreased surface area of the antiparallel form which has a smaller number of low entropy waters in the first monolayer.

Spin injection into a metal from a topological insulator

We study a junction of a topological insulator with a thin two-dimensional nonmagnetic or partially polarized ferromagnetic metallic film deposited on a three-dimensional insulator. We show, by deriving generic boundary conditions applicable to electrons traversing the junction, that there is a finite spin-current injection into the film whose magnitude can be controlled by tuning a voltage V applied across the junction. For ferromagnetic films, the direction of the component of the spin current along the film magnetization can also be tuned by tuning the barrier potential V-0 at the junction. We point out the role of the chiral spin-momentum locking of the Dirac electrons behind this phenomenon and suggest experiments to test our theory.

Generalizing the Amplify-and-Forward Relay Gain Model: An Optimal SEP Perspective

Two models for AF relaying, namely, fixed gain and fixed power relaying, have been extensively studied in the literature given their ability to harness spatial diversity. In fixed gain relaying, the relay gain is fixed but its transmit power varies as a function of the source-relay channel gain. In fixed power relaying, the relay transmit power is fixed, but its gain varies. We revisit and generalize the fundamental two-hop AF relaying model. We present an optimal scheme in which an average power constrained AF relay adapts its gain and transmit power to minimize the symbol error probability (SEP) at the destination. Also derived are insightful and practically amenable closed-form bounds for the optimal relay gain. We then analyze the SEP of MPSK, derive tight bounds for it, and characterize the diversity order for Rayleigh fading. Also derived is an SEP approximation that is accurate to within 0.1 dB. Extensive results show that the scheme yields significant energy savings of 2.0-7.7 dB at the source and relay. Optimal relay placement for the proposed scheme is also characterized, and is different from fixed gain or power relaying. Generalizations to MQAM and other fading distributions are also discussed.

Fidelity susceptibility of one-dimensional models with twisted boundary conditions

Recently it has been shown that the fidelity of the ground state of a quantum many-body system can be used todetect its quantum critical points (QCPs). If g denotes the parameter in the Hamiltonian with respect to which the fidelity is computed, we find that for one-dimensional models with large but finite size, the fidelity susceptibility chi(F) can detect a QCP provided that the correlation length exponent satisfies nu < 2. We then show that chi(F) can be used to locate a QCP even if nu >= 2 if we introduce boundary conditions labeled by a twist angle N theta, where N is the system size. If the QCP lies at g = 0, we find that if N is kept constant, chi(F) has a scaling form given by chi(F) similar to theta(-2/nu) f (g/theta(1/nu)) if theta << 2 pi/N. We illustrate this both in a tight-binding model of fermions with a spatially varying chemical potential with amplitude h and period 2q in which nu = q, and in a XY spin-1/2 chain in which nu = 2. Finally we show that when q is very large, the model has two additional QCPs at h = +/- 2 which cannot be detected by studying the energy spectrum but are clearly detected by chi(F). The peak value and width of chi(F) seem to scale as nontrivial powers of q at these QCPs. We argue that these QCPs mark a transition between extended and localized states at the Fermi energy. DOI: 10.1103/PhysRevB.86.245424

Optimal Linear Codes with a Local-Error-Correction Property

Motivated by applications to distributed storage, Gopalan et al recently introduced the interesting notion of information-symbol locality in a linear code. By this it is meant that each message symbol appears in a parity-check equation associated with small Hamming weight, thereby enabling recovery of the message symbol by examining a small number of other code symbols. This notion is expanded to the case when all code symbols, not just the message symbols, are covered by such ``local'' parity. In this paper, we extend the results of Gopalan et. al. so as to permit recovery of an erased code symbol even in the presence of errors in local parity symbols. We present tight bounds on the minimum distance of such codes and exhibit codes that are optimal with respect to the local error-correction property. As a corollary, we obtain an upper bound on the minimum distance of a concatenated code.

Cloning, expression, purification, crystallization and preliminary X-ray crystallographic study of thymidylate kinase (TTHA1607) from Thermus thermophilus HB8

Nucleotide biosynthesis plays a key role in cell survival and cell proliferation. Thymidylate kinase is an enzyme that catalyses the conversion of dTMP to dTDP using ATP-Mg2+ as a phosphoryl-donor group. This enzyme is present at the junction of the de novo and salvage pathways; thus, any inhibitor designed against it will result in cell death. This highlights the importance of this enzyme as a drug target. Thymidylate kinase from the extremely thermophilic organism Thermus thermophilus HB8 has been expressed, purified and crystallized using the microbatch method. The crystals diffracted to a resolution of 1.83 angstrom and belonged to the orthorhombic space group P2(1)2(1)2(1), with unit-cell parameters a = 39.50, b = 80.29, c = 122.55 angstrom. Preliminary studies revealed the presence of a dimer in the asymmetric unit with a Matthews coefficient (V-M) of 2.18 angstrom(3) Da(-1).

Electrophile-Induced C-C Bond Activation of Vinylcyclopropanes for the Synthesis of Z-Alkylidenetetrahydrofurans

We present a detailed study on the behavior of vinylcyclopropanes as masked donor acceptor system toward the stereoselective synthesis of Z-alkylidenetetrahydrofurans. Results of bromenium catalyzed indirect activation of C-C bond of vinylcyclopropanes and concomitant cyclization to alkylidenetetrahydrofuran and other heterocycles have been discussed. The stereoselective formation of the Z-isomer is strongly controlled by the extent of destabilization of one of the gauche conformers of the vinylcyclopropane. The ring-opening/cyclization step was found to be stereospecific as in the case of DA cyclopropanes. The activation of the C-C bond leads to a tight-carbocation intermediate, which is evident from the complete retention of the stereochemistry. The retention of configuration has been established by a necessary control experiment that rules out the possibility of a double inversion pathway. The present results serve as direct stereochemical evidence in support of a tight ion-pair intermediate versus the controversial S(N)2 pathway. A 2D potential energy scan has been carried out at B3LYP/6-31G(d) level theory to obtain the relative energies of the conformers. The Z-selectivity observed has been explained on the basis of the relative population of the conformers and modeling the intermediate and transition state involved in the reaction at M06-2x/6-31+G(d) level. Energy profile for the cyclization step was modeled considering various possible pathways through which cyclization can happen. The methodology has been successfully demonstrated on vinylcyclobutanes as well.

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).

Another look at tightness

We examine a natural, but non-tight, reductionist security proof for deterministic message authentication code (MAC) schemes in the multi-user setting. If security parameters for the MAC scheme are selected without accounting for the non-tightness in the reduction, then the MAC scheme is shown to provide a level of security that is less than desirable in the multi-user setting. We find similar deficiencies in the security assurances provided by non-tight proofs when we analyze some protocols in the literature including ones for network authentication and aggregate MACs. Our observations call into question the practical value of non-tight reductionist security proofs. We also exhibit attacks on authenticated encryption schemes, disk encryption schemes, and stream ciphers in the multi-user setting.

A multi-layer ultra wide band power splitter

This paper presents analysis and design of multilayer ultra wide band (UWB) power splitter suitable for wireless communications. An UWB power splitter is designed in suspended substrate stripline medium. The quarter wave transformer in the conventional Wilkinson power divider is replaced by broadside coupled lines to achieve tight coupling for broadband operation. The UWB power splitter is analyzed using circuit models of coupled lines and full wave simulator. Experimental results of 3dB power splitter designed using the proposed structure have been verified against the results from circuit simulation and full wave simulation. The return loss is better than 12 dB across the band 3.1GHz to 10.6GHz. Size of the power splitter is 30mm× 20mm×6.38mm.