Acyclic Edge-Coloring of Planar Graphs

A proper edge-coloring with the property that every cycle contains edges of at least three distinct colors is called an acyclic edge-coloring. The acyclic chromatic index of a graph G, denoted. chi'(alpha)(G), is the minimum k such that G admits an acyclic edge-coloring with k colors. We conjecture that if G is planar and Delta(G) is large enough, then chi'(alpha) (G) = Delta (G). We settle this conjecture for planar graphs with girth at least 5. We also show that chi'(alpha) (G) <= Delta (G) + 12 for all planar G, which improves a previous result by Fiedorowicz, Haluszczak, and Narayan Inform. Process. Lett., 108 (2008), pp. 412-417].

Anomalous Temperature dependence of Fermi-edge Singularity in Modulation-doped AlGaAs/InGaAs/GaAs hetero-structures

The temperature and power dependence of Fermi-edge singularity (FES) in high-density two-dimensional electron gas, specific to pseudomorphic AlxGa1-xAs/InyGa1-yAs/GaAs heterostructures is studied by photoluminescence (PL). In all these structures, there are two prominent transitions E11 and E21 considered to be the result of electron-hole recombination from first and second electron sub-bands with that of first heavy-hole sub-band. FES is observed approximately 5 -10 meV below the E21 transition. At 4.2 K, FES appears as a lower energy shoulder to the E21 transition. The PL intensity of all the three transitions E11, FES and E21 grows linearly with excitation power. However, we observe anomalous behavior of FES with temperature. While PL intensity of E11 and E21 decrease with increasing temperature, FES transition becomes stronger initially and then quenches-off slowly (till 40K). Though it appears as a distinct peak at about 20 K, its maximum is around 7 - 13 K.

Role of interface states associated with transitional nanophase precipitates in the photoluminescence enhancement of SrTiO3 : Pr3+,Al3+

SrTiO3:Pr3+,Al3+ phosphor samples with varying ratios of Sr/Ti/Al were prepared by the gel-carbonate method and the mechanism of enhancement of the red photoluminescence intensity therein was investigated. The photoluminescence (PL) spectra of SrTiO3:Pr3+ show both D-1(2) --> H-3(4) and P-3(0) --> H-3(4) emission in the red and blue spectral regions, respectively, with comparable intensity. The emission intensity of D-1(2) --> H-3(4) is drastically enhanced by the incorporation of Al3+ and excess Ti4+ in the compositional range Sr(Ti,Al-y)(O3+3y/2):Pr3+ (0.2 less than or equal to y less than or equal to 0.4) and SrTi1+xAlyO3+z:Pr3+ (0.2 less than or equal to x less than or equal to 0.5; 0.05 less than or equal to y less than or equal to 0.1; z = 2x + 3y/2) with the complete disappearance of the blue band. This cannot be explained by the simple point defect model as the EPR studies do not show any evidence for the presence of electron or hole centers. TEM investigations show the presence of exsolved nanophases of SrAl12O19 and/or TiO2 in the grain boundary region as well as grain interiors as lamellae which, in turn, form the solid-state defects, namely, dislocation networks, stacking faults and crystallographic shear planes whereby the framework of corner shared TiO6 octehedra changes over to edge-sharing TiO5-AlO5 strands as indicated from the Al-27 MAS NMR studies. The presence of transitional nanophases and the associated defects modify the excitation-emission processes by way of formation of electronic sub-levels at 3.40 and 4.43 eV, leading to magnetic-dipole related red emission with enhanced intensity. This is evidenced by the fact that SrAl12O19:Pr3+,Ti4+ shows bright red emission whereas SrAl12O19:Pr3+ does not show red photoluminescence.

Low-temperature polaronic relaxations with variable range hopping conductivity in FeTiMO(6) (M = Ta,Nb,Sb)

Low-temperature dielectric measurements on FeTiMO(6) (M = Ta,Nb,Sb) rutile-type oxides at frequencies from 0.1 Hz to 10 MHz revealed anomalous dielectric relaxations with frequency dispersion. Unlike the high-temperature relaxor response of these materials, the low-temperature relaxations are polaronic in nature. The relationship between frequency and temperature of dielectric loss peak follows T(-1/4) behavior. The frequency dependence of ac conductivity shows the well-known universal dielectric response, while the dc conductivity follows Mott variable range hopping (VRH) behavior, confirming the polaronic origin of the observed dielectric relaxations. The frequency domain analysis of the dielectric spectra shows evidence for two relaxations, with the high-frequency relaxations following Mott VRH behavior more closely. Significantly, the Cr- and Ga-based analogs, CrTiNbO(6) and GaTiMO(6) (M = Ta,Nb), that were also studied, did not show these anomalies.

