Parameterized Algorithms for MAX COLORABLE INDUCED SUBGRAPH Problem on Perfect Graphs

We address the parameterized complexity ofMaxColorable Induced Subgraph on perfect graphs. The problem asks for a maximum sized q-colorable induced subgraph of an input graph G. Yannakakis and Gavril IPL 1987] showed that this problem is NP-complete even on split graphs if q is part of input, but gave a n(O(q)) algorithm on chordal graphs. We first observe that the problem is W2]-hard parameterized by q, even on split graphs. However, when parameterized by l, the number of vertices in the solution, we give two fixed-parameter tractable algorithms. The first algorithm runs in time 5.44(l) (n+#alpha(G))(O(1)) where #alpha(G) is the number of maximal independent sets of the input graph. The second algorithm runs in time q(l+o()l())n(O(1))T(alpha) where T-alpha is the time required to find a maximum independent set in any induced subgraph of G. The first algorithm is efficient when the input graph contains only polynomially many maximal independent sets; for example split graphs and co-chordal graphs. The running time of the second algorithm is FPT in l alone (whenever T-alpha is a polynomial in n), since q <= l for all non-trivial situations. Finally, we show that (under standard complexitytheoretic assumptions) the problem does not admit a polynomial kernel on split and perfect graphs in the following sense: (a) On split graphs, we do not expect a polynomial kernel if q is a part of the input. (b) On perfect graphs, we do not expect a polynomial kernel even for fixed values of q >= 2.

Vertex Cover Gets Faster and Harder on Low Degree Graphs

The problem of finding an optimal vertex cover in a graph is a classic NP-complete problem, and is a special case of the hitting set question. On the other hand, the hitting set problem, when asked in the context of induced geometric objects, often turns out to be exactly the vertex cover problem on restricted classes of graphs. In this work we explore a particular instance of such a phenomenon. We consider the problem of hitting all axis-parallel slabs induced by a point set P, and show that it is equivalent to the problem of finding a vertex cover on a graph whose edge set is the union of two Hamiltonian Paths. We show the latter problem to be NP-complete, and also give an algorithm to find a vertex cover of size at most k, on graphs of maximum degree four, whose running time is 1.2637(k) n(O(1)).

The irregularities of the sunspot cycle and their theoretical modelling

The 11-year sunspot cycle has many irregularities, the most prominent amongst them being the grand minima when sunspots may not be seen for several cycles. After summarizing the relevant observational data about the irregularities, we introduce the flux transport dynamo model, the currently most successful theoretical model for explaining the 11-year sunspot cycle. Then we analyze the respective roles of nonlinearities and random fluctuations in creating the irregularities. We also discuss how it has recently been realized that the fluctuations in meridional circulation also can be a source of irregularities. We end by pointing out that fluctuations in the poloidal field generation and fluctuations in meridional circulation together can explain the occurrences of grand minima.

Rainbow matchings in strongly edge-colored graphs

A rainbow matching of an edge-colored graph G is a matching in which no two edges have the same color. There have been several studies regarding the maximum size of a rainbow matching in a properly edge-colored graph G in terms of its minimum degree 3(G). Wang (2011) asked whether there exists a function f such that a properly edge-colored graph G with at least f (delta(G)) vertices is guaranteed to contain a rainbow matching of size delta(G). This was answered in the affirmative later: the best currently known function Lo and Tan (2014) is f(k) = 4k - 4, for k >= 4 and f (k) = 4k - 3, for k <= 3. Afterwards, the research was focused on finding lower bounds for the size of maximum rainbow matchings in properly edge-colored graphs with fewer than 4 delta(G) - 4 vertices. Strong edge-coloring of a graph G is a restriction of proper edge-coloring where every color class is required to be an induced matching, instead of just being a matching. In this paper, we give lower bounds for the size of a maximum rainbow matching in a strongly edge-colored graph Gin terms of delta(G). We show that for a strongly edge-colored graph G, if |V(G)| >= 2 |3 delta(G)/4|, then G has a rainbow matching of size |3 delta(G)/4|, and if |V(G)| < 2 |3 delta(G)/4|, then G has a rainbow matching of size |V(G)|/2] In addition, we prove that if G is a strongly edge-colored graph that is triangle-free, then it contains a rainbow matching of size at least delta(G). (C) 2015 Elsevier B.V. All rights reserved.

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.

Heterochromatic paths in edge colored graphs without small cycles and heterochromatic-triangle-free graphs

