An upper bound for Cubicity in terms of Boxicity

An axis-parallel b-dimensional box is a Cartesian product R-1 x R-2 x ... x R-b where each R-i (for 1 <= i <= b) is a closed interval of the form [a(i), b(i)] on the real line. The boxicity of any graph G, box(G) is the minimum positive integer b such that G can be represented as the intersection graph of axis-parallel b-dimensional boxes. A b-dimensional cube is a Cartesian product R-1 x R-2 x ... x R-b, where each R-i (for 1 <= i <= b) is a closed interval of the form [a(i), a(i) + 1] on the real line. When the boxes are restricted to be axis-parallel cubes in b-dimension, the minimum dimension b required to represent the graph is called the cubicity of the graph (denoted by cub(G)). In this paper we prove that cub(G) <= inverted right perpendicularlog(2) ninverted left perpendicular box(G), where n is the number of vertices in the graph. We also show that this upper bound is tight.Some immediate consequences of the above result are listed below: 1. Planar graphs have cubicity at most 3inverted right perpendicularlog(2) ninvereted left perpendicular.2. Outer planar graphs have cubicity at most 2inverted right perpendicularlog(2) ninverted left perpendicular.3. Any graph of treewidth tw has cubicity at most (tw + 2) inverted right perpendicularlog(2) ninverted left perpendicular. Thus, chordal graphs have cubicity at most (omega + 1) inverted right erpendicularlog(2) ninverted left perpendicular and circular arc graphs have cubicity at most (2 omega + 1)inverted right perpendicularlog(2) ninverted left perpendicular, where omega is the clique number.

Arsenic trioxide promotes mitochondrial DNA mutation and cell apoptosis in primary APL cells and NB4 cell line

This study aimed to investigate the effects of arsenic trioxide (As2O3) on the mitochondrial DNA (mtDNA) of acute promyelocytic leukemia (APL) cells. The NB4 cell line was treated with 2.0 μmol/L As2O3in vitro, and the primary APL cells were treated with 2.0 μmol/L As2O3in vitro and 0.16 mg kg-1 d-1 As2O3in vivo. The mitochondrial DNA of all the cells above was amplified by PCR, directly sequenced and analyzed by Sequence Navigatore and Factura software. The apoptosis rates were assayed by flow cytometry. Mitochondrial DNA mutation in the D-loop region was found in NB4 and APL cells before As2O3 use, but the mutation spots were remarkably increased after As2O3 treatment, which was positively correlated to the rates of cellular apoptosis, the correlation coefficient: rNB4-As2O3=0.973818, and rAPL-As2O3=0.934703. The mutation types include transition, transversion, codon insertion or deletion, and the mutation spots in all samples were not constant and regular. It is revealed that As2O3 aggravates mtDNA mutation in the D-loop region of acute promyelocytic leukemia cells both in vitro and in vivo. Mitochondrial DNA might be one of the targets of As2O3 in APL treatment.

Characterisation of k-Variegated Graphs, k greater-than-or-equal-to 3

A graph is said to be k-variegated if its vertex set can be partitioned into k equal parts such that each vertex is adjacent to exactly one vertex from every other part not containing it. Bednarek and Sanders [1] posed the problem of characterizing k-variegated graphs. V.N. Bhat-Nayak, S.A. Choudum and R.N. Naik [2] gave the characterization of 2-variegated graphs. In this paper we characterize k-variegated graphs for k greater-or-equal, slanted 3.

Unsteady Attachment Line Flow On A Flat-Plate With Attached Cylinder

The unsteady laminar incompressible boundary-layer attachment-line flow on a flat plate with attached cylinder with heat and mass transfer has been studied when the free stream velocity, mass transfer and surface wall temperature vary arbitrarily with time. The governing partial differential equations with three independent variables have been solved numerically using an implicit finite-difference scheme. The heat transfer was found to be strongly dependent on the Prandtl number, variation of wall temperature with time and dissipation parameter (for large times). However, the free stream velocity distribution and mass transfer affect both the heat transfer and skin friction.

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.

The Broad-Line Type Ic Supernoava SN 2007ru: Adding To The Diversity Of Type Ic Supernovae

