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.

Kinematics of pantograph masts

This paper deals with the kinematics of pantograph masts. Pantograph masts have widespread use in space application as deployable structures. They are over constrained mechanisms with degree-of-freedom, evaluated by the Grübler–Kutzback formula, as less than one. In this paper, a numerical algorithm is used to evaluate the degree-of-freedom of pantograph masts by obtaining the null space of a constraint Jacobian matrix. In the process redundant joints in the masts are obtained. A method based on symbolic computation, to obtain the closed-form kinematics equations of triangular and box shaped pantograph masts, is presented. In the process, the various configurations such masts can attain during deployment, are obtained. The closed-form solution also helps in identifying the redundant joints in the masts. The symbolic computations involving the Jacobian matrix also leads to a method to evaluate the global degree-of-freedom for these masts.

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

Nonsimilar boundary layers for non-Darcy mixed convection flow about a horizontal surface in a saturated porous medium

The nonsimilar non-Darcy mixed convection flow about a heated horizontal surface in a saturated porous medium has been studied when the surface temperature is a power function of distance (Tw = T∞ ± Axλ). The analysis is performed for the cases of parallel and stagnation flows with favourable induced pressure gradient. The partial differential equations governing the flow have been solved numerically using the Keller box method. The heat transfer is enhanced due to the buoyancy parameter and wall temperature, but the non-Darcy parameter reduces it. For non-Darcy flow, the similarity solution exists only for the case of parallel flow.

Evaluation of interfacial frictional resistance

Three distinct mechanisms — sliding, bonding and bearing — for the mobilisation of interfacial friction have been identified. In the light of these mechanisms, the effect of variation in reinforcement parameters, such as extensibility, flexibility and hardness on mobilisation of interfacial friction, and the mechanisms themselves has been examined. The influence of boundary effects of apparatus on the interfacial friction has been discussed and a method of estimating the same in a pull-out box has been proposed.

Non-Darcy mixed convection flow with thermal dispersion on a vertical cylinder in a saturated porous medium

The non-Darcy mixed convection flow on a vertical cylinder embedded in a saturated porous medium has been studied taking into account the effect of thermal dispersion. Both forced flow and buoyancy force dominated cases with constant wall temperature condition have been considered. The governing partial differential equations have been solved numerically using the Keller box method. The results are presented for the buoyancy parameter which cover the entire regime of mixed convection flow ranging from pure forced convection to pure free convection. The effect of thermal dispersion is found to be more pronounced on the heat transfer than on the skin friction and it enhances the heat transfer but reduces the skin friction.

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.

Conjugate MHD flow past a flat plate

A boundary layer solution for the conjugate forced convection flow of an electrically conducting fluid over a semi-infinite flat plate in the presence of a transverse magnetic field is presented. The governing nonsimilar partial differential equations are solved numerically using the Keller box method. Values of the temperature profiles of the plate are obtained for various values of the parameters entering the problem and are given in a table and shown on graphs.

Modeling of a reacting nanofilm on a composite substrate

This article provides a detailed computational analysis of the reaction of dense nanofilms and the heat transfer characteristics on a composite substrate. Although traditional energetic compounds based on organic materials have similar energy per unit weight, non-organic material in nanofilm configuration offers much higher energy density and higher flame speed. The reaction of a multilayer thin film of aluminum and copper oxide has been studied by varying the substrate material and thicknesses. The numerical analysis of the thermal transport of the reacting film deposited on the substrate combined a hybrid approach in which a traditional two-dimensional black box theory was used in conjunction with the sandwich model to estimate the appropriate heat flux on the substrate accounting for the heat loss to the surroundings. A procedure to estimate this heat flux using stoichiometric calculations is provided. This work highlights two important findings. One is that there is very little difference in the temperature profiles between a single substrate of silica and a composite substrate of silicon silica. Secondly, with increase in substrate thickness, the quenching effect is progressively diminished at a given speed. These findings show that the composite substrate is effective and that the average speed and quenching of flames depend on the thickness of the silica substrate, and can be controlled by a careful choice of the substrate configuration. (C) 2011 Elsevier Ltd. All rights reserved.

Nonsimilar mixed convection flow of a non-Newtonian fluid past a vertical wedge

The flow and heat transfer characteristics of a second-order fluid over a vertical wedge with buoyancy forces have been analysed. The coupled nonlinear partial differential equations governing the nonsimilar mixed convection flow have been solved numerically using Keller box method. The effects of the buoyancy parameter, viscoelastic parameter, mass transfer parameter, pressure gradient parameter, Prandtl number and viscous dissipation parameter on the skin friction and heat transfer have been examined in detail. Particular cases of the present results match exactly with those available in the literature.

A checking method for probabilistic seismic-hazard assessment: case studies on three cities

The conventional Cornell's source-based approach of probabilistic seismic-hazard assessment (PSHA) has been employed all around the world, whilst many studies often rely on the use of computer packages such as FRISK (McGuire FRISK-a computer program for seismic risk analysis. Open-File Report 78-1007, United States Geological Survey, Department of Interior, Washington 1978) and SEISRISK III (Bender and Perkins SEISRISK III-a computer program for seismic hazard estimation, Bulletin 1772. United States Geological Survey, Department of Interior, Washington 1987). A ``black-box'' syndrome may be resulted if the user of the software does not have another simple and robust PSHA method that can be used to make comparisons. An alternative method for PSHA, namely direct amplitude-based (DAB) approach, has been developed as a heuristic and efficient method enabling users to undertake their own sanity checks on outputs from computer packages. This paper experiments the application of the DAB approach for three cities in China, Iran, and India, respectively, and compares with documented results computed by the source-based approach. Several insights regarding the procedure of conducting PSHA have also been obtained, which could be useful for future seismic-hazard studies.

