Non-contractible non-edges in 2-connected graphs

Any pair of non-adjacent vertices forms a non-edge in a graph. Contraction of a non-edge merges two non-adjacent vertices into a single vertex such that the edges incident on the non-adjacent vertices are now incident on the merged vertex. In this paper, we consider simple connected graphs, hence parallel edges are removed after contraction. The minimum number of nodes whose removal disconnects the graph is the connectivity of the graph. We say a graph is k-connected, if its connectivity is k. A non-edge in a k-connected graph is contractible if its contraction does not result in a graph of lower connectivity. Otherwise the non-edge is non-contractible. We focus our study on non-contractible non-edges in 2-connected graphs. We show that cycles are the only 2-connected graphs in which every non-edge is non-contractible. (C) 2010 Elsevier B.V. All rights reserved.

Compression of Weighted Graphs

We propose to compress weighted graphs (networks), motivated by the observation that large networks of social, biological, or other relations can be complex to handle and visualize. In the process also known as graph simplication, nodes and (unweighted) edges are grouped to supernodes and superedges, respectively, to obtain a smaller graph. We propose models and algorithms for weighted graphs. The interpretation (i.e. decompression) of a compressed, weighted graph is that a pair of original nodes is connected by an edge if their supernodes are connected by one, and that the weight of an edge is approximated to be the weight of the superedge. The compression problem now consists of choosing supernodes, superedges, and superedge weights so that the approximation error is minimized while the amount of compression is maximized. In this paper, we formulate this task as the 'simple weighted graph compression problem'. We then propose a much wider class of tasks under the name of 'generalized weighted graph compression problem'. The generalized task extends the optimization to preserve longer-range connectivities between nodes, not just individual edge weights. We study the properties of these problems and propose a range of algorithms to solve them, with dierent balances between complexity and quality of the result. We evaluate the problems and algorithms experimentally on real networks. The results indicate that weighted graphs can be compressed efficiently with relatively little compression error.

CA/TG sequence at the 5' end of oligo(A)-tracts strongly modulates DNA curvature

An analysis of the base pair doublet geometries in available crystal structures indicates that the often reported intrinsic curvature of DNA containing oligo-(d(A).d(T)) tracts may also depend on the nature of the flanking sequences. The presence of CA/TG doublet in particular at the 5' end of these tracts is expected to enhance their intrinsic bending property. To test this proposition, three oligonucleotides, d(GAAAAACCCCCC), d(CCCCCCAAAAAG), d(GAAAAATTTTTC), and their complementary sequences were synthesized to study the effect of various flanking sequences, at the 5' and 3' ends of the A-tracts, on the curvature of DNA in solution. An analysis of the polyacrylamide gel electrophoretic mobilities of these sequences under different conditions of salts and temperatures (below their melting points) clearly showed that the oligomer with CA/TG sequence in the center was always more retarded than the oligomer with AC/GT sequence, as well as the oligomer with AT/AT sequence. Hydroxyl radical probing of the sequences with AC/GT and CA/TG doublet junctions gives a similar cutting pattern in the A-tracts, which is quite different from that in the C-tracts, indicating that the oligo(A)-tracts have similar structures in the two oligomers. KMnO4 probing shows that the oligomer with a CA/TG doublet junction forms a kink that is responsible for its inherent curvature and unusual electrophoretic mobility. UV melting shows a reduced thermal stability of the duplex with CA/TG doublet junction, and circular dichroism (CD) studies indicate that a premelting transition occurs in the oligomer with CA/TG doublet step before global melting but not in the oligomer with AC/GT doublet step, which may correspond to thermally induced unbending of the oligomer. These observations indicate that the CA/TG doublet junction at the 5' end of the oligo(A)-tract has a crucial role in modulating the overall curvature in DNA.

CA\TG Sequence at the 5'end of Oligo(A)-tracts Strongly Modulates DNA Curvature

