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.

On measurement of top polarization as a probe of t(t)over-bar production mechanisms at the LHC

In this note we demonstrate the use of top polarization in the study of t (t) over bar resonances at the LHC, in the possible case where the dynamics implies a non-zero top polarization. As a probe of top polarization we construct an asymmetry in the decay-lepton azimuthal angle distribution (corresponding to the sign of cos phi(l)) in the laboratory. The asymmetry is non-vanishing even for a symmetric collider like the LHC, where a positive z axis is not uniquely defined. The angular distribution of the leptons has the advantage of being a faithful top-spin analyzer, unaffected by possible anomalous tbW couplings, to linear order. We study, for purposes of demonstration, the case of a Z' as might exist in the little Higgs models. We identify kinematic cuts which ensure that our asymmetry reflects the polarization in sign and magnitude. We investigate possibilities at the LHC with two energy options: root s = 14TeV and root s = 7TeV, as well as at the Tevatron. At the LHC the model predicts net top quark polarization of the order of a few per cent for M-Z' similar or equal to 1200GeV, being as high as 10% for a smaller mass of the Z' of 700GeV and for the largest allowed coupling in the model, the values being higher for the 7TeV option. These polarizations translate to a deviation from the standard-model value of azimuthal asymmetry of up to about 4% (7%) for 14 (7) TeV LHC, whereas for the Tevatron, values as high as 12% are attained. For the 14TeV LHC with an integrated luminosity of 10 fb(-1), these numbers translate into a 3 sigma sensitivity over a large part of the range 500 less than or similar to M-Z' less than or similar to 1500GeV.

Error-free matrix symmetrizers and equivalent symmetric matrices

A symmetrizer of the matrix A is a symmetric solution X that satisfies the matrix equation XA=AprimeX. An exact matrix symmetrizer is computed by obtaining a general algorithm and superimposing a modified multiple modulus residue arithmetic on this algorithm. A procedure based on computing a symmetrizer to obtain a symmetric matrix, called here an equivalent symmetric matrix, whose eigenvalues are the same as those of a given real nonsymmetric matrix is presented.

Analogues of the Wiener-Tauberian and Schwartz theorems for radial functions on symmetric spaces

We prove a Wiener Tauberian theorem for the L-1 spherical functions on a semisimple Lie group of arbitrary real rank. We also establish a Schwartz-type theorem for complex groups. As a corollary we obtain a Wiener Tauberian type result for compactly supported distributions.

Boxicity and Poset Dimension

Let G be a simple, undirected, finite graph with vertex set V(G) and edge set E(C). A k-dimensional box is a Cartesian product of closed intervals a(1), b(1)] x a(2), b(2)] x ... x a(k), b(k)]. The boxicity of G, box(G) is the minimum integer k such that G can be represented as the intersection graph of k-dimensional boxes, i.e. each vertex is mapped to a k-dimensional box and two vertices are adjacent in G if and only if their corresponding boxes intersect. Let P = (S, P) be a poset where S is the ground set and P is a reflexive, anti-symmetric and transitive binary relation on S. The dimension of P, dim(P) is the minimum integer l such that P can be expressed as the intersection of t total orders. Let G(P) be the underlying comparability graph of P. It is a well-known fact that posets with the same underlying comparability graph have the same dimension. The first result of this paper links the dimension of a poset to the boxicity of its underlying comparability graph. In particular, we show that for any poset P, box(G(P))/(chi(G(P)) - 1) <= dim(P) <= 2box(G(P)), where chi(G(P)) is the chromatic number of G(P) and chi(G(P)) not equal 1. The second result of the paper relates the boxicity of a graph G with a natural partial order associated with its extended double cover, denoted as G(c). Let P-c be the natural height-2 poset associated with G(c) by making A the set of minimal elements and B the set of maximal elements. We show that box(G)/2 <= dim(P-c) <= 2box(G) + 4. These results have some immediate and significant consequences. The upper bound dim(P) <= 2box(G(P)) allows us to derive hitherto unknown upper bounds for poset dimension. In the other direction, using the already known bounds for partial order dimension we get the following: (I) The boxicity of any graph with maximum degree Delta is O(Delta log(2) Delta) which is an improvement over the best known upper bound of Delta(2) + 2. (2) There exist graphs with boxicity Omega(Delta log Delta). This disproves a conjecture that the boxicity of a graph is O(Delta). (3) There exists no polynomial-time algorithm to approximate the boxicity of a bipartite graph on n vertices with a factor of O(n(0.5-epsilon)) for any epsilon > 0, unless NP=ZPP.

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.

Resonant absorption of alfvén waves near a neutral point

It is shown that, although the mathematical analysis of the Alfven-wave equation does not show any variation at non-zero or zero singular points, the role of surface waves in the physical mechanism of resonant absorption of Alfven waves is very different at these points. This difference becomes even greater when resistivity is taken into account. At the neutral point the zero-frequency surface waves that are symmetric surface modes of the structured neutral layer couple to the tearing mode instability of the layer. The importance of this study for the energy balance in tearing modes and the association of surface waves with driven magnetic reconnection is also pointed out.

Stabilizing trench's algorithm to invert symmetric toeplitz matrices

Presented here is a stable algorithm that uses Zohar's formulation of Trench's algorithm and computes the inverse of a symmetric Toeplitz matrix including those with vanishing or nearvanishing leading minors. The algorithm is based on a diagonal modification of the matrix, and exploits symmetry and persymmetry properties of the inverse matrix.

Correlation of Kauzman temperature with odd-even effect in n-alkanes

A unique correlation has been established between Kauzmann temperature (Tk1) and the odd–even effect in n‐alkanes. The derived new parameter, i.e., Tm/Tk1 obtained from entropy conservation at Tk1, when plotted against chain length, provides a much sharper odd–even contrast than entropy of fusion plot reported earlier. © 1996 American Institute of Physics.

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.

Lopsidedness in WHISP galaxies I. Rotation curves and kinematic lopsidedness

The frequently observed lopsidedness of the distribution of stars and gas in disc galaxies is still considered as a major problem in galaxy dynamics. It is even discussed as an imprint of the formation history of discs and the evolution of baryons in dark matter haloes. Here, we analyse a selected sample of 70 galaxies from the Westerbork Hi Survey of Spiral and Irregular Galaxies. The Hi data allow us to follow the morphology and the kinematics out to very large radii. In the present paper, we present the rotation curves and study the kinematic asymmetry. We extract the rotation curves of the receding and approaching sides separately and show that the kinematic behaviour of disc galaxies can be classified into five different types: symmetric velocity fields where the rotation curves of the receding and approaching sides are almost identical; global distortions where the rotation velocities of the receding and approaching sides have an offset that is constant with radius; local distortions leading to large deviations in the inner and negligible deviations in the outer parts (and vice versa); and distortions that divide the galaxies into two kinematic systems that are visible in terms of the different behaviour of the rotation curves of the receding and approaching sides, which leads to a crossing and a change in side. The kinematic lopsidedness is measured from the maximum rotation velocities, averaged over the plateau of the rotation curves. This gives a good estimate of the global lopsidedness in the outer parts of the sample galaxies. We find that the mean value of the perturbation parameter denoting the lopsided potential as obtained from the kinematic data is 0.056. Altogether, 36% of the sample galaxies are globally lopsided, which can be interpreted as the disc responding to a halo that was distorted by a tidal encounter. In Paper II, we study the morphological lopsidedness of the same sample of galaxies.