Numerical evidence against a conjecture on the cover time of planar graphs

We investigate a conjecture on the cover times of planar graphs by means of large Monte Carlo simulations. The conjecture states that the cover time tau (G(N)) of a planar graph G(N) of N vertices and maximal degree d is lower bounded by tau (G(N)) >= C(d)N(lnN)(2) with C(d) = (d/4 pi) tan(pi/d), with equality holding for some geometries. We tested this conjecture on the regular honeycomb (d = 3), regular square (d = 4), regular elongated triangular (d = 5), and regular triangular (d = 6) lattices, as well as on the nonregular Union Jack lattice (d(min) = 4, d(max) = 8). Indeed, the Monte Carlo data suggest that the rigorous lower bound may hold as an equality for most of these lattices, with an interesting issue in the case of the Union Jack lattice. The data for the honeycomb lattice, however, violate the bound with the conjectured constant. The empirical probability distribution function of the cover time for the square lattice is also briefly presented, since very little is known about cover time probability distribution functions in general.

On the k-restricted structure ratio in planar and outerplanar graphs

A planar k-restricted structure is a simple graph whose blocks are planar and each has at most k vertices. Planar k-restricted structures are used by approximation algorithms for Maximum Weight Planar Subgraph, which motivates this work. The planar k-restricted ratio is the infimum, over simple planar graphs H, of the ratio of the number of edges in a maximum k-restricted structure subgraph of H to the number edges of H. We prove that, as k tends to infinity, the planar k-restricted ratio tends to 1/2. The same result holds for the weighted version. Our results are based on analyzing the analogous ratios for outerplanar and weighted outerplanar graphs. Here both ratios tend to 1 as k goes to infinity, and we provide good estimates of the rates of convergence, showing that they differ in the weighted from the unweighted case.

On the resilience of long cycles in random graphs

In this paper we determine the local and global resilience of random graphs G(n,p) (p >> n(-1)) with respect to the property of containing a cycle of length at least (1 - alpha)n. Roughly speaking, given alpha > 0, we determine the smallest r(g) (G, alpha) with the property that almost surely every subgraph of G = G(n,p) having more than r(g) (G, alpha)vertical bar E(G)vertical bar edges contains a cycle of length at least (1 - alpha)n (global resilience). We also obtain, for alpha < 1/2, the smallest r(l) (G, alpha) such that any H subset of G having deg(H) (v) larger than r(l) (G, alpha) deg(G) (v) for all v is an element of V(G) contains a cycle of length at least (1 - alpha)n (local resilience). The results above are in fact proved in the more general setting of pseudorandom graphs.

Characterization of electrical penetration graphs of Bucephalogonia xanthophis, a vector of Xylella fastidiosa in citrus

The sharpshooter Bucephalogonia xanthophis (Berg) (Homoptera: Cicadellidae) is a vector of the xylem-limited bacterium, Xylella fastidiosa (Wells, Raju, Hung, Weisburg, Mandelco-Paul, and Brenner), which causes citrus variegated chlorosis. Despite the importance of citrus variegated chlorosis, the probing behavior of vectors on citrus and its implications for transmission of X. fastidiosa have not been studied. Here we studied electrical penetration graph (EPG-DC system) waveforms produced by B. xanthophis on Citrus sinensis (L.) Osbeck (Rutaceae), and their relationships with stylet activities and xylem ingestion. Electrical penetration graph waveforms were described based on amplitude, frequency, voltage level, and electrical origin of the observed traces during stylet penetration on plant tissues. The main waveforms were correlated with histological observations of salivary sheaths in plant tissues and excretion analysis, in order to determine stylet activities and their precise position. Six waveforms and associated activities are described: (S) secretion of salivary sheath and intracellular stylet pathway, (R) resting during stylet pathway, (Xc) contact of stylets with xylem vessels, (Xi) active xylem ingestion, (N) interruption within the xylem phase (during Xc or Xi), and (W) withdrawal of stylet from the plant. The sharpshooter spent 91.8% of its probing time with its stylet in the xylem, where the main activity was ingestion (Xi: 97.5%). During a probe, the most likely sequence of events is secretion of salivary sheath and pathway (S) through epidermal and parenchyma cells (all individuals), followed by contact with xylem (Xc) (67.6% of all individuals) and ingestion (Xi) (88.3% of those that exhibit waveform Xc). The mean time to contact the xylem (Xc) and initiate ingestion (Xi) after onset of the first probe was 27.8 and 34.2 min, respectively. However, sustained xylem ingestion (Xi > 5 min) was established after 39.8 min, on average. This information is basic for future studies on the transmission mechanisms of X. fastidiosa and in order to establish control strategies aimed at interfering with this process.

PARALLEL ALGORITHMS FOR MAXIMAL CLIQUES IN CIRCLE GRAPHS AND UNRESTRICTED DEPTH SEARCH

