Algorithms for Maximum Independent Set in Convex Bipartite Graphs

A bipartite graph G = (V, W, E) is convex if there exists an ordering of the vertices of W such that, for each v. V, the neighbors of v are consecutive in W. We describe both a sequential and a BSP/CGM algorithm to find a maximum independent set in a convex bipartite graph. The sequential algorithm improves over the running time of the previously known algorithm and the BSP/CGM algorithm is a parallel version of the sequential one. The complexity of the algorithms does not depend on |W|.

Packing triangles in low degree graphs and indifference graphs

We consider the problems of finding the maximum number of vertex-disjoint triangles (VTP) and edge-disjoint triangles (ETP) in a simple graph. Both problems are NP-hard. The algorithm with the best approximation ratio known so far for these problems has ratio 3/2 + epsilon, a result that follows from a more general algorithm for set packing obtained by Hurkens and Schrijver [On the size of systems of sets every t of which have an SDR, with an application to the worst-case ratio of heuristics for packing problems, SIAM J. Discrete Math. 2(1) (1989) 68-72]. We present improvements on the approximation ratio for restricted cases of VTP and ETP that are known to be APX-hard: we give an approximation algorithm for VTP on graphs with maximum degree 4 with ratio slightly less than 1.2, and for ETP on graphs with maximum degree 5 with ratio 4/3. We also present an exact linear-time algorithm for VTP on the class of indifference graphs. (C) 2007 Elsevier B.V. All rights reserved.

Sparse partition universal graphs for graphs of bounded degree