An analysis of the base pair doublet geometries in available crystal structures indicates that the often reported intrinsic curvature of DNA containing oligo-(d(A).d(T)) tracts may also depend on the nature of the flanking sequences. The presence of CA/TG doublet in particular at the 5' end of these tracts is expected to enhance their intrinsic bending property. To test this proposition, three oligonucleotides, d(GAAAAACCCCCC), d(CCCCCCAAAAAG), d(GAAAAATTTTTC), and their complementary sequences were synthesized to study the effect of various flanking sequences, at the 5' and 3' ends of the A-tracts, on the curvature of DNA in solution. An analysis of the polyacrylamide gel electrophoretic mobilities of these sequences under different conditions of salts and temperatures (below their melting points) clearly showed that the oligomer with CA/TG sequence in the center was always more retarded than the oligomer with AC/GT sequence, as well as the oligomer with AT/AT sequence. Hydroxyl radical probing of the sequences with AC/GT and CA/TG doublet junctions gives a similar cutting pattern in the A-tracts, which is quite different from that in the C-tracts, indicating that the oligo(A)-tracts have similar structures in the two oligomers. KMnO4 probing shows that the oligomer with a CA/TG doublet junction forms a kink that is responsible for its inherent curvature and unusual electrophoretic mobility. UV melting shows a reduced thermal stability of the duplex with CA/TG doublet junction, and circular dichroism (CD) studies indicate that a premelting transition occurs in the oligomer with CA/TG doublet step before global melting but not in the oligomer with AC/GT doublet step, which may correspond to thermally induced unbending of the oligomer. These observations indicate that the CA/TG doublet junction at the 5' end of the oligo(A)-tract has a crucial role in modulating the overall curvature in DNA.

On the Nash-Williams′ Lemma in Graph Reconstruction Theory

A generalization of Nash-Williams′ lemma is proved for the Structure of m-uniform null (m − k)-designs. It is then applied to various graph reconstruction problems. A short combinatorial proof of the edge reconstructibility of digraphs having regular underlying undirected graphs (e.g., tournaments) is given. A type of Nash-Williams′ lemma is conjectured for the vertex reconstruction problem.

New Approximation Algorithms for Minimum Cycle Bases of Graphs

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.

CAITG sequence at the 5' end of Oligo(A)-tracts strongly modulates DNA curvature

An analysis of the base pair doublet geometries in available crystal structures indicates that the often reported intrinsic curvature of DNA containing oligo-(d(A).d(T)) tracts may also depend on the nature of the flanking sequences. The presence of CA/TG doublet in particular at the 5' end of these tracts is expected to enhance their intrinsic bending property. To test this proposition, three oligonucleotides, d(GAAAAACCCCCC), d(CCCCCCAAAAAG), d(GAAAAATTTTTC), and their complementary sequences were synthesized to study the effect of various flanking sequences, at the 5' and 3' ends of the A-tracts, on the curvature of DNA in solution. An analysis of the polyacrylamide gel electrophoretic mobilities of these sequences under different conditions of salts and temperatures (below their melting points) clearly showed that the oligomer with CA/TG sequence in the center was always more retarded than the oligomer with AC/GT sequence, as well as the oligomer with AT/AT sequence. Hydroxyl radical probing of the sequences with AC/GT and CA/TG doublet junctions gives a similar cutting pattern in the A-tracts, which is quite different from that in the C-tracts, indicating that the oligo(A)-tracts have similar structures in the two oligomers. KMnO4 probing shows that the oligomer with a CA/TG doublet junction forms a kink that is responsible for its inherent curvature and unusual electrophoretic mobility. UV melting shows a reduced thermal stability of the duplex with CA/TG doublet junction, and circular dichroism (CD) studies indicate that a premelting transition occurs in the oligomer with CA/TG doublet step before global melting but not in the oligomer with AC/GT doublet step, which may correspond to thermally induced unbending of the oligomer. These observations indicate that the CA/TG doublet junction at the 5' end of the oligo(A)-tract has a crucial role in modulating the overall curvature in DNA.

Monte-Carlo estimation of time-dependent statistical characteristics of random dynamical systems

