Cubicity of Interval Graphs and the Claw Number

Let G(V, E) be a simple, undirected graph where V is the set of vertices and E is the set of edges. A b-dimensional cube is a Cartesian product l(1) x l(2) x ... x l(b), where each l(i) is a closed interval of unit length on the real line. The cub/city of G, denoted by cub(G), is the minimum positive integer b such that the vertices in G can be mapped to axis parallel b-dimensional cubes in such a way that two vertices are adjacent in G if and only if their assigned cubes intersect. An interval graph is a graph that can be represented as the intersection of intervals on the real line-i.e. the vertices of an interval graph can be mapped to intervals on the real line such that two vertices are adjacent if and only if their corresponding intervals overlap. Suppose S(m) denotes a star graph on m+1 nodes. We define claw number psi(G) of the graph to be the largest positive integer m such that S(m) is an induced subgraph of G. It can be easily shown that the cubicity of any graph is at least log(2) psi(G)]. In this article, we show that for an interval graph G log(2) psi(G)-]<= cub(G)<=log(2) psi(G)]+2. It is not clear whether the upper bound of log(2) psi(G)]+2 is tight: till now we are unable to find any interval graph with cub(G)> (log(2)psi(G)]. We also show that for an interval graph G, cub(G) <= log(2) alpha], where alpha is the independence number of G. Therefore, in the special case of psi(G)=alpha, cub(G) is exactly log(2) alpha(2)]. The concept of cubicity can be generalized by considering boxes instead of cubes. A b-dimensional box is a Cartesian product l(1) x l(2) x ... x l(b), where each I is a closed interval on the real line. The boxicity of a graph, denoted box(G), is the minimum k such that G is the intersection graph of k-dimensional boxes. It is clear that box(G)<= cub(G). From the above result, it follows that for any graph G, cub(G) <= box(G)log(2) alpha]. (C) 2010 Wiley Periodicals, Inc. J Graph Theory 65: 323-333, 2010

A local 2-approximation algorithm for the vertex cover problem

We present a distributed 2-approximation algorithm for the minimum vertex cover problem. The algorithm is deterministic, and it runs in (Δ + 1)2 synchronous communication rounds, where Δ is the maximum degree of the graph. For Δ = 3, we give a 2-approximation algorithm also for the weighted version of the problem.

A simple local 3-approximation algorithm for vertex cover

We present a local algorithm (constant-time distributed algorithm) for finding a 3-approximate vertex cover in bounded-degree graphs. The algorithm is deterministic, and no auxiliary information besides port numbering is required. (c) 2009 Elsevier B.V. All rights reserved.

A local 2-approximation algorithm for the vertex cover problem

We present a distributed 2-approximation algorithm for the minimum vertex cover problem. The algorithm is deterministic, and it runs in (Δ + 1)2 synchronous communication rounds, where Δ is the maximum degree of the graph. For Δ = 3, we give a 2-approximation algorithm also for the weighted version of the problem.

Non-contractible non-edges in 2-connected graphs

Any pair of non-adjacent vertices forms a non-edge in a graph. Contraction of a non-edge merges two non-adjacent vertices into a single vertex such that the edges incident on the non-adjacent vertices are now incident on the merged vertex. In this paper, we consider simple connected graphs, hence parallel edges are removed after contraction. The minimum number of nodes whose removal disconnects the graph is the connectivity of the graph. We say a graph is k-connected, if its connectivity is k. A non-edge in a k-connected graph is contractible if its contraction does not result in a graph of lower connectivity. Otherwise the non-edge is non-contractible. We focus our study on non-contractible non-edges in 2-connected graphs. We show that cycles are the only 2-connected graphs in which every non-edge is non-contractible. (C) 2010 Elsevier B.V. All rights reserved.

Squeezed states, photon-number distributions, and U(l) invariance

We study the photon-number distribution in squeezed states of a single-mode radiation field. A U(l)-invariant squeezing criterion is compared and contrasted with a more restrictive criterion, with the help of suggestive geometric representations. The U(l) invariance of the photon-number distribution in a squeezed coherent state, with arbitrary complex squeeze and displacement parameters, is explicitly demonstrated. The behavior of the photon-number distribution for a representative value of the displacement and various values of the squeeze parameter is numerically investigated. A new kind of giant oscillation riding as an envelope over more rapid oscillations in this distribution is demonstrated.

