A necessary and sufficient condition for acyclic graphs

This letter gives a new necessary and sufficient condition to determine whether a directed graph is acyclic.

Improvement On Brooks Chromatic Bound For A Class Of Graphs

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

Approximation algorithm for maximum independent set in planar traingle-free graphs

The maximum independent set problem is NP-complete even when restricted to planar graphs, cubic planar graphs or triangle free graphs. The problem of finding an absolute approximation still remains NP-complete. Various polynomial time approximation algorithms, that guarantee a fixed worst case ratio between the independent set size obtained to the maximum independent set size, in planar graphs have been proposed. We present in this paper a simple and efficient, O(|V|) algorithm that guarantees a ratio 1/2, for planar triangle free graphs. The algorithm differs completely from other approaches, in that, it collects groups of independent vertices at a time. Certain bounds we obtain in this paper relate to some interesting questions in the theory of extremal graphs.

Protein A: nature's universal anti-antibody

Staphylococcal protein A specifically interacts with immunogobulins. This fact is being used in various disciplines of biology and some of the unique properties of protein A and their applications are summarized in this review.

Universal jellium BCS picture for Peierls and spin-Peierls phase transitions

Both metal-insulator Peierls and antiferromagnetic spin-Peierls dimerized phase transitions are observed to have a BCS electron-phonon interaction parameter which is compatible with the jellium value λ = 2/3π ≈ 0.21.

Rectangular universal cellular array

A rectangular universal cellular array consisting of cells having three inputs and one output is described. This array is based on the Reed-Muller canonical expansion of a switching function. Although the total number of external input pins required in this array is the same as that of a rectangular array proposed in the literature, the number of cells is very much less.

Algorithms for Constructing Hierarchical Graphs

An algorithm is described for developing a hierarchy among a set of elements having certain precedence relations. This algorithm, which is based on tracing a path through the graph, is easily implemented by a computer.

Algorithms for Constructing Hierarchical Graphs

An algorithm is described for developing a hierarchy among a set of elements having certain precedence relations. This algorithm, which is based on tracing a path through the graph, is easily implemented by a computer.

Protein A: nature's universal anti-antibody

Staphylococcal protein A specifically interacts with immunogobulins. This fact is being used in various disciplines of biology and some of the unique properties of protein A and their applications are summarized in this review.

The hydrogen bond: a molecular beam microwave spectroscopist's view with a universal appeal

In this manuscript, we propose a criterion for a weakly bound complex formed in a supersonic beam to be characterized as a `hydrogen bonded complex'. For a `hydrogen bonded complex', the zero point energy along any large amplitude vibrational coordinate that destroys the orientational preference for the hydrogen bond should be significantly below the barrier along that coordinate so that there is at least one bound level. These are vibrational modes that do not lead to the breakdown of the complex as a whole. If the zero point level is higher than the barrier, the `hydrogen bond' would not be able to stabilize the orientation which favors it and it is no longer sensible to characterize a complex as hydrogen bonded. Four complexes, Ar-2-H2O, Ar-2-H2S, C2H4-H2O and C2H4-H2S, were chosen for investigations. Zero point energies and barriers for large amplitude motions were calculated at a reasonable level of calculation, MP2(full)/aug-cc-pVTZ, for all these complexes. Atoms in molecules (AIM) theoretical analyses of these complexes were carried out as well. All these complexes would be considered hydrogen bonded according to the AIM theoretical criteria suggested by Koch and Popelier for C-H center dot center dot center dot O hydrogen bonds (U. Koch and P. L. A. Popelier, J. Phys. Chem., 1995, 99, 9747), which has been widely and, at times, incorrectly used for all types of contacts involving H. It is shown that, according to the criterion proposed here, the Ar-2-H2O/H2S complexes are not hydrogen bonded even at zero kelvin and C2H4-H2O/H2S complexes are. This analysis can naturally be extended to all temperatures. It can explain the recent experimental observations on crystal structures of H2S at various conditions and the crossed beam scattering studies on rare gases with H2O and H2S.

Geometric Representation of Graphs in Low Dimension Using Axis Parallel Boxes

