Sequences of Maximal Degree Vertices in Graphs

2000 Mathematics Subject Classification: 05C35.

Closo versus Hypercloso Metallaboranes: A DFT Study

The structures and electronic relationship of 9-, 10-, 11-, and 12-vertex closo and hypercloso (isocloso) etallaboranes are explored using OFT calculations. The role of the transition metal in stabilizing the hypercloso borane structures is explained using the concept of orbital compatibility. The hypercloso structures, C6H6MBn-1Hn-1 (n = 9-12; M = Fe, Ru, and Os) are taken as model complexes. Calculations on metal free polyhedral borane BnHn suggest that n vertex hypercloso structures need only n skeleton electron pairs (SEPs), but the structure will have one or more six-degree vertices, whereas the corresponding closo structures with n + 1 SEPs have only four- and five-degree vertices. This high-degree vertex of hypercloso structures can be effectively occupied by transition metal fragments with their highly diffused orbitals. Calculations further show that a heavy transition metal with more diffused orbitals prefers over a light transition metal to form hypercloso geometry, This is in accordance with the fact that there are more experimentally characterized hypercloso structures with the heavy transition metals. The size of the exohedral ligands attached to the metal atom also plays a role in deciding the stability of the hypercloso structure. The interaction between the borane and the metal fragments in the hypercloso geometry is analyzed using the fragment molecular orbital approach. The interconversion of the closo and hypercloso structures by the addition and removal of the electrons is also discussed in terms of the correlation diagrams.

Vasoactivity of Rucaparib, a PARP-1 Inhibitor, is a Complex Process that Involves Myosin Light Chain Kinase, P2 Receptors, and PARP Itself

Therapeutic inhibition of poly(ADP-ribose) polymerase (PARP), as monotherapy or to supplement the potencies of other agents, is a promising strategy in cancer treatment. We previously reported that the first PARP inhibitor to enter clinical trial, rucaparib (AG014699), induced vasodilation in vivo in xenografts, potentiating response to temozolomide. We now report that rucaparib inhibits the activity of the muscle contraction mediator myosin light chain kinase (MLCK) 10-fold more potently than its commercially available inhibitor ML-9. Moreover, rucaparib produces additive relaxation above the maximal degree achievable with ML-9, suggesting that MLCK inhibition is not solely responsible for dilation. Inhibition of nitric oxide synthesis using L-NMMA also failed to impact rucaparib's activity. Rucaparib contains the nicotinamide pharmacophore, suggesting it may inhibit other NAD+-dependent processes. NAD+ exerts P2 purinergic receptor-dependent inhibition of smooth muscle contraction. Indiscriminate blockade of the P2 purinergic receptors with suramin abrogated rucaparib-induced vasodilation in rat arterial tissue without affecting ML-9-evoked dilation, although the specific receptor subtypes responsible have not been unequivocally identified. Furthermore, dorsal window chamber and real time tumor vessel perfusion analyses in PARP-1-/- mice indicate a potential role for PARP in dilation of tumor-recruited vessels. Finally, rucaparib provoked relaxation in 70% of patient-derived tumor-associated vessels. These data provide tantalising evidence of the complexity of the mechanism underlying rucaparib-mediated vasodilation.

Algorithms for Robust Pole Assignment in Singular Systems

The solution of the pole assignment problem by feedback in singular systems is parameterized and conditions are given which guarantee the regularity and maximal degree of the closed loop pencil. A robustness measure is defined, and numerical procedures are described for selecting the free parameters in the feedback to give optimal robustness.

Cubic twistorial string field theory

Witten has recently proposed a string theory in twistor space whose D-instanton contributions are conjectured to compute M = 4 super-Yang-Mills scattering amplitudes. An alternative string theory in twistor space was then proposed whose open string tree amplitudes reproduce the D-instanton computations of maximal degree in Witten's model. In this paper, a cubic open string field theory action is constructed for this alternative string in twistor space, and is shown to be invariant under parity transformations which exchange MHV and googly amplitudes. Since the string field theory action is gauge-invariant and reproduces the correct cubic super-Yang-Mills interactions, it provides strong support for the conjecture that the string theory correctly computes N-point super-Yang-Mills tree amplitudes. © SISSA/ISAS 2004.

The functional structure of the sentence: evidence from non-finite clauses