Photometric and spectral evolution of the Type Ic supernova SN 2007ru until around 210 days after maximum are presented. The spectra show broad spectral features due to very high expansion velocity, normally seen in hypernovae. The photospheric velocity is higher than other normal Type Ic supernovae (SNe Ic). It is lower than SN 1998bw at similar to 8 days after the explosion, but is comparable at later epochs. The light curve (LC) evolution of SN 2007ru indicates a fast rise time of 8 +/- 3 days to B-band maximum and postmaximum decline more rapid than other broad-line SNe Ic. With an absolute V magnitude of -19.06, SN 2007ru is comparable in brightness with SN 1998bw and lies at the brighter end of the observed SNe Ic. The ejected mass of Ni-56 is estimated to be similar to 0.4 M-circle dot. The fast rise and decline of the LC and the high expansion velocity suggest that SN 2007ru is an explosion with a high kinetic energy/ejecta mass ratio (E-K/M-ej). This adds to the diversity of SNe Ic. Although the early phase spectra are most similar to those of broad-line SN 2003jd, the [O I] line profile in the nebular spectrum of SN 2007ru shows the singly peaked profile, in contrast to the doubly peaked profile in SN 2003jd. The singly peaked profile, together with the high luminosity and the high expansion velocity, may suggest that SN 2007ru could be an aspherical explosion viewed from the polar direction. Estimated oxygen abundance 12 + log(O/H) of similar to 8.8 indicates that SN 2007ru occurred in a region with nearly solar metallicity.

Representation of functional dependencies in relational databases using linear graphs

Functional dependencies in relational databases are investigated. Eight binary relations, viz., (1) dependency relation, (2) equipotence relation, (3) dissidence relation, (4) completion relation, and dual relations of each of them are described. Any one of these eight relations can be used to represent the functional dependencies in a database. Results from linear graph theory are found helpful in obtaining these representations. The dependency relation directly gives the functional dependencies. The equipotence relation specifies the dependencies in terms of attribute sets which functionally determine each other. The dissidence relation specifies the dependencies in terms of saturated sets in a very indirect way. Completion relation represents the functional dependencies as a function, the range of which turns out to be a lattice. Depletion relation which is the dual of the completion relation can also represent functional dependencies and similarly can the duals of dependency, equipotence, and dissidence relations. The class of depleted sets, which is the dual of saturated sets, is defined and used in the study of depletion relations.

An on-line algorithm for the location of cross point faults in programmable logic arrays

An on-line algorithm is developed for the location of single cross point faults in a PLA (FPLA). The main feature of the algorithm is the determination of a fault set corresponding to the response obtained for a failed test. For the apparently small number of faults in this set, all other tests are generated and a fault table is formed. Subsequently, an adaptive procedure is used to diagnose the fault. Functional equivalence test is carried out to determine the actual fault class if the adaptive testing results in a set of faults with identical tests. The large amount of computation time and storage required in the determination, a priori, of all the fault equivalence classes or in the construction of a fault dictionary are not needed here. A brief study of functional equivalence among the cross point faults is also made.

Efficient algorithms for computing Reeb graphs

The Reeb graph tracks topology changes in level sets of a scalar function and finds applications in scientific visualization and geometric modeling. We describe an algorithm that constructs the Reeb graph of a Morse function defined on a 3-manifold. Our algorithm maintains connected components of the two dimensional levels sets as a dynamic graph and constructs the Reeb graph in O(nlogn+nlogg(loglogg)3) time, where n is the number of triangles in the tetrahedral mesh representing the 3-manifold and g is the maximum genus over all level sets of the function. We extend this algorithm to construct Reeb graphs of d-manifolds in O(nlogn(loglogn)3) time, where n is the number of triangles in the simplicial complex that represents the d-manifold. Our result is a significant improvement over the previously known O(n2) algorithm. Finally, we present experimental results of our implementation and demonstrate that our algorithm for 3-manifolds performs efficiently in practice.

Forms of relativistic dynamics with World Line Condition and separability

he Dirac generator formalism for relativistic Hamiltonian dynamics is reviewed along with its extension to constraint formalism. In these theories evolution is with respect to a dynamically defined parameter, and thus time evolution involves an eleventh generator. These formulations evade the No-Interaction Theorem. But the incorporation of separability reopens the question, and together with the World Line Condition leads to a second no-interaction theorem for systems of three or more particles. Proofs are omitted, but the results of recent research in this area is highlighted.

Investigation of movement and factors influencing post-release survival of line-caught coral reef fish using recreational tag-recapture data

