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.

Mean-field theories of Hubbard and t-J models

We report novel results obtained for the Hubbard and t-J models by various mean-field approximations.

Social Life of Captive Asian Elephants (Elephas maximus) in Southern India: Implications for Elephant Welfare

Asian elephants in the wild live in complex social societies; in captivity, however, management often occurs in solitary conditions, especially at the temples and private places of India. To investigate the effect of social isolation, this study assessed the social group sizes and the presence of stereotypies among 140 captive Asian elephants managed in 3 captive systems (private, temple, and forest department) in Tamil Nadu, India, between 2003 and 2005. The majority of the facilities in the private (82%) and temple (95%) systems held a single elephant without opportunity for social interaction. The forest department managed the elephants in significantly larger groups than the private and temple systems. Among the 3 systems, the proportion of elephants with stereotypies was the highest in temple (49%) followed by private system (26%) and the forest department facility (6%); this correlates with the social isolation trend observed in the 3 systems and suggests a possible link between social isolation and abnormal elephant behavior separate from other environmental factors. The results of this study indicate it would be of greater benefit to elephant well being to keep the patchily distributed solitary temple and private elephants who are socially compatible and free from contagious diseases in small social groups at ocommon elephant houseso for socialization.