Conditions for the existence of heterochromatic Hamiltonian paths and cycles in edge colored graphs are well investigated in literature. A related problem in this domain is to obtain good lower bounds for the length of a maximum heterochromatic path in an edge colored graph G. This problem is also well explored by now and the lower bounds are often specified as functions of the minimum color degree of G - the minimum number of distinct colors occurring at edges incident to any vertex of G - denoted by v(G). Initially, it was conjectured that the lower bound for the length of a maximum heterochromatic path for an edge colored graph G would be 2v(G)/3]. Chen and Li (2005) showed that the length of a maximum heterochromatic path in an edge colored graph G is at least v(G) - 1, if 1 <= v(G) <= 7, and at least 3v(G)/5] + 1 if v(G) >= 8. They conjectured that the tight lower bound would be v(G) - 1 and demonstrated some examples which achieve this bound. An unpublished manuscript from the same authors (Chen, Li) reported to show that if v(G) >= 8, then G contains a heterochromatic path of length at least 120 + 1. In this paper, we give lower bounds for the length of a maximum heterochromatic path in edge colored graphs without small cycles. We show that if G has no four cycles, then it contains a heterochromatic path of length at least v(G) - o(v(G)) and if the girth of G is at least 4 log(2)(v(G)) + 2, then it contains a heterochromatic path of length at least v(G) - 2, which is only one less than the bound conjectured by Chen and Li (2005). Other special cases considered include lower bounds for the length of a maximum heterochromatic path in edge colored bipartite graphs and triangle-free graphs: for triangle-free graphs we obtain a lower bound of 5v(G)/6] and for bipartite graphs we obtain a lower bound of 6v(G)-3/7]. In this paper, it is also shown that if the coloring is such that G has no heterochromatic triangles, then G contains a heterochromatic path of length at least 13v(G)/17)]. This improves the previously known 3v(G)/4] bound obtained by Chen and Li (2011). We also give a relatively shorter and simpler proof showing that any edge colored graph G contains a heterochromatic path of length at least (C) 2015 Elsevier Ltd. All rights reserved.

DNA intercalative 4-butylaminopyrimido4',5':4,5]thieno(2,3-b)quinoline induces cell cycle arrest and apoptosis in leukemia cells

DNA intercalators are one of the interesting groups in cancer chemotherapy. The development of novel anticancer small molecule has gained remarkable interest over the last decade. In this study, we synthesized and investigated the ability of a tetracyclic-condensed quinoline compound, 4-butylaminopyrimido4',5':4,5]thieno(2,3-b)quinoline (BPTQ), to interact with double-stranded DNA and inhibit cancer cell proliferation. Circular dichroism, topological studies, molecular docking, absorbance, and fluorescence spectral titrations were employed to study the interaction of BPTQ with DNA. Cytotoxicity was studied by performing 3-(4,5-dimethylthiazol-2-yl)-2,5-diphenyltetrazolium bromide (MTT) and lactate dehydrogenase (LDH) assay. Further, cell cycle analysis by flow cytometry, annexin V staining, mitochondrial membrane potential assay, DNA fragmentation, and western blot analysis were used to elucidate the mechanism of action of BPTQ at the cellular level. Spectral, topological, and docking studies confirmed that BPTQ is a typical intercalator of DNA. BPTQ induces dose-dependent inhibitory effect on the proliferation of cancer cells by arresting cells at S and G2/M phase. Further, BPTQ activates the mitochondria-mediated apoptosis pathway, as explicated by a decrease in mitochondrial membrane potential, increase in the Bax:Bcl-2 ratio, and activation of caspases. These results confirmed that BPTQ is a DNA intercalative anticancer molecule, which could aid in the development of future cancer therapeutic agents.

Cross-section fluctuations in open microwave billiards and quantum graphs: The counting-of-maxima method revisited

The fluctuations exhibited by the cross sections generated in a compound-nucleus reaction or, more generally, in a quantum-chaotic scattering process, when varying the excitation energy or another external parameter, are characterized by the width Gamma(corr) of the cross-section correlation function. Brink and Stephen Phys. Lett. 5, 77 (1963)] proposed a method for its determination by simply counting the number of maxima featured by the cross sections as a function of the parameter under consideration. They stated that the product of the average number of maxima per unit energy range and Gamma(corr) is constant in the Ercison region of strongly overlapping resonances. We use the analogy between the scattering formalism for compound-nucleus reactions and for microwave resonators to test this method experimentally with unprecedented accuracy using large data sets and propose an analytical description for the regions of isolated and overlapping resonances.

On Locally Gabriel Geometric Graphs

Let be a set of points in the plane. A geometric graph on is said to be locally Gabriel if for every edge in , the Euclidean disk with the segment joining and as diameter does not contain any points of that are neighbors of or in . A locally Gabriel graph(LGG) is a generalization of Gabriel graph and is motivated by applications in wireless networks. Unlike a Gabriel graph, there is no unique LGG on a given point set since no edge in a LGG is necessarily included or excluded. Thus the edge set of the graph can be customized to optimize certain network parameters depending on the application. The unit distance graph(UDG), introduced by Erdos, is also a LGG. In this paper, we show the following combinatorial bounds on edge complexity and independent sets of LGG: (i) For any , there exists LGG with edges. This improves upon the previous best bound of . (ii) For various subclasses of convex point sets, we show tight linear bounds on the maximum edge complexity of LGG. (iii) For any LGG on any point set, there exists an independent set of size .

Separation index of graphs and stacked 2-spheres