The problem of estimating the time-dependent statistical characteristics of a random dynamical system is studied under two different settings. In the first, the system dynamics is governed by a differential equation parameterized by a random parameter, while in the second, this is governed by a differential equation with an underlying parameter sequence characterized by a continuous time Markov chain. We propose, for the first time in the literature, stochastic approximation algorithms for estimating various time-dependent process characteristics of the system. In particular, we provide efficient estimators for quantities such as the mean, variance and distribution of the process at any given time as well as the joint distribution and the autocorrelation coefficient at different times. A novel aspect of our approach is that we assume that information on the parameter model (i.e., its distribution in the first case and transition probabilities of the Markov chain in the second) is not available in either case. This is unlike most other work in the literature that assumes availability of such information. Also, most of the prior work in the literature is geared towards analyzing the steady-state system behavior of the random dynamical system while our focus is on analyzing the time-dependent statistical characteristics which are in general difficult to obtain. We prove the almost sure convergence of our stochastic approximation scheme in each case to the true value of the quantity being estimated. We provide a general class of strongly consistent estimators for the aforementioned statistical quantities with regular sample average estimators being a specific instance of these. We also present an application of the proposed scheme on a widely used model in population biology. Numerical experiments in this framework show that the time-dependent process characteristics as obtained using our algorithm in each case exhibit excellent agreement with exact results. (C) 2010 Elsevier Inc. All rights reserved.

Chordal Bipartite Graphs with High Boxicity

The boxicity of a graph G is defined as the minimum integer k such that G is an intersection graph of axis-parallel k-dimensional boxes. Chordal bipartite graphs are bipartite graphs that do not contain an induced cycle of length greater than 4. It was conjectured by Otachi, Okamoto and Yamazaki that chordal bipartite graphs have boxicity at most 2. We disprove this conjecture by exhibiting an infinite family of chordal bipartite graphs that have unbounded boxicity.

Some results on the reconstruction problems. p-claw-free, chordal, and p4-reducible graphs

A claw is an induced subgraph isomorphic to K-1,K-3. The claw-point is the point of degree 3 in a claw. A graph is called p-claw-free when no p-cycle has a claw-point on it. It is proved that for p greater than or equal to 4, p-claw-free graphs containing at least one chordless p-cycle are edge reconstructible. It is also proved that chordal graphs are edge reconstructible. These two results together imply the edge reconstructibility of claw-free graphs. A simple proof of vertex reconstructibility of P-4-reducible graphs is also presented. (C) 1995 John Wiley and Sons, Inc.

Regular versus alternating (FeS4)(n) chains: Magnetism in KFeS2 and CsFeS2

We report crystal magnetic susceptibility results of two S = 1/2 one-dimensional Heisenberg antiferromagnets, KFeS2 and CsFeS2. Both compounds consist of (FeS4)(n) chains with an average Fe-Fe distance of 2.7 Angstrom. In KFeS2, all intrachain Fe-Fe distances are identical. Its magnetic susceptibility is typical of a regular antiferromagnetic chain with spin-spin exchange parameter J = -440.7 K. In CsFeS2, however, the Fe-Fe distances alternate between 2.61 and 2.82 Angstrom. This is reflected in its magnetic susceptibility, which could be fitted with J = -640 K, and the degree of alternation, alpha = 0.3. These compounds form a unique pair, and allow for a convenient experimental comparison of the magnetic properties of regular versus alternating Heisenberg chains.

The existence of homeomorphic subgraphs in chordal graphs

We establish conditions for the existence, in a chordal graph, of subgraphs homeomorphic to K-n (n greater than or equal to 3), K-m,K-n (m,n greater than or equal to 2), and wheels W-r (r greater than or equal to 3). Using these results, we develop a simple linear time algorithm for testing planarity of chordal graphs. We also show how these results lead to simple polynomial time algorithms for the Fixed Subgraph Homeomorphism problem on chordal graphs for some special classes of pattern graphs.

Acyclic Edge-Coloring of Planar Graphs

A proper edge-coloring with the property that every cycle contains edges of at least three distinct colors is called an acyclic edge-coloring. The acyclic chromatic index of a graph G, denoted. chi'(alpha)(G), is the minimum k such that G admits an acyclic edge-coloring with k colors. We conjecture that if G is planar and Delta(G) is large enough, then chi'(alpha) (G) = Delta (G). We settle this conjecture for planar graphs with girth at least 5. We also show that chi'(alpha) (G) <= Delta (G) + 12 for all planar G, which improves a previous result by Fiedorowicz, Haluszczak, and Narayan Inform. Process. Lett., 108 (2008), pp. 412-417].