Edge intersection graphs of systems of paths on a grid with a bounded number of bends

We answer some of the questions raised by Golumbic, Lipshteyn and Stern and obtain some other results about edge intersection graphs of paths on a grid (EPG graphs). We show that for any d≥4, in order to represent every n vertex graph with maximum degree d as an edge intersection graph of n paths on a grid, a grid of area Θ(n²) is needed. We also show several results related to the classes B_k-EPG, where B_k-EPG denotes the class of graphs that have an EPG representation such that each path has at most k bends. In particular, we prove: For a fixed k and a sufficiently large n, the complete bipartite graph K_m,n does not belong to B_2m−3-EPG (it is known that this graph belongs to B_2m−2-EPG); for any odd integer k we have B_k-EPG B_k+1-EPG; there is no number k such that all graphs belong to B_k-EPG; only 2^O(knlog(kn)) out of all the labeled graphs with n vertices are in B_k-EPG.     

Intersection models of weakly chordal graphs

We first present new structural properties of a two-pair in various graphs. A two-pair is used in a well-known characterization of weakly chordal graphs. Based on these properties, we prove the main theorem: a graph G is a weakly chordal ()-free graph if and only if G is an edge intersection graph of subtrees on a tree with maximum degree 4. This characterizes the so called [4, 4, 2] graphs. The proof of the theorem constructively finds the representation. Thus, we obtain an algorithm to construct an edge intersection model of subtrees on a tree with maximum degree 4 for such a given graph. This is a recognition algorithm for [4, 4, 2] graphs.     

Characterizing path graphs by forbidden induced subgraphs

A path graph is the intersection graph of subpaths of a tree. In 1970, Renz asked for a characterization of path graphs by forbidden induced subgraphs. We answer this question by determining the complete list of graphs that are not path graphs and are minimal with this property. © 2009 Wiley Periodicals, Inc. J Graph Theory 62: 369–384, 2009     

On the Equations De.ning Curves in a Polynomial Algebra

Let A be a commutative Noetherian ring of dimension n (n ≥ 3). Let I be a local complete intersection ideal in A[T] of height n. Suppose I/I ² is free A[T]/I-module of rank n and (A[T]/I) is torsion in K ₀(A[T]). It is proved in this article that I is a set theoretic complete intersection ideal in A[T] if one of the following conditions holds: (1) n ≥ 5, odd; (2) n is even, and A contains the field of rational numbers; (3) n = 3, and A contains the field of rational numbers.     

Ab initio insights on photophysics of 9-methylhypoxanthine

In this work, the low-lying electronic singlet states of 9-methylhypoxanthine (9MHPX) were explored by the complete active space self-consistent-field (CASSCF) and complete active space second-order perturbation theory (CASPT2) calculations, and the conical intersections between the optically bright excited S₁ state and ground S₀ state were optimised by the two-root state-averaged SA-2-CASSCF approach. These studies indicate that four slightly different kinds of S₁/S₀ conical intersections are identified computationally for 9MHPX, corresponding to four main internal conversion pathways, respectively, all of which are found to show the comparable timescales according to dynamics simulations. At the CASPT2 level, four bright ππ* transitions of 9MHPX are calculated to locate at 4.47, 5.35, 5.97 and 6.30 eV, respectively, responsible for the available experimental absorption peaks of 9MHPX in the vapour phase (4.41, 5.19, 6.05 and 6.42 eV). Though one relatively weak ππ* transition computed at 5.69 eV is not observed in the vapour phase, it is in accordance with the circular dichroism measurement of another hypoxanthine derivative deoxyinosine 5'-phosphate near 5.51 eV.     

The fine triangle intersections for maximum kite packings

In this paper, the fine triangle intersection problem for a pair of maximum kite packings is investigated. Let Fin(v) = {(s,t) : a pair of maximum kite packings of order v intersecting in s blocks and s+t triangles}. Let Adm(v) = {(s, t) : s + t ≤ bv , s,t are non-negative integers}, where b v = v(v 1)/8 . It is established that Fin(v) = Adm(v)\{(bv-1, 0), (bv-1,1)} for any integer v ≡ 0, 1 (mod 8) and v ≥ 8; Fin(v) = Adm(v) for any integer v ≡ 2, 3, 4, 5, 6, 7 (mod 8) and v ≥ 4.