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.

d-Regular Graphs of Acyclic Chromatic Index at Least d+2

An acyclic edge coloring of a graph is a proper edge coloring such that there are no bichromatic cycles. The acyclic chromatic index of a graph is the minimum number k such that there is an acyclic edge coloring using k colors and is denoted by a'(G). It was conjectured by Alon, Suclakov and Zaks (and earlier by Fiamcik) that a'(G) <= Delta+2, where Delta = Delta(G) denotes the maximum degree of the graph. Alon et al. also raised the question whether the complete graphs of even order are the only regular graphs which require Delta+2 colors to be acyclically edge colored. In this article, using a simple counting argument we observe not only that this is not true, but in fact all d-regular graphs with 2n vertices and d>n, requires at least d+2 colors. We also show that a'(K-n,K-n) >= n+2, when n is odd using a more non-trivial argument. (Here K-n,K-n denotes the complete bipartite graph with n vertices on each side.) This lower bound for Kn,n can be shown to be tight for some families of complete bipartite graphs and for small values of n. We also infer that for every d, n such that d >= 5, n >= 2d+3 and dn even, there exist d-regular graphs which require at least d+2-colors to be acyclically edge colored. (C) 2009 Wiley Periodicals, Inc. J Graph Theory 63: 226-230, 2010.

Electrochemical Functionalization of a Gold Electrode with Redox-Active Self-Assembled Monolayer for Electroanalytical Application

The electrochemical functionalization of a Au electrode with a redox-active monolayer and the electroanalytical applications of the functionalized electrode are described. Reaction of the electrochemically derived o-quinone on the self-assembled monolayer (SAM) of 6-mercaptopurine (MPU) on a Au electrode gives a redox-active 4-(6-mercapto-purin-9-yl)benzene-1,2-diol (MPBD) self-assembly under optimized conditions. Electrochemical quartz crystal microbalance technique has been employed to follow the functionalization of the electrode in real time. Electrochemically derived o-quinone reacts at the N(9) position of the self-assembled MPU in neutral pH. Raman spectral measurement confirms the reaction of o-quinone on MPU self-assembly. MPBD shows a well-defined reversible redox response, characteristic of a surface-confined redox mediator at 0.21 V in neutral pH. The anodic peak potential (Epa) of MPBD shifts by −60 mV while changing the solution pH by 1 unit, indicating that the redox reaction involves two electrons and two protons. The surface coverage (Γ) of MPBD was 7.2 ± 0.3 × 10-12 mol/cm2. The apparent heterogeneous rate constant (ksapp) for MPBD was 268 ± 6 s-1. MPBD efficiently mediates the oxidation of nicotinamide adenine dinucleotide (NADH) and ascorbate (AA). A large decrease in the overpotential and significant increase in the peak current with respect to the unmodified electrode has been observed. Surface-confined MPBD has been successfully used for the amperometric sensing of NADH and AA in neutral pH at the nanomolar level.

Hadwiger Number and the Cartesian Product of Graphs

The Hadwiger number eta(G) of a graph G is the largest integer n for which the complete graph K-n on n vertices is a minor of G. Hadwiger conjectured that for every graph G, eta(G) >= chi(G), where chi(G) is the chromatic number of G. In this paper, we study the Hadwiger number of the Cartesian product G square H of graphs. As the main result of this paper, we prove that eta(G(1) square G(2)) >= h root 1 (1 - o(1)) for any two graphs G(1) and G(2) with eta(G(1)) = h and eta(G(2)) = l. We show that the above lower bound is asymptotically best possible when h >= l. This asymptotically settles a question of Z. Miller (1978). As consequences of our main result, we show the following: 1. Let G be a connected graph. Let G = G(1) square G(2) square ... square G(k) be the ( unique) prime factorization of G. Then G satisfies Hadwiger's conjecture if k >= 2 log log chi(G) + c', where c' is a constant. This improves the 2 log chi(G) + 3 bound in [2] 2. Let G(1) and G(2) be two graphs such that chi(G1) >= chi(G2) >= clog(1.5)(chi(G(1))), where c is a constant. Then G1 square G2 satisfies Hadwiger's conjecture. 3. Hadwiger's conjecture is true for G(d) (Cartesian product of G taken d times) for every graph G and every d >= 2. This settles a question by Chandran and Sivadasan [2]. ( They had shown that the Hadiwger's conjecture is true for G(d) if d >= 3).

