Representing a cubic graph as the intersection graph of axis-parallel boxes in three dimensions

We show that every graph of maximum degree 3 can be represented as the intersection graph of axis parallel boxes in three dimensions, that is, every vertex can be mapped to an axis parallel box such that two boxes intersect if and only if their corresponding vertices are adjacent. In fact, we construct a representation in which any two intersecting boxes just touch at their boundaries. Further, this construction can be realized in linear time.

On the secret key capacity of the harary graph PIN model

A pairwise independent network (PIN) model consists of pairwise secret keys (SKs) distributed among m terminals. The goal is to generate, through public communication among the terminals, a group SK that is information-theoretically secure from an eavesdropper. In this paper, we study the Harary graph PIN model, which has useful fault-tolerant properties. We derive the exact SK capacity for a regular Harary graph PIN model. Lower and upper bounds on the fault-tolerant SK capacity of the Harary graph PIN model are also derived.

Loss and gain signals in broadband stimulated-Raman spectra: Theoretical analysis

Stimulated optical signals obtained by subjecting the system to a narrow band and a broadband pulse show both gain and loss Raman features at the red and blue side of the narrow beam, respectively. Recently observed temperature-dependent asymmetry in these features Mallick et al., J. Raman Spectrosc. 42, 1883 (2011); Dang et al., Phys. Rev. Lett. 107, 043001 (2011)] has been attributed to the Stokes and anti-Stokes components of the third-order susceptibility, chi((3)). By treating the setup as a steady state of an open system coupled to four quantum radiation field modes, we show that Stokes and anti-Stokes processes contribute to both the loss and gain resonances. chi((3)) predicts loss and gain signals with equal intensity for electronically off-resonant excitation. Some asymmetry may exist for resonant excitation. However, this is unrelated to the Stokes vs anti-Stokes processes. Any observed temperature-dependent asymmetry must thus originate from effects lying outside the chi((3)) regime.

Information content of molecular graph and prediction of gas phase thermal entropy of organic compounds

Entropy is a fundamental thermodynamic property that has attracted a wide attention across domains, including chemistry. Inference of entropy of chemical compounds using various approaches has been a widely studied topic. However, many aspects of entropy in chemical compounds remain unexplained. In the present work, we propose two new information-theoretical molecular descriptors for the prediction of gas phase thermal entropy of organic compounds. The descriptors reflect the bulk and size of the compounds as well as the gross topological symmetry in their structures, all of which are believed to determine entropy. A high correlation () between the entropy values and our information-theoretical indices have been found and the predicted entropy values, obtained from the corresponding statistically significant regression model, have been found to be within acceptable approximation. We provide additional mathematical result in the form of a theorem and proof that might further help in assessing changes in gas phase thermal entropy values with the changes in molecular structures. The proposed information-theoretical molecular descriptors, regression model and the mathematical result are expected to augment predictions of gas phase thermal entropy for a large number of chemical compounds.

Vibrational spectra of fluorene, 1-methylfluorene and 1,8-dimethylfluorene

In this paper, we report the gas phase infrared spectra of fluorene and its methylated derivatives using a heated multipass cell and argon as a carrier gas. The observed spectra in the 4000-400 cm(-1) range have been fitted using the modified scaled quantum mechanical force field (SQMFF) calculation with the 6-311G** basis. The advantage of using the modified SQMFF method is that it scales the force constants to find the best fit to the observed spectral lines by minimizing the fitting error. In this way we are able to assign all the observed fundamental bands in the spectra. With consecutive methyl substitutions two sets of bands are found to shift in a systematic way. The set of four aromatic C-H stretching vibrations around 3000 cm(-1) shifts toward lower frequencies while the single most intense aromatic C-H out-of-plane bending mode around 750 cm(-1) shifts toward higher frequencies. The reason for shifting of aromatic C-H stretching frequency toward lower wave numbers with gradual methyl substitution has been attributed to the lengthening of the C-H bonds due to the +I effect of the methyl groups to the ring current as revealed from the calculations. While the unexpected shifting of the aromatic C-H out-of-plane bend toward higher wave numbers with increasing methyl substitution is ascribed to the lowering of the number of adjacent aromatic C-H bonds on the plane of the benzene ring with gradual methyl substitutions. (C) 2013 Elsevier B.V. All rights reserved.

