Cubicity, boxicity, and vertex cover

A k-dimensional box is the cartesian product R-1 x R-2 x ... x R-k where each R-i is a closed interval on the real line. The boxicity of a graph G,denoted as box(G), is the minimum integer k such that G is the intersection graph of a collection of k-dimensional boxes. A unit cube in k-dimensional space or a k-cube is defined as the cartesian product R-1 x R-2 x ... x R-k where each Ri is a closed interval on the real line of the form [a(i), a(i) + 1]. The cubicity of G, denoted as cub(G), is the minimum k such that G is the intersection graph of a collection of k-cubes. In this paper we show that cub(G) <= t + inverted right perpendicularlog(n - t)inverted left perpendicular - 1 and box(G) <= left perpendiculart/2right perpendicular + 1, where t is the cardinality of a minimum vertex cover of G and n is the number of vertices of G. We also show the tightness of these upper bounds. F.S. Roberts in his pioneering paper on boxicity and cubicity had shown that for a graph G, box(G) <= left perpendicularn/2right perpendicular and cub(G) <= inverted right perpendicular2n/3inverted left perpendicular, where n is the number of vertices of G, and these bounds are tight. We show that if G is a bipartite graph then box(G) <= inverted right perpendicularn/4inverted left perpendicular and this bound is tight. We also show that if G is a bipartite graph then cub(G) <= n/2 + inverted right perpendicularlog n inverted left perpendicular - 1. We point out that there exist graphs of very high boxicity but with very low chromatic number. For example there exist bipartite (i.e., 2 colorable) graphs with boxicity equal to n/4. Interestingly, if boxicity is very close to n/2, then chromatic number also has to be very high. In particular, we show that if box(G) = n/2 - s, s >= 0, then chi (G) >= n/2s+2, where chi (G) is the chromatic number of G.

Boxicity of Halin graphs

A k-dimensional box is the Cartesian product R-1 x R-2 x ... x R-k where each R-i is a closed interval on the real line. The boxicity of a graph G, denoted as box(G) is the minimum integer k such that G is the intersection graph of a collection of k-dimensional boxes. Halin graphs are the graphs formed by taking a tree with no degree 2 vertex and then connecting its leaves to form a cycle in such a way that the graph has a planar embedding. We prove that if G is a Halin graph that is not isomorphic to K-4, then box(G) = 2. In fact, we prove the stronger result that if G is a planar graph formed by connecting the leaves of any tree in a simple cycle, then box(G) = 2 unless G is isomorphic to K4 (in which case its boxicity is 1).

Site-Specific Functionalization of Hyperbranched Polymers Using ``Click'' Chemistry

Different strategies for functionalization of the core region and periphery of core-shell type hyperbranched polymers (HBP) using the ``click'' reaction have been explored. For achieving periphera functionalization, an AB(2) + A-R-1 + A-R-2 type copolymerization approach was used, where A-R-1 is heptaethylene glycol monomethyl ether (HPEG-M) and A-R-2 is tetraethylene glycol monopropargyl ether (TEG-P). A very small mole fraction of the propargyl containing monomer, TEG-P, was used to ensure that the water-solubility of the hyperbranched polymer is minimally affected. Similarly, to incorporate propargyl groups in the core region, a new propargyl group bearing B-2-typ monomer was designed and utilized in an AB(2) + A(2) + B-2 + A-R-1 type copolymerization, such that the total mole fraction of B-2 + A(2) is small and their mole-ratio is 1: 1. Further, using a combination of both the above approaches, namely AB(2) + A(2) + B-2 + A-R-1 + A-R-2, hyperbranched structures that incorporate propargyl groups both at theperiphery and within the core were synthesized. Since the AB(2) monomer carries a hexamethylene spacer (C-6) and the periphery is PEGylated all the derivatized polymers form core-shell type structures in aqueous solutions. Attempts were made to ascertain and probe the location of the propargyl groups in these HBP's, by ``clicking'' azidomethylpyrene, onto them. However, the fluorescence spectra of aqueous solutions of the pyrene derivatized polymers were unable to discriminate between the various locations, possibly because the relatively hydrophobic pyrene units insert themselves into the core region to minimize exposure to water.

Improved bounds on the radius and curvature of the K pi scalar form factor and implications to low-energy theorems

We obtain stringent bounds in the < r(2)>(K pi)(S)-c plane where these are the scalar radius and the curvature parameters of the scalar K pi form factor, respectively, using analyticity and dispersion relation constraints, the knowledge of the form factor from the well-known Callan-Treiman point m(K)(2)-m(pi)(2), as well as at m(pi)(2)-m(K)(2), which we call the second Callan-Treiman point. The central values of these parameters from a recent determination are accomodated in the allowed region provided the higher loop corrections to the value of th form factor at the second Callan-Treiman point reduce the one-loop result by about 3% with F-K/F-pi = 1.21. Such a variation in magnitude at the second Callan-Treiman point yields 0.12 fm(2) less than or similar to < r(2)>(K pi)(S) less than or similar to 0.21 fm(2) and 0.56 GeV-4 less than or similar to c less than or similar to 1.47 GeV-4 and a strong correlation between them. A smaller value of F-K/F-pi shifts both bounds to lower values.

