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.

Electrical, structural and magnetic properties of polyaniline/pTSA-TiO2 nanocomposites

Polyaniline (PANI)/para-toluene sulfonic acid (pTSA) and PANI/pTSA-TiO2 composites were prepared using chemical method and characterized by infrared spectroscopy (IR), powder X-ray diffraction (XRD), scanning electron microscopy (SEM). The electrical conductivity and magnetic properties were also measured. In corroboration with XRD, the micrographs of SEM indicated the homogeneous dispersion of TiO nanoparticles in bulk PANI/pTSA matrix. Conductivity of the PANI/pTSA-TiO2 was higher than the PAN[/pTSA, and the maximum conductivity obtained was 9.48 (S/cm) at 5 wt% of TiO2. Using SQUID magnetometer, it was found that PANI/pTSA was either paramagnetic or weakly ferromagnetic from 300 K down to 5 K with H-C approximate to 30 Oe and M-r approximate to 0.015 emu/g. On the other hand,PANI/pTSA-TiO2 was diamagnetic from 300 K down to about 50 K and below which it was weakly ferromagnetic. Furthermore, a nearly temperature-independent magnetization was observed in both the cases down to 50 K and below which the magnetization increased rapidly (a Curie like susceptibility was observed). The Pauli susceptibility (chi(pauli)) was calculated to be about 4.8 X 10(-5) and 1.6 x 10(-5)emug(-1) Oe(-1) K for PANI/pTSA and PANI/pTSA-TiO2, respectively.