RES-TOCSY: a simple approach to resolve overlapped H-1 NMR spectra of enantiomers

Chiral auxiliaries are used for the NMR spectroscopic study of enantiomers. Often the presence of impurities, overlap of peaks, line broadening and the multiplicity pattern restrict the chiral analysis in the 1D H-1 NMR spectrum. The present study introduces a simple 2D H-1 NMR experiment to unravel the overlapped spectrum. The experiment separates the spectra of enantiomers, thereby allowing the unambiguous assignment of all the coupled peaks and the measurement of enantiomeric excess (ee) from a single experiment even in combinatorial mixtures.

Electronic band Structure and Photoemission Spectra of Graphene on Silicon Substrate

Synergizing graphene on silicon based nanostructures is pivotal in advancing nano-electronic device technology. A combination of molecular dynamics and density functional theory has been used to predict the electronic energy band structure and photo-emission spectrum for graphene-Si system with silicon as a substrate for graphene. The equilibrium geometry of the system after energy minimization is obtained from molecular dynamics simulations. For the stable geometry obtained, density functional theory calculations are employed to determine the energy band structure and dielectric constant of the system. Further the work function of the system which is a direct consequence of photoemission spectrum is calculated from the energy band structure using random phase approximations.

Parallel Flow-Sensitive Pointer Analysis by Graph-Rewriting

Precise pointer analysis is a problem of interest to both the compiler and the program verification community. Flow-sensitivity is an important dimension of pointer analysis that affects the precision of the final result computed. Scaling flow-sensitive pointer analysis to millions of lines of code is a major challenge. Recently, staged flow-sensitive pointer analysis has been proposed, which exploits a sparse representation of program code created by staged analysis. In this paper we formulate the staged flow-sensitive pointer analysis as a graph-rewriting problem. Graph-rewriting has already been used for flow-insensitive analysis. However, formulating flow-sensitive pointer analysis as a graph-rewriting problem adds additional challenges due to the nature of flow-sensitivity. We implement our parallel algorithm using Intel Threading Building Blocks and demonstrate considerable scaling (upto 2.6x) for 8 threads on a set of 10 benchmarks. Compared to the sequential implementation of staged flow-sensitive analysis, a single threaded execution of our implementation performs better in 8 of the benchmarks.

Diffusing-wave spectroscopy in an inhomogeneous object: Local viscoelastic spectra from ultrasound-assisted measurement of correlation decay arising from the ultrasound focal volume

We demonstrate diffusing-wave spectroscopy (DWS) in a localized region of a viscoelastically inhomogeneous object by measurement of the intensity autocorrelation g(2)(tau)] that captures only the decay introduced by the temperature-induced Brownian motion in the region. The region is roughly specified by the focal volume of an ultrasound transducer which introduces region specific mechanical vibration owing to insonification. Essential characteristics of the localized non-Markovian dynamics are contained in the decay of the modulation depth M(tau)], introduced by the ultrasound forcing in the focal volume selected, on g(2)(tau). The modulation depth M(tau(i)) at any delay time tau(i) can be measured by short-time Fourier transform of g(2)(tau) and measurement of the magnitude of the spectrum at the ultrasound drive frequency. By following the established theoretical framework of DWS, we are able to connect the decay in M(tau) to the mean-squared displacement (MSD) of scattering centers and the MSD to G*(omega), the complex viscoelastic spectrum. A two-region composite polyvinyl alcohol phantom with different viscoelastic properties is selected for demonstrating local DWS-based recovery of G*(omega) corresponding to these regions from the measured region specific M(tau(i))vs tau(i). The ultrasound-assisted measurement of MSD is verified by simulating, using a generalized Langevin equation (GLE), the dynamics of the particles in the region selected as well as by the usual DWS experiment without the ultrasound. It is shown that whereas the MSD obtained by solving the GLE without the ultrasound forcing agreed with its experimental counterpart covering small and large values of tau, the match was good only in the initial transients in regard to experimental measurements with ultrasound.

REPRESENTING A CUBIC GRAPH AS THE INTERSECTION GRAPH OF AXIS-PARALLEL BOXES IN THREE DIMENSIONS