An elementary approach to gap theorems

Using elementary comparison geometry, we prove: Let (M, g) be a simply-connected complete Riemannian manifold of dimension >= 3. Suppose that the sectional curvature K satisfies -1-s(r) <= K <= -1, where r denotes distance to a fixed point in M. If lim(r ->infinity) e(2r) s(r) = 0, then (M, g) has to be isometric to H-n.The same proof also yields that if K satisfies -s(r) <= K <= 0 where lim(r ->infinity) r(2) s(r) = 0, then (M, g) is isometric to R-n, a result due to Greene and Wu.Our second result is a local one: Let (M, g) be any Riemannian manifold. For a E R, if K < a on a geodesic ball Bp (R) in M and K = a on partial derivative B-p (R), then K = a on B-p (R).

A composition dependent thermal behavior of GexSe35-xTe65 glasses

Alternating differential scanning calorimetric (ADSC) studies have been performed to understand the thermal behavior of bulk GexSe35-xTe65 glasses (17 <= x <= 25); it is found that the glasses with x <= 20 exhibit two crystallization exotherms (T-c1 & T-c2). On the other hand, those with x >= 20.5, show a single crystallization reaction upon heating. The exothermic reaction at T-c1 has been found to correspond to the partial crystallization of the glass into hexagonal Te and the reaction at T-c2 is associated with the additional crystallization of rhombohedral Ge-Te phase. The glass transition temperature of GexSe35-xTe65 glasses is found to show a linear but not-steep increase, indicating a progressive, but a gradual increase in network connectivity with Ge addition. It is also found that T-c1 of GexSe35-xTe65 glasses with x <= 20, increases progressively with Ge content and eventually merges with T-c2 at x approximate to 20.5 (< r > = 2.41); this behavior has been understood on the basis of the reduction in Te-Te bonds of lower energy and increase in Ge-Te bonds of higher energy, with increasing Ge content. Apart from the interesting composition dependent crystallization, an anomalous melting behavior is also exhibited by the GexSe35-xTe65 glasses.

Microstrip square ring antenna for dual-band operation

This paper presents a generalized approach to design an electromagnetically coupled microstrip ring antenna for dual-band operation. By widening two opposite sides of a square ring antenna, its fractional bandwidth at the primary resonance mode can be increased significantly so that it may be used for practical applications. By attaching a stub to the inner edge of the side opposite to the feed arm, some of the losses in electrical length caused by widening can be regained. More importantly, this addition also alters the current distribution on the antenna and directs radiations at the second resonant frequency towards boresight. It has also been observed that for the dual frequency configurations studied, the ratio of the resonant frequencies (center dot r(2)center dot center dot r(1)) can range between 1.55 and 2.01. This shows flexibility in designing dual frequency antennas with a desired pair of resonant frequencies.

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.

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.

Evidence for a thermally reversing window in bulk Ge-Te-Si glasses revealed by alternating differential scanning calorimetry

Experiments on Ge15Tc85-xSix glasses (2 <= x <= 12) using alternating differential scanning calorimetry (ADSC) indicate that these glasses exhibit one glass transition and two crystallization reactions upon heating. The glass transition temperature has been found to increase almost linearly with silicon content, in the entire composition tie-line. The first crystallization temperature (T-cl) exhibits an increase with silicon content for x<5; T-cl remains almost a constant in the composition range 5 < x <= 10 and it increases comparatively more sharply with silicon content thereafter. The specific heat change (Delta C-p) is found to decrease with an increase in silicon content, exhibiting a minimum at x=5 (average coordination number, (r) = 2.4); a continuous increase is seen in Delta C-p with silicon concentration above x = 5. The effects seen in the variation with composition of T-cl and Delta C-p at x=5, are the specific signatures of the mean-field stiffness threshold at (r) = 2.4. Furthermore, a broad trough is seen in the enthalpy change (Delta H-NR), which is indicative of a thermally reversing window in Ge15Te85-xSix glasses in the composition range 2 <= x <= 6 (2.34 <= (r) <= 2.42).

High pressure studies on the electrical resistivity of As-Te-bond Si glasses and the effect of network topological thresholds

The variation of resistivity in an amorphous As30Te70-xSix system of glasses with high pressure has been studied for pressures up to 8 GPa. It is found that the electrical resistivity and the conduction activation energy decrease continuously with increase in pressure, and samples become metallic in the pressure range 1.0-2.0 GPa. Temperature variation studies carried out at a pressure of 0.92 GPa show that the activation energies lie in the range 0.16-0.18eV. Studies on the composition/average co-ordination number (r) dependence of normalized electrical resistivity at different pressures indicate that rigidity percolation is extended, the onset of the intermediate phase is around (r) = 2.44, and completion at (r) = 2.56, respectively, while the chemical threshold is at (r) = 2.67. These results compare favorably with those obtained from electrical switching and differential scanning calorimetric studies.