Fast edge splitting and Edmonds' arborescence construction for unweighted graphs

Given an unweighted undirected or directed graph with n vertices, m edges and edge connectivity c, we present a new deterministic algorithm for edge splitting. Our algorithm splits-off any specified subset S of vertices satisfying standard conditions (even degree for the undirected case and in-degree ≥ out-degree for the directed case) while maintaining connectivity c for vertices outside S in Õ(m+nc2) time for an undirected graph and Õ(mc) time for a directed graph. This improves the current best deterministic time bounds due to Gabow [8], who splits-off a single vertex in Õ(nc2+m) time for an undirected graph and Õ(mc) time for a directed graph. Further, for appropriate ranges of n, c, |S| it improves the current best randomized bounds due to Benczúr and Karger [2], who split-off a single vertex in an undirected graph in Õ(n2) Monte Carlo time. We give two applications of our edge splitting algorithms. Our first application is a sub-quadratic (in n) algorithm to construct Edmonds' arborescences. A classical result of Edmonds [5] shows that an unweighted directed graph with c edge-disjoint paths from any particular vertex r to every other vertex has exactly c edge-disjoint arborescences rooted at r. For a c edge connected unweighted undirected graph, the same theorem holds on the digraph obtained by replacing each undirected edge by two directed edges, one in each direction. The current fastest construction of these arborescences by Gabow [7] takes Õ(n2c2) time. Our algorithm takes Õ(nc3+m) time for the undirected case and Õ(nc4+mc) time for the directed case. The second application of our splitting algorithm is a new Steiner edge connectivity algorithm for undirected graphs which matches the best known bound of Õ(nc2 + m) time due to Bhalgat et al [3]. Finally, our algorithm can also be viewed as an alternative proof for existential edge splitting theorems due to Lovász [9] and Mader [11].

Altitude variation of aerosol properties over the Himalayan range inferred from spatial measurements

Altitude variations of the mass concentration of black carbon, number concentration of composite aerosols are examined along with the columnar spectral aerosol optical depths using state of the art instruments and the Angstrom parameters are inferred from the ground based measurements at several altitude levels, en route from Manora Peak, Nainital (similar to 1950 m above mean sea level) to a low altitude station Haldwani (similar to 330 m above mean sea level) at its foothill within an aerial distance of <10,000 m. The measurements were done during the winter months (November-February) of 2005, 2006 and 2007 under fair weather conditions. The results show a rapid decrease in all the measured parameters with increase in altitude, with >60% contribution to the AOD coming from the regions below 1000 m. The Angstrom wavelength exponent remained high in the well mixed region, and decreased above. The normalized AOD gradient was used to estimate aerosol mixing height, which was found to be in the altitude range 1000-1500 m, above which the particle concentrations are slowly varying as a function of altitude. The heating rate at the surface is found to be maximum but decreases sharply with increase in altitude. Analysis of the wavelength dependence of absorption aerosol optical depth (AAOD) showed that the aerosol absorption over the site is generally due to mixed aerosols. (C) 2011 Elsevier Ltd. All rights reserved.

Energy-insensitive Guidance of Solid Motor Propelled Long Range Flight Vehicles Using MPSP and Dynamic Inversion

A energy-insensitive explicit guidance design is proposed in this paper by appending newlydeveloped nonlinear model predictive static programming technique with dynamic inversion, which render a closed form solution of the necessary guidance command update. The closed form nature of the proposed optimal guidance scheme suppressed the computational difficulties, and facilitate realtime solution. The guidance law is successfully verified in a solid motor propelled long range flight vehicle, for which developing an effective guidance law is more difficult as compared to a liquid engine propelled vehicle, mainly because of the absence of thrust cutoff facility. The scheme guides the vehicle appropriately so that it completes the mission within a tight error bound assuming that the starting point of the second stage to be a deterministic point beyond the atmosphere. The simulation results demonstrate its ability to intercept the target, even with an uncertainty of greater than 10% in the burnout time