Improved mechanical properties of polymer nanocomposites incorporating graphene-like BN: Dependence on the number of BN layers

The mechanical properties of composites of polymethylmethacrylate (PMMA) with two-dimensional graphene-like boron nitride (BN) have been investigated to explore the dependence of the properties on the number of BN layers. This study demonstrates that significantly improved mechanical properties are exhibited by the composite with the fewest number of BN layers. Thus, with incorporation of three BN layers, the hardness and elastic modulus of the composite showed an increase of 125% and 130%, respectively, relative to pure PMMA. (C) 2010 Acta Materialia Inc. Published by Elsevier Ltd. All rights reserved.

Boxicity and Poset Dimension

Let G be a simple, undirected, finite graph with vertex set V(G) and edge set E(C). A k-dimensional box is a Cartesian product of closed intervals a(1), b(1)] x a(2), b(2)] x ... x a(k), b(k)]. The boxicity of G, box(G) is the minimum integer k such that G can be represented as the intersection graph of k-dimensional boxes, i.e. each vertex is mapped to a k-dimensional box and two vertices are adjacent in G if and only if their corresponding boxes intersect. Let P = (S, P) be a poset where S is the ground set and P is a reflexive, anti-symmetric and transitive binary relation on S. The dimension of P, dim(P) is the minimum integer l such that P can be expressed as the intersection of t total orders. Let G(P) be the underlying comparability graph of P. It is a well-known fact that posets with the same underlying comparability graph have the same dimension. The first result of this paper links the dimension of a poset to the boxicity of its underlying comparability graph. In particular, we show that for any poset P, box(G(P))/(chi(G(P)) - 1) <= dim(P) <= 2box(G(P)), where chi(G(P)) is the chromatic number of G(P) and chi(G(P)) not equal 1. The second result of the paper relates the boxicity of a graph G with a natural partial order associated with its extended double cover, denoted as G(c). Let P-c be the natural height-2 poset associated with G(c) by making A the set of minimal elements and B the set of maximal elements. We show that box(G)/2 <= dim(P-c) <= 2box(G) + 4. These results have some immediate and significant consequences. The upper bound dim(P) <= 2box(G(P)) allows us to derive hitherto unknown upper bounds for poset dimension. In the other direction, using the already known bounds for partial order dimension we get the following: (I) The boxicity of any graph with maximum degree Delta is O(Delta log(2) Delta) which is an improvement over the best known upper bound of Delta(2) + 2. (2) There exist graphs with boxicity Omega(Delta log Delta). This disproves a conjecture that the boxicity of a graph is O(Delta). (3) There exists no polynomial-time algorithm to approximate the boxicity of a bipartite graph on n vertices with a factor of O(n(0.5-epsilon)) for any epsilon > 0, unless NP=ZPP.

Five-level inverter scheme for an open-end winding induction machine with less number of switches

Higher level of inversion is achieved with a less number of switches in the proposed scheme. The scheme proposes a five-level inverter for an open-end winding induction motor which uses only two DC-link rectifiers of voltage rating of Vdc/4, a neutral-point clamped (NPC) three-level inverter and a two-level inverter. Even though the two-level inverter is connected to the high-voltage side, it is always in square-wave operation. Since the two-level inverter is not switching in a pulse width modulated fashion and the magnitude of switching transient is only half compared to the convention three-level NPC inverter, the switching losses and electromagnetic interference is not so high. The scheme is experimentally verified on a 2.5 kW induction machine.

On kuhnels 9-vertex complex projective plane

We present an elementary combinatorial proof of the existence and uniqueness of the 9-vertex triangulation of C P2. The original proof of existence, due to Kuhnel, as well as the original proof of uniqueness, due to Kuhnel and Lassmann, were based on extensive computer search. Recently Arnoux and Marin have used cohomology theory to present a computer-free proof. Our proof has the advantage of displaying a canonical copy of the affine plane over the three-element field inside this complex in terms of which the entire complex has a very neat and short description. This explicates the full automorphism group of the Kuhnel complex as a subgroup of the automorphism group of this affine plane. Our method also brings out the rich combinatorial structure inside this complex.