In 1987, Kalai proved that stacked spheres of dimension d >= 3 are characterised by the fact that they attain equality in Barnette's celebrated Lower Bound Theorem. This result does not extend to dimension d = 2. In this article, we give a characterisation of stacked 2-spheres using what we call the separation index. Namely, we show that the separation index of a triangulated 2-sphere is maximal if and only if it is stacked. In addition, we prove that, amongst all n-vertex triangulated 2-spheres, the separation index is minimised by some n-vertex flag sphere for n >= 6. Furthermore, we apply this characterisation of stacked 2-spheres to settle the outstanding 3-dimensional case of the Lutz-Sulanke-Swartz conjecture that ``tight-neighbourly triangulated manifolds are tight''. For dimension d >= 4, the conjecture has already been proved by Effenberger following a result of Novik and Swartz. (C) 2015 Elsevier Inc. All rights reserved.

DESIGN OF AN EXPERIMENTAL TEST FACILITY FOR SUPERCRITICAL CO2 BRAYTON CYCLE

A supercritical CO2 test facility is currently being developed at Indian Institute of Science, Bangalore, India to analyze the performance of a closed loop Brayton cycle for concentrated solar power (CSP) generation. The loop has been designed for an external heat input of 20 kW a pressure range of 75-135 bar, flow rate of 11 kg/min, and a maximum cycle temperature of 525 degrees C. The operation of the loop and the various parametric tests planned to be performed are discussed in this paper The paper addresses various aspects of the loop design with emphasis on design of various components such as regenerator and expansion device. The regenerator design is critical due to sharp property variations in CO2 occurring during the heat exchange process between the hot and cold streams. Two types of heat exchanger configurations 1) tube-in-tube (TITHE) and 2) printed circuit heat exchanger (PCHE) are analyzed and compared. A PCHE is found to be similar to 5 times compact compared to a TITHE for identical heat transfer and pressure drops. The expansion device is being custom designed to achieve the desired pressure drop for a range of operating temperatures. It is found that capillary of 5.5 mm inner diameter and similar to 2 meter length is sufficient to achieve a pressure drop from 130 to 75 bar at a maximum cycle temperature of 525 degrees C.

ADVANCED LOW PRESSURE CYCLE FOR CONCENTRATED SOLAR POWER GENERATION

Turbine inlet pressures of similar to 300 bar in case of CO2 based cycles call for redesigning the cycle in such a way that the optimum high side pressures are restricted to the discharge pressure limits imposed by currently available commercial compressors (similar to 150 bar) for distributed power generation. This leads to a cycle which is a combination of a transcritical condensing and a subcritical cycle with an intercooler and a bifurcation system in it. Using a realistic thermodynamic model, it is predicted that the cycle with the working fluid as a non-flammable mixture of 48.5 % propane and rest CO2 delivers similar to 37.2 % efficiency at 873 K with a high and a low side pressure of 150 and 26 bar respectively. This is in contrast to the best efficiency of similar to 36.1 % offered by a transcritical condensing cycle with the same working fluid at a high side pressure of similar to 300 bar

MOMENT ANALYSIS OF A SCROLL EXPANDER USED IN AN ORGANIC RANKINE CYCLE

Recent studies on small-scale power generation with the organic Rankine cycle suggest superior performance of positive displacement type of expanders compared to turbines. Scroll expanders in particular achieve high isentropic efficiencies due to lower leakage and frictional losses. Performance of scroll machines may be enhanced by the use of non-circular involute curves in place of the circular involutes resulting non-uniform wall thickness. In this paper, a detailed moment analysis is performed for such an expander having volumetric expansion ratio of 5 using thermodynamic models proposed earlier by one of the present authors. The working fluid considered in the power cycle is R-245fa with scroll inlet temperature of 125 degrees C for a gross power output of similar to 3.5 kW. The model developed in this paper is verified with an air scroll compressor available in the literature and then applied to an expander Prediction of small variation of moment with scroll motion recommends use of scroll expander without a flywheel over other positive displacement type of expanders, e.g. reciprocating, where a flywheel is an essential component.

A comparison of the fine-scale structure of the diurnal cycle of tropical rain and lightning

In this study, the fine-scale structure of the diurnal variability of ground-based lightning is systematically compared with satellite-based rain. At the outset, it is shown that tropical variability of lightning exhibits a prominent diurnal mode, much like rain. A comparison of the geographical distribution of the timing of the diurnal maximum shows that there is very good agreement between the two observables over continental and coastal regions throughout the tropics. Following this global tropical comparison, we focus on two regions, Borneo and equatorial South America, both of which show the interplay between oceanward and landward propagations of the phase of the diurnal maximum. Over Borneo, both rain and lightning clearly show a climatological cycle of ``breathing in'' (afternoon to early morning) and ``breathing out'' (morning to early afternoon). Over the equatorial east coast of South America, landward propagation is noticed in rain and lightning from early afternoon to early morning. Along the Pacific coast of South America, both rain and lightning show oceanward propagation. Though qualitatively consistent, over both regions the propagation is seen to extend further in rainfall. Additionally, given that lightning highlights vigorous convection, the timing of its diurnal maximum often precedes that of rainfall in the convective life cycle. (C) 2015 Elsevier B.V. All rights reserved.