Geometric Representation of Graphs in Low Dimension Using Axis Parallel Boxes

An axis-parallel k-dimensional box is a Cartesian product R-1 x R-2 x...x R-k where R-i (for 1 <= i <= k) is a closed interval of the form [a(i), b(i)] on the real line. For a graph G, its boxicity box(G) is the minimum dimension k, such that G is representable as the intersection graph of (axis-parallel) boxes in k-dimensional space. The concept of boxicity finds applications in various areas such as ecology, operations research etc. A number of NP-hard problems are either polynomial time solvable or have much better approximation ratio on low boxicity graphs. For example, the max-clique problem is polynomial time solvable on bounded boxicity graphs and the maximum independent set problem for boxicity d graphs, given a box representation, has a left perpendicular1 + 1/c log n right perpendicular(d-1) approximation ratio for any constant c >= 1 when d >= 2. In most cases, the first step usually is computing a low dimensional box representation of the given graph. Deciding whether the boxicity of a graph is at most 2 itself is NP-hard. We give an efficient randomized algorithm to construct a box representation of any graph G on n vertices in left perpendicular(Delta + 2) ln nright perpendicular dimensions, where Delta is the maximum degree of G. This algorithm implies that box(G) <= left perpendicular(Delta + 2) ln nright perpendicular for any graph G. Our bound is tight up to a factor of ln n. We also show that our randomized algorithm can be derandomized to get a polynomial time deterministic algorithm. Though our general upper bound is in terms of maximum degree Delta, we show that for almost all graphs on n vertices, their boxicity is O(d(av) ln n) where d(av) is the average degree.

H N.M.R. studies of protected alpha-aminoisobutyric acid containing peptides. Chemical shift nonequivalence of benzyloxycarbonyl methylene protons

The benzylic methylene protons in a large number of benzyloxycarbonyl alpha-aminoisobutyric acid (Z-Aib) containing peptides, show chemical shift nonequivalence. The magnitude of the geminal nonequivalence is correlated with the involvement of the urethane carbonyl group, in an intramolecular hydrogen bond. Studies of the model compounds Z-Aib-Aib-Ala-NHMe, and Z-Aib-Aib-Aib-Pro-OMe clearly establish the presence of intramolecular hydrogen bonds, involving the urethane CO group. In both compounds marked anisochrony of the benzylic methylene protons is demonstrated. In Z-Aib-Aib-Pro-OMe, where a 4 leads to 1 hydrogen bonded beta-turn is not possible, the benzylic-CH2-protons appear as a singlet in CDCl3 and have a very small chemical shift difference in (CD3)2SO. The observation of such nonequivalence is of value in establishing whether the amino terminal Aib-Pro beta-turn is retained in large peptide-fragments of alamethicin.

Electronic Structure and Bonding in Neutral and Dianionic Boradiphospholes: R ' BC2P2R2 (R=H, tBu, R '=H, Ph)

Classical and non-classical isomers of both neutral and dianionic BC2P2H3 species, which are isolobal to Cp+ and Cp-, are studied at both B3LYP/6-311++G(d,p) and G3B3 levels of theory. The global minimum structure given by B3LYP/6-311+ + G(d,p) for BC2P2H3 is based on a vinylcyclopropenyl-type structure, whereas BC2P2H32- has a planar aromatic cyclopentadienyl-ion-like structure. However, at the G3B3 level, there are three low-energy isomers for BC2P2H3: 1)tricyclopentane, 2) nido and 3) vinylcyclopropenyl-type structures, all within 1.7 kcal mol(-1) of each other. On the contrary, for the dianionic species the cyclic planar structure is still the minimum. In comparison to the isolobal Cp+ and HnCnP5-n+ isomers, BC2P2H3 shows a competition between pi-delocalised vinylcyclopropenyl- and cluster-type structures (nido and tricyclopentane). Substitution of H on C by tBu, and H on B by Ph, in BC2P2H3 increases the energy difference between the low-lying isomers, giving the lowest energy structure as a tricyclopentane type. Similar substitution in BC2P2H32- merely favours different positional isomers of the cyclic planar geometry, as observed in 1) isoelectronic neutral heterodiphospholes EtBu2C2P2 (E=S, Se, Te), 2) monoanionic heterophospholyl rings EtBu2C2P2 (E=P-, As-, Sb-) and 3) polyphospholyl rings anions tBu(5-n)C(n)P(5-n) (n=0-5). The principal factors that affect the stability of three-, four-, and five-membered ring and acyclic geometrical and positional isomers of neutral and dianionic BC2P2H3 isomers appear to be: 1) relative bond strengths, 2) availability of electrons for the empty 2p boron orbital and 3) steric effects of the tBu groups in the HBC(2)P(2)tBu(2) systems.