An axis-parallel k-dimensional box is a Cartesian product R-1 x R-2 x...x R-k where R-i (for 1 <= i <= k) is a closed interval of the form [a(i), b(i)] on the real line. For a graph G, its boxicity box(G) is the minimum dimension k, such that G is representable as the intersection graph of (axis-parallel) boxes in k-dimensional space. The concept of boxicity finds applications in various areas such as ecology, operations research etc. A number of NP-hard problems are either polynomial time solvable or have much better approximation ratio on low boxicity graphs. For example, the max-clique problem is polynomial time solvable on bounded boxicity graphs and the maximum independent set problem for boxicity d graphs, given a box representation, has a left perpendicular1 + 1/c log n right perpendicular(d-1) approximation ratio for any constant c >= 1 when d >= 2. In most cases, the first step usually is computing a low dimensional box representation of the given graph. Deciding whether the boxicity of a graph is at most 2 itself is NP-hard. We give an efficient randomized algorithm to construct a box representation of any graph G on n vertices in left perpendicular(Delta + 2) ln nright perpendicular dimensions, where Delta is the maximum degree of G. This algorithm implies that box(G) <= left perpendicular(Delta + 2) ln nright perpendicular for any graph G. Our bound is tight up to a factor of ln n. We also show that our randomized algorithm can be derandomized to get a polynomial time deterministic algorithm. Though our general upper bound is in terms of maximum degree Delta, we show that for almost all graphs on n vertices, their boxicity is O(d(av) ln n) where d(av) is the average degree.

Acyclic edge coloring of subcubic graphs

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 it is denoted by a′(G). From a result of Burnstein it follows that all subcubic graphs are acyclically edge colorable using five colors. This result is tight since there are 3-regular graphs which require five colors. In this paper we prove that any non-regular connected graph of maximum degree 3 is acyclically edge colorable using at most four colors. This result is tight since all edge maximal non-regular connected graphs of maximum degree 3 require four colors.

A universal relation for the cohesive energy of nanoparticles

A universal relation between the cohesive energy and the particle size has been predicted based on the liquid-drop model. The universal relation is well supported by other theoretical models and the available experimental data. The universal relations for intermediate size range as well as for particles with very few atoms are discussed. A comparison of onset temperature of evaporation also establishes a universal relation.

A note on the Hadwiger number of circular arc graphs

The intention of this note is to motivate the researchers to study Hadwiger's conjecture for circular arc graphs. Let η(G) denote the largest clique minor of a graph G, and let χ(G) denote its chromatic number. Hadwiger's conjecture states that η(G)greater-or-equal, slantedχ(G) and is one of the most important and difficult open problems in graph theory. From the point of view of researchers who are sceptical of the validity of the conjecture, it is interesting to study the conjecture for graph classes where η(G) is guaranteed not to grow too fast with respect to χ(G), since such classes of graphs are indeed a reasonable place to look for possible counterexamples. We show that in any circular arc graph G, η(G)less-than-or-equals, slant2χ(G)−1, and there is a family with equality. So, it makes sense to study Hadwiger's conjecture for this family.

On the Cubicity of AT-Free Graphs and Circular-Arc Graphs

A unit cube in k dimensions (k-cube) is defined as the Cartesian product R-1 x R-2 x ... x R-k where R-i (for 1 <= i <= k) is a closed interval of the form [a(i), a(i) + 1] on the real line. A graph G on n nodes is said to be representable as the intersection of k-cubes (cube representation in k dimensions) if each vertex of C can be mapped to a k-cube such that two vertices are adjacent in G if and only if their corresponding k-cubes have a non-empty intersection. The cubicity of G denoted as cub(G) is the minimum k for which G can be represented as the intersection of k-cubes. An interesting aspect about cubicity is that many problems known to be NP-complete for general graphs have polynomial time deterministic algorithms or have good approximation ratios in graphs of low cubicity. In most of these algorithms, computing a low dimensional cube representation of the given graph is usually the first step. We give an O(bw . n) algorithm to compute the cube representation of a general graph G in bw + 1 dimensions given a bandwidth ordering of the vertices of G, where bw is the bandwidth of G. As a consequence, we get O(Delta) upper bounds on the cubicity of many well-known graph classes such as AT-free graphs, circular-arc graphs and cocomparability graphs which have O(Delta) bandwidth. Thus we have: 1. cub(G) <= 3 Delta - 1, if G is an AT-free graph. 2. cub(G) <= 2 Delta + 1, if G is a circular-arc graph. 3. cub(G) <= 2 Delta, if G is a cocomparability graph. Also for these graph classes, there axe constant factor approximation algorithms for bandwidth computation that generate orderings of vertices with O(Delta) width. We can thus generate the cube representation of such graphs in O(Delta) dimensions in polynomial time.