Non-finite clauses are sentential constituents with a verbal head that lacks a morphological specification for tense and agreement. In this paper I contend that these clauses are defective not only morphologically but also syntactically, in the sense that they all lack some of the functional categories that make up a full sentence. In particular I argue that to-infinitive clauses, gerund(ive) clauses and participial clauses differ among themselves, and with respect to other subordinate clauses, in the degree of structural defectiveness they display, which goes from the almost complete functional structure of the infinitive to the maximal degree of syntactic truncation of participial clauses (analyzed here as verbal small clauses). I also show the significant parallelism that exists in this respect between English and Spanish non-finite clauses, pointing to the implication this may have for a cross-linguistic approach to the cartography of syntactic structures.

Fast distributed approximation algorithms for vertex cover and set cover in anonymous networks

We present a distributed algorithm that finds a maximal edge packing in O(Δ + log* W) synchronous communication rounds in a weighted graph, independent of the number of nodes in the network; here Δ is the maximum degree of the graph and W is the maximum weight. As a direct application, we have a distributed 2-approximation algorithm for minimum-weight vertex cover, with the same running time. We also show how to find an f-approximation of minimum-weight set cover in O(f2k2 + fk log* W) rounds; here k is the maximum size of a subset in the set cover instance, f is the maximum frequency of an element, and W is the maximum weight of a subset. The algorithms are deterministic, and they can be applied in anonymous networks.

Vertex Cover Gets Faster and Harder on Low Degree Graphs

The problem of finding an optimal vertex cover in a graph is a classic NP-complete problem, and is a special case of the hitting set question. On the other hand, the hitting set problem, when asked in the context of induced geometric objects, often turns out to be exactly the vertex cover problem on restricted classes of graphs. In this work we explore a particular instance of such a phenomenon. We consider the problem of hitting all axis-parallel slabs induced by a point set P, and show that it is equivalent to the problem of finding a vertex cover on a graph whose edge set is the union of two Hamiltonian Paths. We show the latter problem to be NP-complete, and also give an algorithm to find a vertex cover of size at most k, on graphs of maximum degree four, whose running time is 1.2637(k) n(O(1)).

An Algorithm for Group Formation and Maximal Independent Set in an Amorphous Computer

Amorphous computing is the study of programming ultra-scale computing environments of smart sensors and actuators cite{white-paper}. The individual elements are identical, asynchronous, randomly placed, embedded and communicate locally via wireless broadcast. Aggregating the processors into groups is a useful paradigm for programming an amorphous computer because groups can be used for specialization, increased robustness, and efficient resource allocation. This paper presents a new algorithm, called the clubs algorithm, for efficiently aggregating processors into groups in an amorphous computer, in time proportional to the local density of processors. The clubs algorithm is well-suited to the unique characteristics of an amorphous computer. In addition, the algorithm derives two properties from the physical embedding of the amorphous computer: an upper bound on the number of groups formed and a constant upper bound on the density of groups. The clubs algorithm can also be extended to find the maximal independent set (MIS) and $Delta + 1$ vertex coloring in an amorphous computer in $O(log N)$ rounds, where $N$ is the total number of elements and $Delta$ is the maximum degree.

On Hamilton cycles in locally connected graphs with vertex degree constraints

It is shown that every connected, locally connected graph with the maximum vertex degree Δ(G)=5 and the minimum vertex degree δ(G)3 is fully cycle extendable. For Δ(G)4, all connected, locally connected graphs, including infinite ones, are explicitly described. The Hamilton Cycle problem for locally connected graphs with Δ(G)7 is shown to be NP-complete

On the Vertex Separation of Maximal Outerplanar Graphs

We investigate the NP-complete problem Vertex Separation (VS) on Maximal Outerplanar Graphs (mops). We formulate and prove a “main theorem for mops”, a necessary and sufficient condition for the vertex separation of a mop being k. The main theorem reduces the vertex separation of mops to a special kind of stretchability, one that we call affixability, of submops.

A local 2-approximation algorithm for the vertex cover problem

We present a distributed 2-approximation algorithm for the minimum vertex cover problem. The algorithm is deterministic, and it runs in (Δ + 1)2 synchronous communication rounds, where Δ is the maximum degree of the graph. For Δ = 3, we give a 2-approximation algorithm also for the weighted version of the problem.