Geometric representations of graphs in low dimension

We give an efficient randomized algorithm to construct a box representation of any graph G on n vertices in $1.5 (\Delta + 2) \ln n$ dimensions, where $\Delta$ is the maximum degree of G. We also show that $\boxi(G) \le (\Delta + 2) \ln n$ for any graph G. Our bound is tight up to a factor of $\ln n$. We also show that our randomized algorithm can be derandomized to get a polynomial time deterministic algorithm. Though our general upper bound is in terms of maximum degree $\Delta$, we show that for almost all graphs on n vertices, its boxicity is upper bound by $c\cdot(d_{av} + 1) \ln n$ where d_{av} is the average degree and c is a small constant. Also, we show that for any graph G, $\boxi(G) \le \sqrt{8 n d_{av} \ln n}$, which is tight up to a factor of $b \sqrt{\ln n}$ for a constant b.

Output-Sensitive Construction of Reeb Graphs

The Reeb graph of a scalar function represents the evolution of the topology of its level sets. This paper describes a near-optimal output-sensitive algorithm for computing the Reeb graph of scalar functions defined over manifolds or non-manifolds in any dimension. Key to the simplicity and efficiency of the algorithm is an alternate definition of the Reeb graph that considers equivalence classes of level sets instead of individual level sets. The algorithm works in two steps. The first step locates all critical points of the function in the domain. Critical points correspond to nodes in the Reeb graph. Arcs connecting the nodes are computed in the second step by a simple search procedure that works on a small subset of the domain that corresponds to a pair of critical points. The paper also describes a scheme for controlled simplification of the Reeb graph and two different graph layout schemes that help in the effective presentation of Reeb graphs for visual analysis of scalar fields. Finally, the Reeb graph is employed in four different applications-surface segmentation, spatially-aware transfer function design, visualization of interval volumes, and interactive exploration of time-varying data.

Acyclic edge coloring of 2-degenerate graphs

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). A graph is called 2-degenerate if any of its induced subgraph has a vertex of degree at most 2. The class of 2-degenerate graphs properly contains seriesparallel graphs, outerplanar graphs, non - regular subcubic graphs, planar graphs of girth at least 6 and circle graphs of girth at least 5 as subclasses. It was conjectured by Alon, Sudakov and Zaks (and much earlier by Fiamcik) that a'(G)<=Delta + 2, where Delta = Delta(G) denotes the maximum degree of the graph. We prove the conjecture for 2-degenerate graphs. In fact we prove a stronger bound: we prove that if G is a 2-degenerate graph with maximum degree ?, then a'(G)<=Delta + 1. (C) 2010 Wiley Periodicals, Inc. J Graph Theory 68:1-27, 2011

IN-VITRO CYTOTOXICITY AND CELL CYCLE ANALYSIS OF TWO NOVEL BIS-1, 2, 4-TRIAZOLE DERIVATIVES: 1,4-BIS[5-(5-MERCAPTO-1,3,4-OXADIAZOL-2-yl-METHYL)-THIO-4-(p-TOLYL)-1, 2,4-TRIAZOL-3-yl]-BUTANE (MNP-14) AND 1,4-BIS[5-(CARBETHOXY-METHYL)-THIO-4-(p-ETHOXY PHENYL)-1,2,4-TRIAZOL-3-yl]-BUTANE (MNP-16)

In the present study, we have tested the cytotoxic and DNA damage activity of two novel bis-1,2,4 triazole derivatives, namely 1,4-bis[5-(5-mercapto-1,3,4-oxadiazol-2-yl-methyl)-thio4-(p-tolyl)-1,2 ,4-triazol-3-yl]-butane (MNP-14) and 1,4-bis[5-(carbethoxy-methyl)-thio-4-(p-ethoxy phenyl) -1,2,4-triazol-3-yl]-butane (MNP-16). The effect of these molecules on cellular apoptosis was also determined. The in-vitro cytotoxicity was evaluated by a 3-(4,5-dimethylthiazol-2-yl)-2,5-diphenyl tetrazolium bromide (MTT) assay as well as Trypan blue dye exclusion methods against human acute lymphoblastic leukemia (MOLT4) and lung cancer cells (A549). Our results showed that MNP-16 induced significant cytotoxicity (IC50 of 3-5 mu M) compared with MNP-14. The cytotoxicity induced by MNP-16 was time and concentration dependent. The cell cycle analysis by flow cytometry (fluorescence-activated cell sorting [FACS]) revealed that though there was a significant increase in the apoptotic population (sub-G1 phase) with an increased concentration of MNP-14 and 16, there was no cell cycle arrest. Further, the comet assay results indicated considerable DNA