Microscopic Frictional Response of Sodium Oleate Self-Assembled on Steel

The article peruses the frictional response of an important metal working lubricant additive, sodium oleate. Frictional force microscopy is used to track the response of molecules self-assembled on a steel substrate of 3–4 nm roughness at 0% relative humidity. The friction-normal load characteristic emerges as bell-shaped, where the peak friction and normal load at peak friction are both sensitive to substrate roughness. The frictional response at loads lower than that associated with the peak friction is path reversible while at higher loads the loading and unloading paths are different. We suggest that a new low-friction interface material is created when the normal loads are high.

On a Special Co-cycle Basis of Graphs

In this paper we consider the problems of computing a minimum co-cycle basis and a minimum weakly fundamental co-cycle basis of a directed graph G. A co-cycle in G corresponds to a vertex partition (S,V ∖ S) and a { − 1,0,1} edge incidence vector is associated with each co-cycle. The vector space over ℚ generated by these vectors is the co-cycle space of G. Alternately, the co-cycle space is the orthogonal complement of the cycle space of G. The minimum co-cycle basis problem asks for a set of co-cycles that span the co-cycle space of G and whose sum of weights is minimum. Weakly fundamental co-cycle bases are a special class of co-cycle bases, these form a natural superclass of strictly fundamental co-cycle bases and it is known that computing a minimum weight strictly fundamental co-cycle basis is NP-hard. We show that the co-cycle basis corresponding to the cuts of a Gomory-Hu tree of the underlying undirected graph of G is a minimum co-cycle basis of G and it is also weakly fundamental.

New approximation algorithms for minimum cycle bases of graphs

We consider the problem of computing an approximate minimum cycle basis of an undirected edge-weighted graph G with m edges and n vertices; the extension to directed graphs is also discussed. In this problem, a {0,1} incidence vector is associated with each cycle and the vector space over F-2 generated by these vectors is the cycle space of G. A set of cycles is called a cycle basis of G if it forms a basis for its cycle space. A cycle basis where the sum of the weights of the cycles is minimum is called a minimum cycle basis of G. Cycle bases of low weight are useful in a number of contexts, e.g. the analysis of electrical networks, structural engineering, chemistry, and surface reconstruction. We present two new algorithms to compute an approximate minimum cycle basis. For any integer k >= 1, we give (2k - 1)-approximation algorithms with expected running time 0(kmn(1+2/k) + mn((1+1/k)(omega-1))) and deterministic running time 0(n(3+2/k)), respectively. Here omega is the best exponent of matrix multiplication. It is presently known that omega < 2.376. Both algorithms are o(m(omega)) for dense graphs. This is the first time that any algorithm which computes sparse cycle bases with a guarantee drops below the Theta(m(omega)) bound. We also present a 2-approximation algorithm with O(m(omega) root n log n) expected running time, a linear time 2-approximation algorithm for planar graphs and an O(n(3)) time 2.42-approximation algorithm for the complete Euclidean graph in the plane.

Self-Assembly of a Nanoscopic Prism via a New Organometallic Pt3 Acceptor and Its Fluorescent Detection of Nitroaromatics

A nanoscale-sized cage with a trigonal prismatic shape is prepared by coordination-driven self-assembly of a predesigned organometallic Pt-3 acceptor with an organic clip-type ligand. This trigonal prism is fluorescent and undergoes efficient fluorescence quenching by nitroaromatics, which are the chemical signatures of many explosives.

Self-interrupted regenerative metal cutting in turning