Fluorescent resonant excitation energy transfer in linear polyenes

We have studied the dynamics of excitation transfer between two conjugated polyene molecules whose intermolecular separation is comparable to the molecular dimensions. We have employed a correlated electron model that includes both the charge-charge, charge-bond, and bond-bond intermolecular electron repulsion integrals. We have shown that the excitation transfer rate varies as inverse square of donor-acceptor separation R-2 rather than as R-6, suggested by the Foumlrster type of dipolar approximation. Our time-evolution study alsom shows that the orientational dependence on excitation transfer at a fixed short donor-acceptor separation cannot be explained by Foumlrster type of dipolar approximation beyond a certain orientational angle of rotation of an acceptor polyene with respect to the donor polyene. The actual excitation transfer rate beyond a certain orientational angle is faster than the Foumlrster type of dipolar approximation rate. We have also studied the excitation transfer process in a pair of push-pull polyenes for different push-pull strengths. We have seen that, depending on the push-pull strength, excitation transfer could occur to other dipole coupled states. Our study also allows for the excitation energy transfer to optically dark states which are excluded by Foumlrster theory since the one-photon transition intensity to these states (from the ground state) is zero.

Adsorption of anionic dyes on chitosan grafted poly(alkyl methacrylate)s

Chitosan grafted poly(alkyl methacrylate)s (namely chitosan grafted poly(methyl methacrylate) (ChgPMMA), chitosan grafted poly(ethyl methacrylate)(ChgPEMA), chitosan grafted poly(butyl methacrylate) (ChgPBMA) and chitosan grafted poly(hexyl methacrylate) (ChgPHMA)) were synthesized and characterized by using FT-IR and C-13 NMR techniques. The adsorption batch experiments on these grafted copolymers were conducted by using an anionic sulfonated dye. Orange-G. A pseudo-second-order kinetic model was used to determine the kinetics of adsorption. The effect of grafting, effect of process variables and the effect of different sulfonated anionic dyes (Orange-C, Congo Red, Remazol Brill Blue R and Methyl Blue) on the adsorption kinetics was determined. The Langmuir and Freundlich models were used to fit the adsorption isotherms and from the values of correlation coefficients (R-2), it was observed that the experimental data fits very well to the Langmuir model. The values of the maximum adsorption capacity of the adsorbents follow the order: ChgPMMA > ChgPEMA > ChgPBMA > ChgPHMA > chitosan. (C) 2010 Elsevier B.V. All rights reserved.

The hardness of approximating the boxicity, cubicity and threshold dimension of a graph

A k-dimensional box is the Cartesian product R-1 X R-2 X ... X R-k where each R-i is a closed interval on the real line. The boxicity of a graph G, denoted as box(G), is the minimum integer k such that G can be represented as the intersection graph of a collection of k-dimensional boxes. A unit cube in k-dimensional space or a k-cube is defined as the Cartesian product R-1 X R-2 X ... X R-k where each R-i is a closed interval oil the real line of the form a(i), a(i) + 1]. The cubicity of G, denoted as cub(G), is the minimum integer k such that G can be represented as the intersection graph of a collection of k-cubes. The threshold dimension of a graph G(V, E) is the smallest integer k such that E can be covered by k threshold spanning subgraphs of G. In this paper we will show that there exists no polynomial-time algorithm for approximating the threshold dimension of a graph on n vertices with a factor of O(n(0.5-epsilon)) for any epsilon > 0 unless NP = ZPP. From this result we will show that there exists no polynomial-time algorithm for approximating the boxicity and the cubicity of a graph on n vertices with factor O(n(0.5-epsilon)) for any epsilon > 0 unless NP = ZPP. In fact all these hardness results hold even for a highly structured class of graphs, namely the split graphs. We will also show that it is NP-complete to determine whether a given split graph has boxicity at most 3. (C) 2010 Elsevier B.V. All rights reserved.

Studies on ß-arylhydrazone-imine nickel(II) complexes—Examples of metal template syntheses

ß-arylhydrazone-imine ligand complexes of nickel(II), namely, 4,10-dimethyl-5,9-diazatrideca-4,9-diene-2,12-dione-3,11-diphenylhydrazonato nickel(II), Ni(acacpn)(N2Ph-R)2 and 1,11-diphenyl-3,9-dimethyl-4,8-diazaun-deca-3,8-diene,1,11-dione-2,10-diphenyl hydrazonato nickel(II), Ni (beacpn) (N2Ph-R)2, [R = H, o-CH3p-CH3] have been prepared by metal template reactions and characterized. Both the azomethine nitrogens and α-nitrogens of bis-hydrazone form the coordination sites of the square-planar geometry around the nickel(II) ion. Loss of CO from the molecule and subsequently an interesting methyl group migration to the nucleus of the chelate ring have been observed in the mass spectrum. Structures are proposed based on the spectral and magnetic properties.