Characterization of RNA polymerase III transcription factor TFIIIC from the mulberry silkworm, Bombyx mori

Fractionation of nuclear extracts from posterior silk glands of mulberry silkworm Bombyx mori. resolved the transcription factor TFIIIC into two components (designated here as TFIIIC and TFIIIC1) as in HeLa cell nuclear extracts. The reconstituted transcription of tRNA genes required the presence of both components. The affinity purified TFIIIC is a heteromeric complex comprising of five subunits ranging from 44 to 240 kDa. Of these, the 51-kDa subunit could be specifically crosslinked to the B box of tRNA(1)(Gly). Purified swTFIIIC binds to the B box sequences with an affinity in the same range as of yTFIIIC or hTFIIIC2. Although an histone acetyl transferase (HAT) activity was associated with the TFIIIC fractions during the initial stages of purification. the HAT activity, unlike the human TFIIIC preparations, was separated at the final DNA affinity step. The tRNA transcription from DNA template was independent of HAT activity but the repressed transcription from chromatin template could be partially restored by external supplementation of the dissociated HAT activity. This is the first report on the purification and characterization of TFIIIC from insect systems.

Thin Films of Titanium Dioxide Prepared by Chemical Routes using Novel Precursors

Novel, volatile, stable, oxo-β-ketoesterate complexes of titanium, whose synthesis requires only an inert atmosphere, as opposed to a glove box, have been developed. Using one of the complexes as the precursor, thin films of TiO2 have been deposited on glass substrates by metalorganic chemical vapor deposition (MOCVD) at temperatures ranging from 400°C to 525°C and characterized by scanning electron microscopy, transmission electron microscopy, and atomic force microscopy. All the films grown in this temperature range are very smooth; those grown above 480°C consist of nearly monodisperse, nanocrystals of the anatase phase. Optical studies show the bandgaps in the range 3.4–3.7 eV for films grown at different temperatures. Thin films of anatase TiO2 have also been grown by spin-coating technique using another ketoesterate complex of titanium, demonstrating that the newly developed complexes can be successfully used for thin film growth by various chemical routes.

Transcription factors that mediate epithelial-mesenchymal transition lead to multidrug resistance by upregulating ABC transporters

Development of multidrug resistance (MDR) is a major deterrent in the effective treatment of metastatic cancers by chemotherapy. Even though MDR and cancer invasiveness have been correlated, the molecular basis of this link remains obscure. We show here that treatment with chemotherapeutic drugs increases the expression of several ATP binding cassette transporters (ABC transporters) associated with MDR, as well as epithelial-mesenchymal transition (EMT) markers, selectively in invasive breast cancer cells, but not in immortalized or non-invasive cells. Interestingly, the mere induction of an EMT in immortalized and non-invasive cell lines increased their expression of ABC transporters, migration, invasion, and drug resistance. Conversely, reversal of EMT in invasive cells by downregulating EMT-inducing transcription factors reduced their expression of ABC transporters, invasion, and rendered them more chemosensitive. Mechanistically, we demonstrate that the promoters of ABC transporters carry several binding sites for EMT-inducing transcription factors, and overexpression of Twist, Snail, and FOXC2 increases the promoter activity of ABC transporters. Furthermore, chromatin immunoprecipitation studies revealed that Twist binds directly to the E-box elements of ABC transporters. Thus, our study identifies EMT inducers as novel regulators of ABC transporters, thereby providing molecular insights into the long-standing association between invasiveness and MDR. Targeting EMT transcription factors could hence serve as novel strategies to curb both metastasis and the associated drug resistance. Cell Death and Disease (2011) 2, e179; doi:10.1038/cddis.2011.61; published online 7 July 2011

Identification of a core promoter and a novel isoform of the human TSCI gene transcript and structural comparison with mouse homolog

Tuberous sclerosis complex (TSC) is an autosomal dominant disorder with loci on chromosome 9q34.12 (TSC1) and chromosome 16p13.3 (TSC2). Genes for both loci have been isolated and characterized. The promoters of both genes have not been characterized so far and little is known about the regulation of these genes. This study reports the characterization of the human TSC1 promoter region for the first time. We have identified a novel alternative isoform in the 5' untranslated region (UTR) of the TSC1 gene transcript involving exon 1. Alternative isoforms in the 5' UTR of the mouse Tsc1 gene transcript involving exon I and exon 2 have also been identified. We have identified three upstream open reading frames (uORFs) in the 5' UTR of the TSC1/Tsc1 gene. A comparative study of the 5' UTR of TSC1/Tsc1 gene has revealed that there is a high degree of similarity not only in the sequence but also in the splicing pattern of both human and mouse TSC1 genes. We have used PCR methodology to isolate approximately 1.6 kb genomic DNA 5' to the TSC1 cDNA. This sequence has directed a high level of expression of luciferase activity in both HeLa and HepG2 cells. Successive 5' and 3' deletion analysis has suggested that a -587 bp region, from position +77 to -510 from the transcription start site (TSS), contains the promoter activity. Interestingly, this region contains no consensus TATA box or CAAT box. However, a 521-bp fragment surrounding the TSS exhibits the characteristics of a CpG island which overlaps with the promoter region. The identification of the TSC1 promoter region will help in designing a suitable strategy to identify mutations in this region in patients who do not show any mutations in the coding regions. It will also help to study the regulation of the TSC1 gene and its role in tumorigenesis. (C) 2003 Elsevier B.V. All rights reserved.