We present parallel algorithms on the BSP/CGM model, with p processors, to count and generate all the maximal cliques of a circle graph with n vertices and m edges. To count the number of all the maximal cliques, without actually generating them, our algorithm requires O(log p) communication rounds with O(nm/p) local computation time. We also present an algorithm to generate the first maximal clique in O(log p) communication rounds with O(nm/p) local computation, and to generate each one of the subsequent maximal cliques this algorithm requires O(log p) communication rounds with O(m/p) local computation. The maximal cliques generation algorithm is based on generating all maximal paths in a directed acyclic graph, and we present an algorithm for this problem that uses O(log p) communication rounds with O(m/p) local computation for each maximal path. We also show that the presented algorithms can be extended to the CREW PRAM model.

Minimum cycle cover and Chinese postman problems on mixed graphs with bounded tree-width

Let M = (V, E, A) be a mixed graph with vertex set V, edge set E and arc set A. A cycle cover of M is a family C = {C(1), ... , C(k)} of cycles of M such that each edge/arc of M belongs to at least one cycle in C. The weight of C is Sigma(k)(i=1) vertical bar C(i)vertical bar. The minimum cycle cover problem is the following: given a strongly connected mixed graph M without bridges, find a cycle cover of M with weight as small as possible. The Chinese postman problem is: given a strongly connected mixed graph M, find a minimum length closed walk using all edges and arcs of M. These problems are NP-hard. We show that they can be solved in polynomial time if M has bounded tree-width. (C) 2008 Elsevier B.V. All rights reserved.

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

Short-Term effect of COX-2 selective inhibitor as an adjunct for the treatment of periodontal disease: a clinical double-blind study in humans

Adjunctive therapeutic strategies that modulate the inflammatory mediators can play a significant role in periodontal therapy. In this double-blind, placebo-controlled study, 60 subjects diagnosed as periodontitis patients were evaluated for 28 days after periodontal treatment combined with selective cyclooxygenase-2 (COX-2) inhibitor. The experimental group received scaling and root planning (SRP) combined with the Loxoprofen antiinflammatory drug (SRP+Loxoprofen). The control group received SRP combined with placebo (SRP+placebo). Plaque index (PI), probing pocket depth (PD) and bleeding on probing (BOP) were monitored with an electronic probe at baseline and after 14 and 28 days. Both groups displayed clinical improvement in PD, PI and BOP. They also showed statistically similar values (p>0.05) of PD reduction on day 14 (0.4 mm) and on day 28 (0.6 mm). At the baseline, few deeper sites (>7 mm) from SRP+Loxoprofen group were responsible and most PD reduction was observed after 14 days (p<0.05). The percentage of remaining deep pockets (>7 mm) after 14 days in the SRP+Loxoprofen group was significantly lower (p<0.05) than in the SRP+placebo group. Loxoprofen presents potential effect as an adjunct of periodontal disease treatment, but long-term clinical trials are necessary to confirm its efficacy.

Shelf-life of a 2.5% sodium hypochlorite solution as determined by arrhenius equation

Accelerated stability tests are indicated to assess, within a short time, the degree of chemical degradation that may affect an active substance, either alone or in a formula, under normal storage conditions. This method is based on increased stress conditions to accelerate the rate of chemical degradation. Based on the equation of the straight line obtained as a function of the reaction order (at 50 and 70 ºC) and using Arrhenius equation, the speed of the reaction was calculated for the temperature of 20 ºC (normal storage conditions). This model of accelerated stability test makes it possible to predict the chemical stability of any active substance at any given moment, as long as the method to quantify the chemical substance is available. As an example of the applicability of Arrhenius equation in accelerated stability tests, a 2.5% sodium hypochlorite solution was analyzed due to its chemical instability. Iodometric titration was used to quantify free residual chlorine in the solutions. Based on data obtained keeping this solution at 50 and 70 ºC, using Arrhenius equation and considering 2.0% of free residual chlorine as the minimum acceptable threshold, the shelf-life was equal to 166 days at 20 ºC. This model, however, makes it possible to calculate shelf-life at any other given temperature.

Expressão da proteína erbB-2 e dos receptores de hormônios na transição das regiões in situ para invasora de tumores da mama