Systematics of the magnetic-Prandtl-number dependence of homogeneous, isotropic magnetohydrodynamic turbulence

We present the results of our detailed pseudospectral direct numerical simulation (DNS) studies, with up to 1024(3) collocation points, of incompressible, magnetohydrodynamic (MHD) turbulence in three dimensions, without a mean magnetic field. Our study concentrates on the dependence of various statistical properties of both decaying and statistically steady MHD turbulence on the magnetic Prandtl number Pr-M over a large range, namely 0.01 <= Pr-M <= 10. We obtain data for a wide variety of statistical measures, such as probability distribution functions (PDFs) of the moduli of the vorticity and current density, the energy dissipation rates, and velocity and magnetic-field increments, energy and other spectra, velocity and magnetic-field structure functions, which we use to characterize intermittency, isosurfaces of quantities, such as the moduli of the vorticity and current density, and joint PDFs, such as those of fluid and magnetic dissipation rates. Our systematic study uncovers interesting results that have not been noted hitherto. In particular, we find a crossover from a larger intermittency in the magnetic field than in the velocity field, at large Pr-M, to a smaller intermittency in the magnetic field than in the velocity field, at low Pr-M. Furthermore, a comparison of our results for decaying MHD turbulence and its forced, statistically steady analogue suggests that we have strong universality in the sense that, for a fixed value of Pr-M, multiscaling exponent ratios agree, at least within our error bars, for both decaying and statistically steady homogeneous, isotropic MHD turbulence.

Unsteady nonsimilar two-dimensional and axisymmetric water boundary layers with variable viscosity and prandtl number

The influence of temperature-dependent viscosity and Prandtl number on the unsteady laminar nonsimilar forced convection flow over two-dimensional and axisymmetric bodies has been examined where the unsteadiness and (or) nonsimilarity are (is) due to the free stream velocity, mass transfer, and transverse curvature. The partial differential equations governing the flow which involve three independent variables have been solved numerically using an implicit finite-difference scheme along with a quasilinearization technique. It is found that both the skin friction and heat transfer strongly respond to the unsteady free stream velocity distributions. The unsteadiness and injection cause the location of zero skin friction to move upstream. However, the effect of variable viscosity and Prandtl number is to move it downstream. The heat transfer is found to depend strongly on viscous dissipation, but the skin friction is little affected by it. In general, the results pertaining to variable fluid properties differ significantly, from those of constant fluid properties.

Differential influence of ions on the copy number of plasmids in Thiobacillus ferrooxidans

Thiobacillus ferrooxidans MAL4-1, an isolate from Malanjkhand copper mines, India, was adapted to grow in the presence of high concentration (30 gL(-1)) of Cu2+, resulting in a 15-fold increase in its tolerance to Cu2+. While wild-type T. ferrooxidans MAL4-1 contained multiple plasmids, cultures adapted to Cu2+ concentrations of 20 gL(-1) or more showed a drastic reduction in the copy number of the plasmids. The reduction for three of the plasmids was estimated to be over 50-fold. Examination of the plasmid profiles of the strains adapted to high concentration of SO42- anion (as Na2SO4 or ZnSO4) indicated that the reduction in plasmid copy number is not owing to SO42- anion, but is specific for Cu2+. The effect of mercury on the plasmids was similar to that of copper. Deadaptation of the Cu2+- Or Hg2+-adapted T. ferrooxidans resulted in restoration of the plasmids to the original level within the first passage. The fact that the plasmid copy number, in general, is drastically reduced in Cu2+-adapted T. ferrooxidans suggests that resistance to copper is chromosome mediated. This is the first report of a selective negative influence of copper ions on the copy number of plasmids in T. ferrooxidans.

A polynomial bound on the number of light cycles in an undirected graph

Let G be an undirected graph with a positive real weight on each edge. It is shown that the number of minimum-weight cycles of G is bounded above by a polynomial in the number of edges of G. A similar bound holds if we wish to count the number of cycles with weight at most a constant multiple of the minimum weight of a cycle of G.