On the Cubicity of AT-Free Graphs and Circular-Arc Graphs

A unit cube in k dimensions (k-cube) is defined as the Cartesian product R-1 x R-2 x ... x R-k where R-i (for 1 <= i <= k) is a closed interval of the form [a(i), a(i) + 1] on the real line. A graph G on n nodes is said to be representable as the intersection of k-cubes (cube representation in k dimensions) if each vertex of C can be mapped to a k-cube such that two vertices are adjacent in G if and only if their corresponding k-cubes have a non-empty intersection. The cubicity of G denoted as cub(G) is the minimum k for which G can be represented as the intersection of k-cubes. An interesting aspect about cubicity is that many problems known to be NP-complete for general graphs have polynomial time deterministic algorithms or have good approximation ratios in graphs of low cubicity. In most of these algorithms, computing a low dimensional cube representation of the given graph is usually the first step. We give an O(bw . n) algorithm to compute the cube representation of a general graph G in bw + 1 dimensions given a bandwidth ordering of the vertices of G, where bw is the bandwidth of G. As a consequence, we get O(Delta) upper bounds on the cubicity of many well-known graph classes such as AT-free graphs, circular-arc graphs and cocomparability graphs which have O(Delta) bandwidth. Thus we have: 1. cub(G) <= 3 Delta - 1, if G is an AT-free graph. 2. cub(G) <= 2 Delta + 1, if G is a circular-arc graph. 3. cub(G) <= 2 Delta, if G is a cocomparability graph. Also for these graph classes, there axe constant factor approximation algorithms for bandwidth computation that generate orderings of vertices with O(Delta) width. We can thus generate the cube representation of such graphs in O(Delta) dimensions in polynomial time.

Multi-Tone Testing of Linear and Nonlinear Analog Circuits using Polynomial Coefficients

A method of testing for parametric faults of analog circuits based on a polynomial representation of fault-free function of the circuit is presented. The response of the circuit under test (CUT) is estimated as a polynomial in the applied input voltage at relevant frequencies in addition to DC. Classification or Cur is based on a comparison of the estimated polynomial coefficients with those of the fault free circuit. This testing method requires no design for test hardware as might be added to the circuit fly some other methods. The proposed method is illustrated for a benchmark elliptic filter. It is shown to uncover several parametric faults causing deviations as small as 5% from the nominal values.

R3Mn1.5CuV0.5O9 (R = Y, Ho, Er, Tm, Yb and Lu) and Lu3Mn3-3xCu2xVxO9: New noncentro symmetric oxides related to YMnO3

We report formation of new noncentrosymmetric oxides of the formula, R3Mn1.5CuV0.5O9 for R = Y, Ho, Er, Tm, Yb and Lu, possessing the hexagonal RMnO3 (space group P6(3)cm) structure. These oxides could be regarded as the x = 0.5 members of a general series R3Mn3-3xCu2xVxO9. Investigation of the Lu-Mn-Cu-V-O system reveals the existence of isostructural solid solution series, Lu3Mn3-3xCu2xVxO9 for 0 < x <= 0.75. Magnetic and dielectric properties of the oxides are consistent with a random distribution of Mn3+, Cu2+ and V5+ atoms that preserve the noncentrosymmetric RMnO3 structure. (c) 2006 Elsevier Ltd. All rights reserved.

Existence of multiple positive solutions for N-laplacian in a bounded domain in R-N

