922 resultados para Lexicographic product of graphs
Resumo:
Oxygen Consumption by alternative oxidase (AOX), present in mitochondria of many angiosperms, is known to be cyanide-resistant in contrast to cytochrome oxidase. Its activity in potato tuber (Solarium tuberosum L.) was induced following chilling treatment at 4 degrees C.About half of the total O-2 consumption of succinate oxidation in such mitochondria was found to be sensitive to SHAM, a known inhibitor of AOX activity. Addition of catalase to the reaction mixture of AOX during the reaction decreased the rate of SHAM-sensitive oxygen consumption by nearly half, and addition at the end of the reaction released nearly half of the consumed oxygen by AOX, both typical of catalase action on H2O2. These findings with catalase suggest that the product of reduction of AOX is H2O2 and not H2O, as previously Surmised. In potatoes Subjected to chill stress (4 degrees C) for periods of 3, 5 and >= 8 days the activity of AOX in mitochondria increased progressively with a corresponding increase in the AOX protein detected by immunoblot of the protein.
Resumo:
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). It was conjectured by Alon, Sudakov, and Zaks that for any simple and finite graph G, a'(G) <= Delta+2, where Delta=Delta(G) denotes the maximum degree of G. We prove the conjecture for connected graphs with Delta(G)<= 4, with the additional restriction that m <= 2n-1, where n is the number of vertices and m is the number of edges in G. Note that for any graph G, m <= 2n, when Delta(G)<= 4. It follows that for any graph G if Delta(G)<= 4, then a'(G) <= 7.
Resumo:
Brooks' Theorem says that if for a graph G,Δ(G)=n, then G is n-colourable, unless (1) n=2 and G has an odd cycle as a component, or (2) n>2 and Kn+1 is a component of G. In this paper we prove that if a graph G has none of some three graphs (K1,3;K5−e and H) as an induced subgraph and if Δ(G)greater-or-equal, slanted6 and d(G)<Δ(G), then χ(G)<Δ(G). Also we give examples to show that the hypothesis Δ(G)greater-or-equal, slanted6 can not be non-trivially relaxed and the graph K5−e can not be removed from the hypothesis. Moreover, for a graph G with none of K1,3;K5−e and H as an induced subgraph, we verify Borodin and Kostochka's conjecture that if for a graph G,Δ(G)greater-or-equal, slanted9 and d(G)<Δ(G), then χ(G)<Δ(G).
Resumo:
Rice husk ash (about 95% silica) with known physical and chemical characteristics has been reacted with lime and water. The setting process for a lime-excess and a lime-deficient mixture has been investigated. The product of the reaction has been shown to be a calcium silicate hydrate, C-S-H(I)+ by a combination of thermal analysis, XRD and electron microscopy. Formation of C-S-H(I) accounts for the strength of lime-rice husk ash cement.
Resumo:
In this paper we consider the problems of computing a minimum co-cycle basis and a minimum weakly fundamental co-cycle basis of a directed graph G. A co-cycle in G corresponds to a vertex partition (S,V ∖ S) and a { − 1,0,1} edge incidence vector is associated with each co-cycle. The vector space over ℚ generated by these vectors is the co-cycle space of G. Alternately, the co-cycle space is the orthogonal complement of the cycle space of G. The minimum co-cycle basis problem asks for a set of co-cycles that span the co-cycle space of G and whose sum of weights is minimum. Weakly fundamental co-cycle bases are a special class of co-cycle bases, these form a natural superclass of strictly fundamental co-cycle bases and it is known that computing a minimum weight strictly fundamental co-cycle basis is NP-hard. We show that the co-cycle basis corresponding to the cuts of a Gomory-Hu tree of the underlying undirected graph of G is a minimum co-cycle basis of G and it is also weakly fundamental.
Resumo:
We consider the problem of computing an approximate minimum cycle basis of an undirected edge-weighted graph G with m edges and n vertices; the extension to directed graphs is also discussed. In this problem, a {0,1} incidence vector is associated with each cycle and the vector space over F-2 generated by these vectors is the cycle space of G. A set of cycles is called a cycle basis of G if it forms a basis for its cycle space. A cycle basis where the sum of the weights of the cycles is minimum is called a minimum cycle basis of G. Cycle bases of low weight are useful in a number of contexts, e.g. the analysis of electrical networks, structural engineering, chemistry, and surface reconstruction. We present two new algorithms to compute an approximate minimum cycle basis. For any integer k >= 1, we give (2k - 1)-approximation algorithms with expected running time 0(kmn(1+2/k) + mn((1+1/k)(omega-1))) and deterministic running time 0(n(3+2/k)), respectively. Here omega is the best exponent of matrix multiplication. It is presently known that omega < 2.376. Both algorithms are o(m(omega)) for dense graphs. This is the first time that any algorithm which computes sparse cycle bases with a guarantee drops below the Theta(m(omega)) bound. We also present a 2-approximation algorithm with O(m(omega) root n log n) expected running time, a linear time 2-approximation algorithm for planar graphs and an O(n(3)) time 2.42-approximation algorithm for the complete Euclidean graph in the plane.
Resumo:
The condensation product of 2-carbethoxycyclopentanone and ethyl cyanoacetate is ethyl 2-carbethoxycyclopentylidene cyanoacetate (IIa) and not the one described by Kon and Nanji. Similarly, 2-carbomethoxycyclopentanone and methyl cyanoacetate yield methyl 2-carbomethoxycyclopentylidene cyanoacetate (IIb). The by-products obtained in the first reaction are cyclopentylidene cyanoacetate (IV) and the enamine of 2-carbethoxycyclopentanone (VIa).
Resumo:
The synthesis of the title compound is described and results of some experiments on the degradation of patchouli alcohol are reported.
Resumo:
Ethylα-bromovinylacetate (VII) was condensed with the sodio derivative of ethyl piperonoylacetate (VIII) to give diethylα-vinyl-α′-piperonoylsuccinate (IX). The latter on reduction with lithium aluminium hydride furnished the triol (X), which underwent smooth cyclisation with 1% ethanolic hydrogen chloride to 2-(3′, -methylenedioxyphenyl)-hydroxymethyl-4-vinyltetrahydrofuran (XIa). The structure of XIa was established by Oppenauer oxidation to an aldehyde. Ozonolysis of XIa afforded samin (I).
Resumo:
A synthesis of 1,3-dimethyl-1,3-dicarboxycyclohexane-2-acetic acid has been described, and proved to be an isomer of the C12-acid-an oxidative degradation product of abietic acid.
Resumo:
Chill treatment of potato tubers for 8 days induced mitochondrial O-2 consumption by cyanide-insensitive alternative oxidase (AOX). About half of the total O-2 consumption in such mitochondria was found to be sensitive to salicylhydroxamate (SHAM), a known inhibitor of AOX activity. Addition of catalase to the reaction mixture of AOX during the reaction decreased the rate of SHAM-sensitive O-2 consumption by nearly half, and addition at the end of the reaction released half of the O-2 consumed by AOX, both typical of catalase action on H2O2. This reaffirmed that the product of reduction of O-2 by plant AOX was H2O2 as found earlier and not H2O as reported in some recent reviews.
Resumo:
We consider the problem of computing an approximate minimum cycle basis of an undirected non-negative edge-weighted graph G with m edges and n vertices; the extension to directed graphs is also discussed. In this problem, a {0,1} incidence vector is associated with each cycle and the vector space over F-2 generated by these vectors is the cycle space of G. A set of cycles is called a cycle basis of G if it forms a basis for its cycle space. A cycle basis where the sum of the weights of the cycles is minimum is called a minimum cycle basis of G. Cycle bases of low weight are useful in a number of contexts, e.g. the analysis of electrical networks, structural engineering, chemistry, and surface reconstruction. Although in most such applications any cycle basis can be used, a low weight cycle basis often translates to better performance and/or numerical stability. Despite the fact that the problem can be solved exactly in polynomial time, we design approximation algorithms since the performance of the exact algorithms may be too expensive for some practical applications. We present two new algorithms to compute an approximate minimum cycle basis. For any integer k >= 1, we give (2k - 1)-approximation algorithms with expected running time O(kmn(1+2/k) + mn((1+1/k)(omega-1))) and deterministic running time O(n(3+2/k) ), respectively. Here omega is the best exponent of matrix multiplication. It is presently known that omega < 2.376. Both algorithms are o(m(omega)) for dense graphs. This is the first time that any algorithm which computes sparse cycle bases with a guarantee drops below the Theta(m(omega) ) bound. We also present a 2-approximation algorithm with expected running time O(M-omega root n log n), a linear time 2-approximation algorithm for planar graphs and an O(n(3)) time 2.42-approximation algorithm for the complete Euclidean graph in the plane.