A new approach is used to study the global dynamics of regenerative metal cutting in turning. The cut surface is modeled using a partial differential equation (PDE) coupled, via boundary conditions, to an ordinary differential equation (ODE) modeling the dynamics of the cutting tool. This approach automatically incorporates the multiple-regenerative effects accompanying self-interrupted cutting. Taylor's 3/4 power law model for the cutting force is adopted. Lower dimensional ODE approximations are obtained for the combined tool–workpiece model using Galerkin projections, and a bifurcation diagram computed. The unstable solution branch off the subcritical Hopf bifurcation meets the stable branch involving self-interrupted dynamics in a turning point bifurcation. The tool displacement at that turning point is estimated, which helps identify cutting parameter ranges where loss of stability leads to much larger self-interrupted motions than in some other ranges. Numerical bounds are also obtained on the parameter values which guarantee global stability of steady-state cutting, i.e., parameter values for which there exist neither unstable periodic motions nor self-interrupted motions about the stable equilibrium.

Self-assembly of a nanoscopic platinum(II) double square cage

Self-assembly of a rigid tripyridyl linker with a bidentate 90 degrees Pt(II) acceptor yielded a somewhat unusual double square cage, representing the first example of Pt(II) cage of such shape. Multinuclear NMR as well as single-crystal structure analysis characterized the cage.

Self-acylation properties of type II fatty acid biosynthesis acyl carrier protein

Acyl carrier protein (ACIP) plays a central role in many metabolic processes inside the cell, and almost 4% of the total enzymes inside the cell require it as a cofactor. Here, we report self-acylation properties in ACPs from Plasmodium falciparum and Brassica napus that are essential components of type II fatty acid biosynthesis (FAS II), disproving the existing notion that this phenomenon is restricted only to ACPs involved in polyketide biosynthesis. We also provide strong evidence to suggest that catalytic self-acylation is intrinsic to the individual ACP. Mutational analysis of these ACPs revealed the key residue(s) involved in this phenomenon. We also demonstrate that these FAS 11 ACPs exhibit a high degree of selectivity for self-acylation employing only dicarboxylic acids as substrates. A plausible mechanism for the self-acylation reaction is also proposed.

Self-assembly of a nanoscopic platinum(II) double square cage

Self-assembly of a rigid tripyridyl linker with a bidentate 90 degrees Pt(II) acceptor yielded a somewhat unusual double square cage, representing the first example of Pt(II) cage of such shape. Multinuclear NMR as well as single-crystal structure analysis characterized the cage.

Multilayer single-component thin films and microcapsules via covalent bonded layer-by-layer self-assembly

Fabrication of single-component multilayer thin films still remains a challenging task via the layer-by-layer (LbL) approach. In this communication, we report the self-assembly of single-component multilayer thin films on flat and colloidal substrates through glutaraldehyde mediated covalent bonding.

Self-interrupted regenerative turning

A preliminary study of self-interrupted regenerative turning is performed in this paper. To facilitate the analysis, a new approach is proposed to model the regenerative effect in metal cutting. This model automatically incorporates the multiple-regenerative effects accompanying self-interrupted cutting. Some lower dimensional ODE approximations are obtained for this model using Galerkin projections. Using these ODE approximations, a bifurcation diagram of the regenerative turning process is obtained. It is found that the unstable branch resulting from the subcritical Hopf bifurcation meets the stable branch resulting from the self-interrupted dynamics in a turning point bifurcation. Using a rough analytical estimate of the turning point tool displacement, we can identify regions in the cutting parameter space where loss of stability leads to much greater amplitude self-interrupted motions than in some other regions.

A Dynamic Migration Model for Self-adaptive Genetic Algorithms

In this paper, we propose a self Adaptive Migration Model for Genetic Algorithms, where parameters of population size, the number of points of crossover and mutation rate for each population are fixed adaptively. Further, the migration of individuals between populations is decided dynamically. This paper gives a mathematical schema analysis of the method stating and showing that the algorithm exploits previously discovered knowledge for a more focused and concentrated search of heuristically high yielding regions while simultaneously performing a highly explorative search on the other regions of the search space. The effective performance of the algorithm is then shown using standard testbed functions, when compared with Island model GA(IGA) and Simple GA(SGA).