Bipartite Powers of k-chordal Graphs

Let k be an integer and k >= 3. A graph G is k-chordal if G does not have an induced cycle of length greater than k. From the definition it is clear that 3-chordal graphs are precisely the class of chordal graphs. Duchet proved that, for every positive integer m, if G m is chordal then so is G(m+2). Brandst `` adt et al. in Andreas Brandsadt, Van Bang Le, and Thomas Szymczak. Duchet- type theorems for powers of HHD- free graphs. Discrete Mathematics, 177(1- 3): 9- 16, 1997.] showed that if G m is k - chordal, then so is G(m+2). Powering a bipartite graph does not preserve its bipartitedness. In order to preserve the bipartitedness of a bipartite graph while powering Chandran et al. introduced the notion of bipartite powering. This notion was introduced to aid their study of boxicity of chordal bipartite graphs. The m - th bipartite power G(m]) of a bipartite graph G is the bipartite graph obtained from G by adding edges (u; v) where d G (u; v) is odd and less than or equal to m. Note that G(m]) = G(m+1]) for each odd m. In this paper we show that, given a bipartite graph G, if G is k-chordal then so is G m], where k, m are positive integers with k >= 4

Design and synthesis of new low band gap organic semiconductors for photovoltaic applications

Donor-acceptor (D-A) conjugated polymers have attracted a good deal of attention in recent years. In D-A systems, the introduction of electron withdrawing groups reduces E-g by lowering the LUMO levels whereas, the introduction of electron donating groups reduces E-g by raising the HOMO levels. Also, conjugated polymers with desired HOMO and LUMO energy levels could be obtained by the proper selection of donor and acceptor units. Because of this reason, D-A conjugated polymers are emerging as promising materials particularly for polymer light emitting diodes (PLEDs) and polymer solar cells (PSCs). We report the design and synthesis of four new narrow band gap donor-acceptor (D-A) conjugated polymers, PTCNN, PTCNF, PTCNV and PTCNO, containing electron donating 3,4-didodecyloxythiophene and electron accepting cyanovinylene units. The effects of further addition of electron donating and electron withdrawing groups to the repeating unit of a D-A conjugated polymer (PTCNN) on its optical and electrochemical properties are discussed. The studies revealed that the nature of D and A units as well as the extent of alternate D-A structure influences the optical and the electrochemical properties of the polymers. All the polymers are thermally stable up to a temperature of 300 degrees C under nitrogen atmosphere. The electrochemical studies revealed that the polymers possess low-lying HOMO energy levels and low-lying LUMO energy levels. In the UV-Vis absorption study, the polymer films displayed broad absorption in the wavelength region of 400-700 nm. The polymers exhibited low optical band gaps in the range 1.70 - 1.77 eV.

SEPARATION DIMENSION OF BOUNDED DEGREE GRAPHS

The separation dimension of a graph G is the smallest natural number k for which the vertices of G can be embedded in R-k such that any pair of disjoint edges in G can be separated by a hyperplane normal to one of the axes. Equivalently, it is the smallest possible cardinality of a family F of total orders of the vertices of G such that for any two disjoint edges of G, there exists at least one total order in F in which all the vertices in one edge precede those in the other. In general, the maximum separation dimension of a graph on n vertices is Theta(log n). In this article, we focus on bounded degree graphs and show that the separation dimension of a graph with maximum degree d is at most 2(9) (log*d)d. We also demonstrate that the above bound is nearly tight by showing that, for every d, almost all d-regular graphs have separation dimension at least d/2]

Boxicity and cubicity of product graphs

The boxicity (cubicity) of a graph G is the minimum natural number k such that G can be represented as an intersection graph of axis-parallel rectangular boxes (axis-parallel unit cubes) in R-k. In this article, we give estimates on the boxicity and the cubicity of Cartesian, strong and direct products of graphs in terms of invariants of the component graphs. In particular, we study the growth, as a function of d, of the boxicity and the cubicity of the dth power of a graph with respect to the three products. Among others, we show a surprising result that the boxicity and the cubicity of the dth Cartesian power of any given finite graph is, respectively, in O(log d/ log log d) and circle dot(d/ log d). On the other hand, we show that there cannot exist any sublinear bound on the growth of the boxicity of powers of a general graph with respect to strong and direct products. (C) 2015 Elsevier Ltd. All rights reserved.

Anomalous lifetime statistics of ligand-receptor binding in a tethered polymer system

In this paper, motivated by observations of non-exponential decay times in the stochastic binding and release of ligand-receptor systems, exemplified by the work of Rogers et al on optically trapped DNA-coated colloids (Rogers et al 2013 Soft Matter 9 6412), we explore the general problem of polymer-mediated surface adhesion using a simplified model of the phenomenon in which a single polymer molecule, fixed at one end, binds through a ligand at its opposite end to a flat surface a fixed distance L away and uniformly covered with receptor sites. Working within the Wilemski-Fixman approximation to diffusion-controlled reactions, we show that for a flexible Gaussian chain, the predicted distribution of times f(t) for which the ligand and receptor are bound is given, for times much shorter than the longest relaxation time of the polymer, by a power law of the form t(-1/4). We also show when the effects of chain stiffness are incorporated into this model (approximately), the structure of f(t) is altered to t(-1/2). These results broadly mirror the experimental trends in the work cited above.

Upper bound on cubicity in terms of boxicity for graphs of low chromatic number

The boxicity (respectively cubicity) of a graph G is the least integer k such that G can be represented as an intersection graph of axis-parallel k-dimensional boxes (respectively k-dimensional unit cubes) and is denoted by box(G) (respectively cub(G)). It was shown by Adiga and Chandran (2010) that for any graph G, cub(G) <= box(G) log(2) alpha(G], where alpha(G) is the maximum size of an independent set in G. In this note we show that cub(G) <= 2 log(2) X (G)] box(G) + X (G) log(2) alpha(G)], where x (G) is the chromatic number of G. This result can provide a much better upper bound than that of Adiga and Chandran for graph classes with bounded chromatic number. For example, for bipartite graphs we obtain cub(G) <= 2(box(G) + log(2) alpha(G)] Moreover, we show that for every positive integer k, there exist graphs with chromatic number k such that for every epsilon > 0, the value given by our upper bound is at most (1 + epsilon) times their cubicity. Thus, our upper bound is almost tight. (c) 2015 Elsevier B.V. All rights reserved.