We show that every graph of maximum degree 3 can be represented as the intersection graph of axis parallel boxes in three dimensions, that is, every vertex can be mapped to an axis parallel box such that two boxes intersect if and only if their corresponding vertices are adjacent. In fact, we construct a representation in which any two intersecting boxes touch just at their boundaries.

BELIEF PROPAGATION FOR OPTIMAL EDGE COVER IN THE RANDOM COMPLETE GRAPH

We apply the objective method of Aldous to the problem of finding the minimum-cost edge cover of the complete graph with random independent and identically distributed edge costs. The limit, as the number of vertices goes to infinity, of the expected minimum cost for this problem is known via a combinatorial approach of Hessler and Wastlund. We provide a proof of this result using the machinery of the objective method and local weak convergence, which was used to prove the (2) limit of the random assignment problem. A proof via the objective method is useful because it provides us with more information on the nature of the edge's incident on a typical root in the minimum-cost edge cover. We further show that a belief propagation algorithm converges asymptotically to the optimal solution. This can be applied in a computational linguistics problem of semantic projection. The belief propagation algorithm yields a near optimal solution with lesser complexity than the known best algorithms designed for optimality in worst-case settings.

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.

Rotational spectra of propargyl alcohol dimer: A dimer bound with three different types of hydrogen bonds

Pure rotational spectra of the propargyl alcohol dimer and its three deuterium isotopologues have been observed in the 4 to 13 GHz range using a pulsed-nozzle Fourier transform microwave spectrometer. For the parent dimer, a total of 51 transitions could be observed and fitted within experimental uncertainty. For two mono-substituted and one bi-substituted deuterium isotopologues, a total of 14, 17, and 19 transitions were observed, respectively. The observed rotational constants for the parent dimer A = 2321.8335(4) MHz, B = 1150.4774(2) MHz, and C = 1124.8898(2) MHz] are close to those of the most stable structure predicted by ab initio calculations. Spectra of the three deuterated isotopologues and Kraitchman analysis positively confirm this structure. Geometrical parameters and ``Atoms in Molecules'' analysis on the observed structure reveal that the two propargyl alcohol units in the dimer are bound by three different types of hydrogen bonds: O-H center dot center dot center dot O, O-H center dot center dot center dot pi, and C-H center dot center dot center dot pi. To the best of our knowledge, propargyl alcohol seems to be the smallest molecule forming a homodimer with three different points of contact. (C) 2014 AIP Publishing LLC.

Reconstruction of Two-Dimensional Spectra from One-Dimensional Projections-Examples from Solid State NMR

The use of Projection Reconstruction (PR) to obtain two-dimensional (2D) spectra from one-dimensional (1D) data in the solid state is illustrated. The method exploits multiple 1D spectra obtained using magic angle spinning and off-magic angle spinning. The spectra recorded under the influence of scaled heteronuclear scalar and dipolar couplings in the presence of homonuclear dipolar decoupling sequences have been used to reconstruct J/D Resolved 2D-NMR spectra. The use of just two 1D spectra is observed sufficient to reconstruct a J-resolved 2D-spectrum while a Separated Local Field (SLF) 2D-NMR spectrum could be obtained from three 1D spectra. The experimental techniques for recording the 10 spectra and procedure of reconstruction are discussed and the reconstructed results are compared with 20 experiments recorded in traditional methods. The application of the technique has been made to a solid polycrystalline sample and to a uniaxially oriented liquid crystal. Implementation of PR-NMR in solid state provides high-resolution spectra as well as leads to significant reduction in experimental time. The experiments are relatively simple and are devoid of several technical complications involved in performing the 2D experiments.

Belief propagation for minimum weight many-to-one matchings in the random complete graph

In a complete bipartite graph with vertex sets of cardinalities n and n', assign random weights from exponential distribution with mean 1, independently to each edge. We show that, as n -> infinity, with n' = n/alpha] for any fixed alpha > 1, the minimum weight of many-to-one matchings converges to a constant (depending on alpha). Many-to-one matching arises as an optimization step in an algorithm for genome sequencing and as a measure of distance between finite sets. We prove that a belief propagation (BP) algorithm converges asymptotically to the optimal solution. We use the objective method of Aldous to prove our results. We build on previous works on minimum weight matching and minimum weight edge cover problems to extend the objective method and to further the applicability of belief propagation to random combinatorial optimization problems.