Let Ohm be a bounded domain in IRN, N greater than or equal to 2, lambda > 0, q is an element of (0, N - 1) and alpha is an element of (1, N/N-1 In this article we show the existence of at least two positive solutions for the following quasilinear elliptic problem with an exponential type nonlinearity:

Conformational characteristics of asparaginyl residues in proteins

Backbone conformations at 1064 asparaginyl residues in 123 non-homologous, high-resolution X-ray structures of proteins were analysed. Asn adopts conformations in left-handed x-helical region and other partially allowed regions in the Ramachandran map more readily than any other non-glycyl residue. Asn conformational clusters in the (phi,psi) regions of left-handed alpha-helix, right-handed alpha-helix and extended (beta) strands were investigated in detail for their occurrence in various secondary structures, especially in beta-turn regions. Preferences were observed for Asn conformations in different positions in various beta-turn types, including the first and fourth positions of the turn. Asparaginyl residues with extended conformations are found to occur frequently in irregular regions, although they are expected to occur predominantly in extended strands or in the third position of type II beta-turns. Asn conformations at the N-cap positions of helices strongly prefer extended conformation than alpha(L), which seems to be characteristic of non-glycyl residues at that position. In the linkers connecting two extended strands and those connecting an alpha-helix and an extended strand, Asn with alpha(L) or alpha(R) conformation is more favoured than Asn with the beta-conformation. Analysis of Asn-Asn doublets and Asn-X-Asn triplets permitted identification of conformational families in such sequences. Results of this investigation provide useful hints in modelling Asn-rich regions in proteins such as malaria parasite coat protein. (C) Munksgaard 1994.

Studies on a chitooligosaccharide-specific lectin from Coccinia indica. Thermodynamics and kinetics of umbelliferyl glycoside binding.

Coccinia indica agglutinin (CIA) is a chitooligosaccharide-specific lectin with two binding sites/homodimer of M(r) 32,000. Quenching studies implied tryptophan involvement in binding activity, which was confirmed by chemical modification experiments (A. R. Sanadi and A. Surolia, submitted for publication). Binding of 4-methylumbelliferyl chitooligosaccharides has been carried out to study their binding by CIA. Reversal experiments confirm the validity of the data previously obtained (A. R. Sanadi and A. Surolia, submitted for publication) from intrinsic fluorescence studies. Surprisingly, unlike wheat germ agglutinin, there is no consistent thermodynamic effect of the chromophoric label on binding activities as compared with the native sugars. From the changes in the optical properties of the chromophoric group upon binding to CIA, it has been possible to confirm that the tryptophan located in the binding site is closest to the fourth subsite. Thermodynamic analysis shows that the binding of the labeled tetrasaccharide is very strongly entropically driven, with the terminal, nonreducing sugar residue protruding from the binding pocket. The results of stopped-flow kinetic studies on the binding of the chromophoric trisaccharide by CIA show that the mechanism of binding is a one-step process.

Fracture analysis of stiffened panels under combined tensile, bending, and shear loads

The objective is to present the formulation of numerically integrated modified virtual crack closure integral technique for concentrically and eccentrically stiffened panels for computation of strain-energy release rate and stress intensity factor based on linear elastic fracture mechanics principles. Fracture analysis of cracked stiffened panels under combined tensile, bending, and shear loads has been conducted by employing the stiffened plate/shell finite element model, MQL9S2. This model can be used to analyze plates with arbitrarily located concentric/eccentric stiffeners, without increasing the total number of degrees of freedom, of the plate element. Parametric studies on fracture analysis of stiffened plates under combined tensile and moment loads have been conducted. Based on the results of parametric,studies, polynomial curve fitting has been carried out to get best-fit equations corresponding to each of the stiffener positions. These equations can be used for computation of stress intensity factor for cracked stiffened plates subjected to tensile and moment loads for a given plate size, stiffener configuration, and stiffener position without conducting finite element analysis.

Creep behaviour of nimonic and R.R. 59 alloys

The Ramberg-Osgood relation which adequately describes the stress-strain curve of a strain-hardening material is extended to formulate the constitutive laws for creep. The constitutive laws which describe primary creep adequately are extended to secondary creep. The results are verified for the case of R.R. 59 at 200°C, Nimonic 80A and Nimonic 90 alloys at 750°C.

Hydrogen bonding in thiolbenzoic acid. Infra-red, ultra-violet, n.m.r. and cryoscopic studies

Dimerization of thiolbenzoic acid has been studied by infra-red, ultra-violet and n.m.r. spectroscopy and cryoscopy. The results indicate that the tendency to form S - H. O hydrogen bonds is not appreciable.

An optimum criterion for eccentrically loaded R. C. columns

An analysis of eccentrically loaded short reinforced concrete columns using a variable failure strain criterion is presented. The method dispenses with the usual procedure of assuming a fixed value for the ultimate strain in concrete. The analysis is based on the use of a simple, single equation for the complete stress-strain curve of concrete and the adoption of a process of maximisation of moment with respect to extreme fibre concrete compressive strain. Columns of rectangular section and loaded eccentrically along one axis only are considered in this paper. A good agreement is observed between the theoretical and experimental values of some test results.

Confined concrete—Its application in R.C. beams and frames

Stress-strain characteristics of concrete confined in steel binders have been determined. A new factor “confinement index” has been introduced for a quantitative measure of the confinement and using these results a “stress-block” has been developed. Tests have been made on simply supported reinforced concrete beams with spiral binder confinement and analysed on the basis of the proposed stress-block. Tests have also been made oon reinforced concrete portal frames and continuous beams with spiral binder confinement at sections of possible plastic hinge formation. An analysis of these tests indicates that a full redistribution of moments has taken place at ultimate.