Six species of line-caught coral reef fish (Plectropomus spp., Lethrinus miniatus, Lethrinus laticaudis, Lutjanus sebae, Lutjanus malabaricus and Lutjanus erythropterus) were tagged by members of the Australian National Sportsfishing Association (ANSA) in Queensland between 1986 and 2003. Of the 14,757 fish tagged, 1607 were recaptured and we analysed these data to describe movement and determine factors likely to impact release survival. All species were classified as residents since over 80% of recaptures for each species occurred within 1 km of the release site. Few individuals (range 0.8-5%) were recaptured more than 20 km from their release point. L. sebae had a higher recapture rate (19.9%) than the other species studied (range 2.1-11.7%). Venting swimbladder gases, regardless of whether or not fish appeared to be suffering from barotrauma, significantly enhanced (P < 0.05) the survival of L. sebae and L. malabaricus but had no significant effect (P > 0.05) on L. erythropterus. The condition of fish on release, subjectively assessed by anglers, was only a significant effect on recapture rate for L. sebae where fish in "fair" condition had less than half the recapture rate of those assessed as in "excellent" or "good" condition. The recapture rate of L. sebae and L. laticaudis was significantly (P < 0.05) affected by depth with recapture rate declining in depths exceeding 30 m. Overall, the results showed that depth of capture, release condition and treatment for barotrauma influenced recapture rate for some species but these effects were not consistent across all species studied. Recommendations were made to the ANSA tagging clubs to record additional information such as injury, hooking location and hook type to enable a more comprehensive future assessment of the factors influencing release survival.

Line narrowing of electromagnetically induced transparency in Rb with a longitudinal magnetic field

Electromagnetically induced transparency (EIT) experiments in Lambda-type systems benefit from the use of hot vapor where the thermal averaging results in reducing the width of the EIT resonance well below the natural linewidth. Here, we demonstrate a technique for further reducing the EIT width in room-temperature vapor by the application of a small longitudinal magnetic field. The Zeeman shift of the energy levels results in the formation of several shifted subsystems; the net effect is to create multiple EIT dips each of which is significantly narrower than the original resonance. We observe a reduction by a factor of 3 in the D2 line of 87Rb with a field of 3.2 G.

Spatial and temporal variation and effects of changes in management in discard rates from the commercial reef line fishery of the Great Barrier Reef, Australia

Discarding in commercially exploited fisheries has received considerable attention in the last decade, though only more recently in Australia. The Reef Line fishery (RLF) of the Great Barrier Reef (GBR) in Australia is a large-scale multi-sector, multi-species, highly regulated hook and line fishery with the potential for high levels of discarding. We used a range of data sources to estimate discard rates and discard quantities for the two main target groups of the RLF, the coral trout, Plectropomus spp, and the red throat emperor, Lethrinus miniatus, and investigated possible effects on discarding of recent changes in management of the fishery. Fleet-wide estimates of total annual quantities discarded from 1989 to 2003 were 292-622 t and 33-95 t for coral trout and red throat emperor, respectively. Hypothetical scenarios of high-grading after the introduction of a total allowable commercial catch for coral trout resulted in increases in discard quantities up to 3895 t, while no high-grading still meant 421 t were discarded. Increasing the minimum size limit of red throat emperor from 35 to 38 cm also increased discards to an estimated 103 t. We provide spatially and temporally explicit estimates of discarding for the two most important species in the GBR RLF of Australia to demonstrate the importance of accounting for regional variation in quantification of discarding. Effects of management changes on discarding are also highlighted. This study provides a template for exploring discarding levels for other species in the RLF and elsewhere.

The influence of animal mobility on the assumption of uniform distances in aerial line-transect surveys

Line-transect distance sampling is a widely used method for estimating animal density from aerial surveys. Analysis of line-transect distance data usually relies on a requirement that the statistical distribution of distances of animal groups from the transect line is uniform. We show that this requirement is satisfied by the survey design if all other assumptions of distance sampling hold, but it can be violated by consistent survey problems such as responsive movement of the animals towards or away from the observer. We hypothesise that problems with the uniform requirement are unlikely to be encountered for immobile taxa, but might become substantial for species of high mobility. We test evidence for non-uniformity using double-observer distance data from two aerial surveys of five species with a spectrum of mobility capabilities and tendencies. No clear evidence against uniformity was found for crabeater seals or emperor penguins on the pack-ice in East Antarctica, while minor non-uniformity consistent with responsive movement up to 30 m was found for Adelie penguins. Strong evidence of either non-uniformity or a failure of the capture-recapture validating method was found for eastern grey kangaroos and red kangaroos in Queensland.