CFD Based Design Optimizations of the Diffuser of a Gas Dynamically Driver Laser Cavity

Based on the an earlier CFD analysis of the performance of the gas-dynamically controlled laser cavity [1]it was found that there is possibility of optimizing the geometry of the diffuser that can bring about reductions in both size and cost of the system by examining the critical dimensional requirements of the diffuser. Consequently,an extensive CFD analysis has been carried out for a range of diffuser configurations by simulating the supersonic flow through the arrangement including the laser cavity driven by a bank of converging – diverging nozzles and the diffuser. The numerical investigations with 3D-RANS code are carried out to capture the flow patterns through diffusers past the cavity that has multiple supersonic jet interactions with shocks leading to complex flow pattern. Varying length of the diffuser plates is made to be the basic parameter of the study. The analysis reveals that the pressure recovery pattern during the flow through the diffuser from the simulation, being critical for the performance of the laser device shows its dependence on the diffuser length is weaker beyond a critical lower limit and this evaluation of this limit would provide a design guideline for a more efficient system configuration.The observation based on the parametric study shows that the pressure recovery transients in the near vicinity of the cavity is not affected for the reduction in the length of the diffuser plates up to its 10% of the initial size, indicating the design in the first configuration that was tested experimentally has a large factor of margin. The flow stability in the laser cavity is found to be unaffected since a strong and stable shock is located at the leading edge of the diffuser plates while the downstream shock and flow patterns are changed, as one would expect. Results of the study for the different lengths of diffusers in the range of 10% to its full length are presented, keeping the experimentally tested configuration used in the earlier study [1] as the reference length. The conclusions drawn from the analysis is found to be of significance since it provides new design considerations based on the understanding of the intricacies of the flow, allowing for a hardware optimization that can lead to substantial size reduction of the device with no loss of performance.

Efficient Algorithms for Computing All Low s-t Edge Connectivities and Related Problems

Given an undirected unweighted graph G = (V, E) and an integer k ≥ 1, we consider the problem of computing the edge connectivities of all those (s, t) vertex pairs, whose edge connectivity is at most k. We present an algorithm with expected running time Õ(m + nk3) for this problem, where |V| = n and |E| = m. Our output is a weighted tree T whose nodes are the sets V1, V2,..., V l of a partition of V, with the property that the edge connectivity in G between any two vertices s ε Vi and t ε Vj, for i ≠ j, is equal to the weight of the lightest edge on the path between Vi and Vj in T. Also, two vertices s and t belong to the same Vi for any i if and only if they have an edge connectivity greater than k. Currently, the best algorithm for this problem needs to compute all-pairs min-cuts in an O(nk) edge graph; this takes Õ(m + n5/2kmin{k1/2, n1/6}) time. Our algorithm is much faster for small values of k; in fact, it is faster whenever k is o(n5/6). Our algorithm yields the useful corollary that in Õ(m + nc3) time, where c is the size of the global min-cut, we can compute the edge connectivities of all those pairs of vertices whose edge connectivity is at most αc for some constant α. We also present an Õ(m + n) Monte Carlo algorithm for the approximate version of this problem. This algorithm is applicable to weighted graphs as well. Our algorithm, with some modifications, also solves another problem called the minimum T-cut problem. Given T ⊆ V of even cardinality, we present an Õ(m + nk3) algorithm to compute a minimum cut that splits T into two odd cardinality components, where k is the size of this cut.

A Hybrid Energy-insensitive Explicit Guidance Scheme for Long Range Flight Vehicles with Solid Motors

Combining the newly developed nonlinear model predictive static programming technique with null range direction concept, a novel explicit energy-insensitive guidance design method is presented in this paper for long range flight vehicles, which leads to a closed form solution of the necessary guidance command update. Owing to the closed form nature, it does not lead to computational difficulties and the proposed optimal guidance algorithm can be implemented online. The guidance law is verified in a solid motor propelled long range flight vehicle, for which coming up with an effective guidance law is more difficult as compared to a liquid engine propelled vehicle (mainly because of the absence of thrust cutoff facility). Assuming the starting point of the second stage to be a deterministic point beyond the atmosphere, the scheme guides the vehicle properly so that it completes the mission within a tight error bound. The simulation results demonstrate its ability to intercept the target, even with an uncertainty of greater than 10% in burnout time.