In 1983, Chvatal, Trotter and the two senior authors proved that for any Delta there exists a constant B such that, for any n, any 2-colouring of the edges of the complete graph K(N) with N >= Bn vertices yields a monochromatic copy of any graph H that has n vertices and maximum degree Delta. We prove that the complete graph may be replaced by a sparser graph G that has N vertices and O(N(2-1/Delta)log(1/Delta)N) edges, with N = [B`n] for some constant B` that depends only on Delta. Consequently, the so-called size-Ramsey number of any H with n vertices and maximum degree Delta is O(n(2-1/Delta)log(1/Delta)n) Our approach is based on random graphs; in fact, we show that the classical Erdos-Renyi random graph with the numerical parameters above satisfies a stronger partition property with high probability, namely, that any 2-colouring of its edges contains a monochromatic universal graph for the class of graphs on n vertices and maximum degree Delta. The main tool in our proof is the regularity method, adapted to a suitable sparse setting. The novel ingredient developed here is an embedding strategy that allows one to embed bounded degree graphs of linear order in certain pseudorandom graphs. Crucial to our proof is the fact that regularity is typically inherited at a scale that is much finer than the scale at which it is assumed. (C) 2011 Elsevier Inc. All rights reserved.

Geodesics and Almost Geodesic Cycles in Random Regular Graphs

A geodesic in a graph G is a shortest path between two vertices of G. For a specific function e(n) of n, we define an almost geodesic cycle C in G to be a cycle in which for every two vertices u and v in C, the distance d(G)(u, v) is at least d(C)(u, v) - e(n). Let omega(n) be any function tending to infinity with n. We consider a random d-regular graph on n vertices. We show that almost all pairs of vertices belong to an almost geodesic cycle C with e(n)= log(d-1)log(d-1) n+omega(n) and vertical bar C vertical bar =2 log(d-1) n+O(omega(n)). Along the way, we obtain results on near-geodesic paths. We also give the limiting distribution of the number of geodesics between two random vertices in this random graph. (C) 2010 Wiley Periodicals, Inc. J Graph Theory 66: 115-136, 2011

Asymmetric Ramsey Properties of Random Graphs Involving Cliques

Consider the following problem: Forgiven graphs G and F(1),..., F(k), find a coloring of the edges of G with k colors such that G does not contain F; in color i. Rodl and Rucinski studied this problem for the random graph G,,, in the symmetric case when k is fixed and F(1) = ... = F(k) = F. They proved that such a coloring exists asymptotically almost surely (a.a.s.) provided that p <= bn(-beta) for some constants b = b(F,k) and beta = beta(F). This result is essentially best possible because for p >= Bn(-beta), where B = B(F, k) is a large constant, such an edge-coloring does not exist. Kohayakawa and Kreuter conjectured a threshold function n(-beta(F1,..., Fk)) for arbitrary F(1), ..., F(k). In this article we address the case when F(1),..., F(k) are cliques of different sizes and propose an algorithm that a.a.s. finds a valid k-edge-coloring of G(n,p) with p <= bn(-beta) for some constant b = b(F(1),..., F(k)), where beta = beta(F(1),..., F(k)) as conjectured. With a few exceptions, this algorithm also works in the general symmetric case. We also show that there exists a constant B = B(F,,..., Fk) such that for p >= Bn(-beta) the random graph G(n,p) a.a.s. does not have a valid k-edge-coloring provided the so-called KLR-conjecture holds. (C) 2008 Wiley Periodicals, Inc. Random Struct. Alg., 34, 419-453, 2009

The disk-percolation model on graphs

We study a long-range percolation model whose dynamics describe the spreading of an infection on an infinite graph. We obtain a sufficient condition for phase transition and prove all upper bound for the critical parameter of spherically symmetric trees. (C) 2008 Elsevier B.V. All rights reserved.

In vitro evaluation of Cu and Fe bioavailability in cashew nuts by off-line coupled SEC-UV and SIMAAS

In this work Cu and Fe bioavailability in cashew nuts was evaluated using in vitro method. Extractions with simulated gastric and intestinal fluids and dialysis procedures were applied for this purpose. The proteins separation and quantification were performed by size exclusion chromatography (SEC) coupled on-line to ultra-violet (UV) and off-line to simultaneous multielement atomic absorption spectrometry (SIMAAS). The SEC-UV and SIMAAS profiles of the protein fractions obtained by alkaline extraction (NaOH) and precipitation with HCl indicated the presence of high and low molecular weight species in the range between >75 kDa and 9.3 kDa. Almost 83% of Cu and 78% of Fe were extracted during cashew nut digestion and 90% of both elements were dialyzed. With these results it is possible to assume that 75% of Cu and 70% of Fe present in cashew nut could be bioavailable. The SEC-UV and SIMAAS chromatographic profiles obtained after in vitro gastrointestinal digestion reveal that Cu and Fe not dialyzed can be associated to a compound of 9.2 kDa. (C) 2010 Elsevier B.V. All rights reserved.

Overexpression of Nrp/b (nuclear restrict protein in brain) suppresses the malignant phenotype in the C6/ST1 glioma cell line

Upon searching for glucocorticoid-regulated cDNA sequences associated with the transformed to normal phenotypic reversion of C6/ST1 rat glioma cells, we identified Nrp/b (nuclear restrict protein in brain) as a novel rat gene. Here we report on the identification and functional characterization of the complete sequence encoding the rat NRP/B protein. The cloned cDNA presented a 1767 nucleotides open-reading frame encoding a 589 aminoacids residues sequence containing a BTB/POZ (broad complex Tramtrack bric-a-brac/Pox virus and zinc finger) domain in its N-terminal region and kelch motifs in its C-terminal region. Sequence analysis indicates that the rat Nrp/b displays a high level of identity with the equivalent gene orthologs from other organisms. Among rat tissues, Nrp/b expression is more pronounced in brain tissue. We show that overexpression of the Nrp/b cDNA in C6/ST1 cells suppresses anchorage independence in vitro and tumorigenicity in vivo, altering their malignant nature towards a more benign phenotype. Therefore, Nrp/b may be postulated as a novel tumor suppressorgene, with possible relevance for glioblastoma therapy. (C) 2009 Elsevier Ltd. All rights reserved.

On-line mass spectrometry of the electro-oxidation of methanol in acidic media on tungsten carbide

The electro-oxidation of methanol at supported tungsten carbide (WC) nanoparticles in sulfuric acid solution was studied using cyclic voltammetry, potentiostatic measurements, and differential electrochemical mass spectroscopy (DEMS). The catalyst was prepared by a sonochemical method and characterized by X-ray diffraction. Over the WC catalyst, the oxidation of methanol (1 M in a sulfuric acid electrolyte) begins at a potential below 0.5 V/RHE during the anodic sweep. During potentiostatic measurements, a maximum current of 0.8 mA mg(-1) was obtained at 0.4 V. Measurements of DEMS showed that the methanol oxidation reaction over tungsten carbide produces CO2 (m/z=44); no methylformate (m/z=60) was detected. These results are discussed in the context of the continued search for alternative materials for the anode catalyst of direct methanol fuel cells.