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)).

Role of Vertex Index in Substructure Identification and Activity Prediction: A Study on Antitubercular Activity of a Series of Acid Alkyl Ester Derivatives

Tuberculosis (TB) is a life threatening disease caused due to infection from Mycobacterium tuberculosis (Mtb). That most of the TB strains have become resistant to various existing drugs, development of effective novel drug candidates to combat this disease is a need of the day. In spite of intensive research world-wide, the success rate of discovering a new anti-TB drug is very poor. Therefore, novel drug discovery methods have to be tried. We have used a rule based computational method that utilizes a vertex index, named `distance exponent index (D-x)' (taken x = -4 here) for predicting anti-TB activity of a series of acid alkyl ester derivatives. The method is meant to identify activity related substructures from a series a compounds and predict activity of a compound on that basis. The high degree of successful prediction in the present study suggests that the said method may be useful in discovering effective anti-TB compound. It is also apparent that substructural approaches may be leveraged for wide purposes in computer-aided drug design.

Cubicity, boxicity, and vertex cover

A k-dimensional box is the cartesian product R-1 x R-2 x ... x R-k where each R-i is a closed interval on the real line. The boxicity of a graph G,denoted as box(G), is the minimum integer k such that G is the intersection graph of a collection of k-dimensional boxes. A unit cube in k-dimensional space or a k-cube is defined as the cartesian product R-1 x R-2 x ... x R-k where each Ri is a closed interval on the real line of the form [a(i), a(i) + 1]. The cubicity of G, denoted as cub(G), is the minimum k such that G is the intersection graph of a collection of k-cubes. In this paper we show that cub(G) <= t + inverted right perpendicularlog(n - t)inverted left perpendicular - 1 and box(G) <= left perpendiculart/2right perpendicular + 1, where t is the cardinality of a minimum vertex cover of G and n is the number of vertices of G. We also show the tightness of these upper bounds. F.S. Roberts in his pioneering paper on boxicity and cubicity had shown that for a graph G, box(G) <= left perpendicularn/2right perpendicular and cub(G) <= inverted right perpendicular2n/3inverted left perpendicular, where n is the number of vertices of G, and these bounds are tight. We show that if G is a bipartite graph then box(G) <= inverted right perpendicularn/4inverted left perpendicular and this bound is tight. We also show that if G is a bipartite graph then cub(G) <= n/2 + inverted right perpendicularlog n inverted left perpendicular - 1. We point out that there exist graphs of very high boxicity but with very low chromatic number. For example there exist bipartite (i.e., 2 colorable) graphs with boxicity equal to n/4. Interestingly, if boxicity is very close to n/2, then chromatic number also has to be very high. In particular, we show that if box(G) = n/2 - s, s >= 0, then chi (G) >= n/2s+2, where chi (G) is the chromatic number of G.

Boxicity of Halin graphs

A k-dimensional box is the Cartesian product R-1 x R-2 x ... x R-k where each R-i is a closed interval on the real line. The boxicity of a graph G, denoted as box(G) is the minimum integer k such that G is the intersection graph of a collection of k-dimensional boxes. Halin graphs are the graphs formed by taking a tree with no degree 2 vertex and then connecting its leaves to form a cycle in such a way that the graph has a planar embedding. We prove that if G is a Halin graph that is not isomorphic to K-4, then box(G) = 2. In fact, we prove the stronger result that if G is a planar graph formed by connecting the leaves of any tree in a simple cycle, then box(G) = 2 unless G is isomorphic to K4 (in which case its boxicity is 1).

A note on acyclic edge coloring of complete bipartite graphs

An acyclic edge coloring of a graph is a proper edge coloring such that there are no bichromatic (2-colored) 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). Let Delta = Delta(G) denote the maximum degree of a vertex in a graph G. A complete bipartite graph with n vertices on each side is denoted by K-n,K-n. Alon, McDiarmid and Reed observed that a'(K-p-1,K-p-1) = p for every prime p. In this paper we prove that a'(K-p,K-p) <= p + 2 = Delta + 2 when p is prime. Basavaraju, Chandran and Kummini proved that a'(K-n,K-n) >= n + 2 = Delta + 2 when n is odd, which combined with our result implies that a'(K-p,K-p) = p + 2 = Delta + 2 when p is an odd prime. Moreover we show that if we remove any edge from K-p,K-p, the resulting graph is acyclically Delta + 1 = p + 1-edge-colorable. (C) 2009 Elsevier B.V. All rights reserved.

Acyclic Edge Coloring of Graphs with Maximum Degree 4

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.

On the Arrangement of Cliques in Chordal Graphs with respect to the Cuts

A cut (A, B) (where B = V - A) in a graph G = (V, E) is called internal if and only if there exists a vertex x in A that is not adjacent to any vertex in B and there exists a vertex y is an element of B such that it is not adjacent to any vertex in A. In this paper, we present a theorem regarding the arrangement of cliques in a chordal graph with respect to its internal cuts. Our main result is that given any internal cut (A, B) in a chordal graph G, there exists a clique with kappa(G) + vertices (where kappa(G) is the vertex connectivity of G) such that it is (approximately) bisected by the cut (A, B). In fact we give a stronger result: For any internal cut (A, B) of a chordal graph, and for each i, 0 <= i <= kappa(G) + 1 such that vertical bar K-i vertical bar = kappa(G) + 1, vertical bar A boolean AND K-i vertical bar = i and vertical bar B boolean AND K-i vertical bar = kappa(G) + 1 - i. An immediate corollary of the above result is that the number of edges in any internal cut (of a chordal graph) should be Omega(k(2)), where kappa(G) = k. Prompted by this observation, we investigate the size of internal cuts in terms of the vertex connectivity of the chordal graphs. As a corollary, we show that in chordal graphs, if the edge connectivity is strictly less than the minimum degree, then the size of the mincut is at least kappa(G)(kappa(G)+1)/2 where kappa(G) denotes the vertex connectivity. In contrast, in a general graph the size of the mincut can be equal to kappa(G). This result is tight.

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.

Optimum design of a Lanchester damper for a viscously damped single degree of freedom system subjected to inertial excitation

The problem of designing an optimum Lanchester damper for a viscously damped single degree of freedom system subjected to inertial harmonic excitation is investigated. Two criteria are used for optimizing the performance of the damper: (i) minimum motion transmissibility; (ii) minimum force transmissibility. Explicit expressions are developed for determining the absorber parameters.

A note on synthesis of the general, two-degree-of-freedom linkage

A graphical method is presented for synthesis of the general, seven-link, two-degree-of-freedom plane linkage to generate functions of two variables. The method is based on point position reduction and permits synthesis of the linkage to satisfy upto six arbitrarily selected precision positions.

Optimum design of Lanchester damper for a viscously damped single degree of freedom system by using minimum force transmissibility criterion

The problem of optimum design of a Lanchester damper for minimum force transmission from a viscously damped single degree of freedom system subjected to harmonic excitation is investigated. Explicit expressions are developed for determining the optimum absorber parameters. It is shown that for the particular case of the undamped single degree of freedom system the results reduce to the classical ones obtained by using the concept of a fixed point on the transmissibility curves.

Semi-active vibration isolation using a near-zero-spring-rate device:steady state analysis of a single-degree-of-freedom model

A vibration isolator is described which incorporates a near-zero-spring-rate device within its operating range. The device is an assembly of a vertical spring in parallel with two inclined springs. A low spring rate is achieved by combining the equivalent stiffness in the vertical direction of the inclined springs with the stiffness of the vertical central spring. It is shown that there is a relation between the geometry and the stiffness of the individual springs that results in a low spring rate. Computer simulation studies of a single-degree-of-freedom model for harmonic base input show that the performance of the proposed scheme is superior to that of the passive schemes with linear springs and skyhook damping configuration. The response curves show that, for small to large amplitudes of base disturbance, the system goes into resonance at low frequencies of excitation. Thus, it is possible to achieve very good isolation over a wide low-frequency band. Also, the damper force requirements for the proposed scheme are much lower than for the damper force of a skyhook configuration or a conventional linear spring with a semi-active damper.

Vertex-Fused Metallaborane Clusters: Synthesis, Characterization and Electronic Structure of [(eta(5)-C5Me5Mo)(3)MoB9H18]

The reaction of the [(eta(5)-C5Me5)MoCl4] complex with [LiBH4 - TH F] in toluene at - 70 degrees C, followed by pyrolysis at 110 degrees C, afforded dark brown [(eta(5)-C5Me5Mo)(3)MoB9H18], 2, in parallel with the known [(eta(5)-C5Me5Mo)(2)B5H9], 1. Compound 2 has been characterized in solution by H-1, B-11, and C-13 NMR spectroscopy and elemental analysis, and the structural types were unequivocally established by crystallographic studies. The title compound represents a novel class of vertex-fused clusters in which a Mo atom has been fused in a perpendicular fashion between two molybdaborane clusters. Electronic structure calculations employing density functional theory yield geometries in agreement with the structure determinations, and on grounds of density functional theory calculations, we have analyzed the bonding patterns in the structure,

Boxicity and maximum degree

A d-dimensional box is a Cartesian product of d closed intervals on the real line. The boxicity of a graph is the minimum dimension d such that it is representable as the intersection graph of d-dimensional boxes. We give a short constructive proof that every graph with maximum degree D has boxicity at most 2D2. We also conjecture that the best upper bound is linear in D.

Uniqueness of Walkup's 9-vertex 3-dimensional Klein bottle

Via a computer search, Altshuler and Steinberg found that there are 1296+1 combinatorial 3-manifolds on nine vertices, of which only one is non-sphere. This exceptional 3-manifold View the MathML source triangulates the twisted S2-bundle over S1. It was first constructed by Walkup. In this paper, we present a computer-free proof of the uniqueness of this non-sphere combinatorial 3-manifold. As opposed to the computer-generated proof, ours does not require wading through all the 9-vertex 3-spheres. As a preliminary result, we also show that any 9-vertex combinatorial 3-manifold is equivalent by proper bistellar moves to a 9-vertex neighbourly 3-manifold.