OBJETIVOS: avaliar a expressão de erbB-2 e dos receptores hormonais para estrógeno e progesterona (RE/RP) nas regiões de transição entre as frações in situ e invasoras de neoplasias ductais da mama (CDIS e CDI, respectivamente). MÉTODOS: oitenta e cinco casos de neoplasias mamárias, contendo regiões contíguas de CDIS e CDI, foram selecionados. Espécimes histológicos das áreas de CDIS e de CDI foram obtidos através da técnica de tissue microarray (TMA). As expressões da erbB-2 e dos RE/RP foram avaliadas por meio de imunoistoquímica convencional. A comparação da expressão da erbB-2 e dos RE/RP nas frações in situ e invasoras da mama foi realizada com emprego do teste de McNemar. Os intervalos de confiança foram determinados em 5% (p=0,05). Foram calculados coeficientes de correlação intraclasse (ICC) para avaliar a concordância na tabulação cruzada da expressão de erbB-2 e RE/RP nas frações de CDIS e CDI. RESULTADOS: a expressão da erbB-2 não diferiu entre as áreas de CDIS e CDI (p=0,38). Comparando caso a caso suas áreas de CDIS e CDI, houve boa concordância na expressão da erbB-2 (coeficiente de correlação intraclasse, ICC=0,64), dos RP (ICC = 0,71) e dos RE (ICC = 0,64). Considerando apenas tumores cujo componente in situ apresentasse áreas de necrose (comedo), o ICC para erbB-2 foi de 0,4, comparado a 0,6 no conjunto completo de casos. Os ICC não diferiram substancialmente daqueles obtidos com o conjunto completo de espécimes em relação aos RE/RP: para RE, ICC=0,7 (versus 0,7 no conjunto completo), e para RP, ICC=0,7 (versus 0,6 no conjunto completo). CONCLUSÕES: nossos achados sugerem que as expressões de erbB-2 e RE/RP não diferem nos componentes contíguos in situ e invasivo em tumores ductais da mama.

Bottle feeding, increased overjet and Class 2 primary canine relationship: is there any association?

The aim of this study was to investigate the association between bottle feeding and prevalence rates of increased overjet and Class 2 primary canine relationship. The sample consisted of 911 children (461 boys, 450 girls) aged 3 (13.9%), 4 (40.8%), 5 (34%) and 6 (11.3%) years, with complete primary dentition. Information about nutritive and nonnutritive (pacifier and/or digit) sucking habits was collected through questionnaires. Three calibrated dentists (κ: 0.9-1.0 and Rs > 0.90) performed the clinical assessments. The children were divided into four groups: G1 - not bottle-fed; G2 - exclusively bottle-fed; G3 - breast- and bottle-fed, bottle feeding ceased before 3 years of age; and G4 - breast- and bottle-fed, bottle feeding ceased between 3 and 4 years of age. Associations between nutritive and nonnutritive sucking behaviors and the malocclusions studied were analyzed by multiple binary logistic regression (α= 0.05). The frequencies of increased overjet were: 25.3% (G1), 38.8% (G2), 39.2% (G3) and 47.8% (G4). The percentages of Class 2 canine relationship were: 27.9% (G1), 48.8% (G2), 43.4% (G3) and 43% (G4). No significant effect of bottle feeding was found. The chances of diagnosing increased overjet (O.R. = 4.42, p < 0.001) and Class 2 canine relationship (O.R. = 4.02, p < 0.001) were greater for children with pacifier and/or digit-sucking habits, compared to those without a history of nonnutritive sucking behavior. It may be suggested that bottle feeding alone is not directly associated with higher prevalence rates of increased overjet and Class 2 canine relationship in the primary dentition.

Association of polymorphisms at the ADIPOR1 regulatory region with type 2 diabetes and body mass index in a Brazilian population with European or African ancestry

Association studies between ADIPOR1 genetic variants and predisposition to type 2 diabetes (DM2) have provided contradictory results. We determined if two single nucleotide polymorphisms (SNP c.-8503G>A and SNP c.10225C>G) in regulatory regions of ADIPOR1 in 567 Brazilian individuals of European (EA; N = 443) or African (AfA; N = 124) ancestry from rural (quilombo remnants; N = 439) and urban (N = 567) areas. We detected a significant effect of ethnicity on the distribution of the allelic frequencies of both SNPs in these populations (EA: -8503A = 0.27; AfA: -8503A = 0.16; P = 0.001 and EA: 10225G = 0.35; AfA: 10225G = 0.51; P < 0.001). Neither of the polymorphisms were associated with DM2 in the case-control study in EA (SNP c.-8503G>A: DM2 group -8503A = 0.26; control group -8503A = 0.30; P = 0.14/SNP 10225C>G: DM2 group 10225G = 0.37; control group 10225G = 0.32; P = 0.40) and AfA populations (SNP c.-8503G>A: DM2 group -8503A = 0.16; control group -8503A = 0.15; P = 0.34/SNP 10225C>G: DM2 group 10225G = 0.51; control group 10225G = 0.52; P = 0.50). Similarly, none of the polymorphisms were associated with metabolic/anthropometric risk factors for DM2 in any of the three populations, except for HDL cholesterol, which was significantly higher in AfA heterozygotes (GC = 53.75 ± 17.26 mg/dL) than in homozygotes. We conclude that ADIPOR1 polymorphisms are unlikely to be major risk factors for DM2 or for metabolic/anthropometric measurements that represent risk factors for DM2 in populations of European and African ancestries.