Percolation and connectivity in AB random geometric graphs

Given two independent Poisson point processes Phi((1)), Phi((2)) in R-d, the AB Poisson Boolean model is the graph with the points of Phi((1)) as vertices and with edges between any pair of points for which the intersection of balls of radius 2r centered at these points contains at least one point of Phi((2)). This is a generalization of the AB percolation model on discrete lattices. We show the existence of percolation for all d >= 2 and derive bounds fora critical intensity. We also provide a characterization for this critical intensity when d = 2. To study the connectivity problem, we consider independent Poisson point processes of intensities n and tau n in the unit cube. The AB random geometric graph is defined as above but with balls of radius r. We derive a weak law result for the largest nearest-neighbor distance and almost-sure asymptotic bounds for the connectivity threshold.

Tight co-degree condition for perfect matchings in 4-graphs

We will give a tight minimum co-degree condition for a 4-uniform hypergraph to contain a perfect matching.

Maximum weight independent sets in hole- and dart-free graphs

The Maximum Weight Independent Set (MWIS) problem on graphs with vertex weights asks for a set of pairwise nonadjacent vertices of maximum total weight. The complexity of the MWIS problem for hole-free graphs is unknown. In this paper, we first prove that the MWIS problem for (hole, dart, gem)-free graphs can be solved in O(n(3))-time. By using this result, we prove that the MWIS problem for (hole, dart)-free graphs can be solved in O(n(4))-time. Though the MWIS problem for (hole, dart, gem)-free graphs is used as a subroutine, we also give the best known time bound for the solvability of the MWIS problem in (hole, dart, gem)-free graphs. (C) 2012 Elsevier B.V. All rights reserved.

Albedo enhancement over land to counteract global warming: impacts on hydrological cycle

A recent modelling study has shown that precipitation and runoff over land would increase when the reflectivity of marine clouds is increased to counter global warming. This implies that large scale albedo enhancement over land could lead to a decrease in runoff over land. In this study, we perform simulations using NCAR CAM3.1 that have implications for Solar Radiation Management geoengineering schemes that increase the albedo over land. We find that an increase in reflectivity over land that mitigates the global mean warming from a doubling of CO2 leads to a large residual warming in the southern hemisphere and cooling in the northern hemisphere since most of the land is located in northern hemisphere. Precipitation and runoff over land decrease by 13.4 and 22.3%, respectively, because of a large residual sinking motion over land triggered by albedo enhancement over land. Soil water content also declines when albedo over land is enhanced. The simulated magnitude of hydrological changes over land are much larger when compared to changes over oceans in the recent marine cloud albedo enhancement study since the radiative forcing over land needed (-8.2 W m(-2)) to counter global mean radiative forcing from a doubling of CO2 (3.3 W m(-2)) is approximately twice the forcing needed over the oceans (-4.2 W m(-2)). Our results imply that albedo enhancement over oceans produce climates closer to the unperturbed climate state than do albedo changes on land when the consequences on land hydrology are considered. Our study also has important implications for any intentional or unintentional large scale changes in land surface albedo such as deforestation/afforestation/reforestation, air pollution, and desert and urban albedo modification.

Algorithmic aspects of k-tuple total domination in graphs

For a fixed positive integer k, a k-tuple total dominating set of a graph G = (V. E) is a subset T D-k of V such that every vertex in V is adjacent to at least k vertices of T Dk. In minimum k-tuple total dominating set problem (MIN k-TUPLE TOTAL DOM SET), it is required to find a k-tuple total dominating set of minimum cardinality and DECIDE MIN k-TUPLE TOTAL DOM SET is the decision version of MIN k-TUPLE TOTAL DOM SET problem. In this paper, we show that DECIDE MIN k-TUPLE TOTAL DOM SET is NP-complete for split graphs, doubly chordal graphs and bipartite graphs. For chordal bipartite graphs, we show that MIN k-TUPLE TOTAL DOM SET can be solved in polynomial time. We also propose some hardness results and approximation algorithms for MIN k-TUPLE TOTAL DOM SET problem. (c) 2012 Elsevier B.V. All rights reserved.