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]

Temperature Dependence of Mechanical Properties in Molecular Crystals

Quantitative evaluation of the mechanical behavior of molecular materials by a nanoindentation technique has gained prominence recently. However, all the reported data have been on room-temperature properties despite many interesting phenomena observed in them with variations in temperature. In this paper, we report the results of nanoindentation experiments conducted as a function of temperature, T, between 283 and 343 K, on the major faces of three organic crystals: saccharin, sulfathiazole (form 2), and L-alanine, which are distinct in terms of the number and strength of intermolecular interactions in them. Results show that elastic modulus, E, and hardness, H, decrease markedly with increasing T. While E decreases linearly with T, the variations in H with T are not so, and were observed to drop by similar to 50% over the range of T investigated. The slope of the linear fits to E vs T for the organic crystals was found to be around 1, which is considerably higher than the values of 0.3-0.5 reported in the literature for metallic, ionic, and covalently bonded crystalline materials. Possible implications of the observed remarkable changes in H for pharmaceutical manufacturing are highlighted.

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.

Dependence of ``critical cloud fraction' on aerosol composition

Recent studies, over regions influenced by biomass burning aerosol, have shown that it is possible to define a critical cloud fraction' (CCF) at which the aerosol direct radiative forcing switch from a cooling to a warming effect. Using 4 years of multi-satellite data analysis, we show that CCF varies with aerosol composition and changed from 0.28 to 0.13 from postmonsoon to winter as a result of shift from less absorbing to moderately absorbing aerosol. Our results indicate that we can estimate aerosol absorption from space using independently measured top of the atmosphere (TOA) fluxes Cloud Aerosol Lidar with Orthogonal Polarization-Moderate resolution Imaging Spectroradiometer-Clouds and the Earth's Radiant Energy System (CALIPSO-MODIS-CERES)] combined algorithms for example.

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.

Anisotropy in the mechanical properties of organic crystals: temperature dependence

The nanoindentation technique has recently been utilized for quantitative evaluation of the mechanical properties of molecular materials successfully, including their temperature (T) dependence. In this paper, we examine how the mechanical anisotropy varies with T in saccharin and L-alanine single crystals. Our results show that elastic modulus (E) decreases linearly in all the cases examined, with the T-dependence of E being anisotropic. Correspondence between directional dependence of the slopes of the E vs. T plots and the linear thermal expansion coefficients was found. The T-dependence of hardness (H), on the other hand, was found to be nonlinear and significant when (100) of saccharin and (001) of L-alanine are indented. While the anisotropies in E and H of saccharin and E of L-alanine enhance with T, the anisotropy in H of L-alanine was found to reduce with T. Possible mechanistic origins of these variations are discussed.

Ultra-sensitive pressure dependence of bandgap of rutile-GeO2 revealed by many body perturbation theory

The reported values of bandgap of rutile GeO2 calculated by the standard density functional theory within local-density approximation (LDA)/generalized gradient approximation (GGA) show a wide variation (similar to 2 eV), whose origin remains unresolved. Here, we investigate the reasons for this variation by studying the electronic structure of rutile-GeO2 using many-body perturbation theory within the GW framework. The bandgap as well as valence bandwidth at Gamma-point of rutile phase shows a strong dependence on volume change, which is independent of bandgap underestimation problem of LDA/GGA. This strong dependence originates from a change in hybridization among O-p and Ge-(s and p) orbitals. Furthermore, the parabolic nature of first conduction band along X-Gamma-M direction changes towards a linear dispersion with volume expansion. (C) 2015 AIP Publishing LLC.

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.

Dependence of shear yield strain and shear transformation zone on the glass transition temperature in thin film metallic glasses

The dependence of shear yield strain, the activation energy and volume of shear transformation zone on the glass transition temperature was investigated through the analysis of statistical distributions of the first pop-in events during spherical indentation of four different thin film metallic glasses. Only the Cu-Zr metallic glass exhibits a bimodal distribution of the first pop-in loads, whereas W-Ru-B, Zr-Cu-Ni-Al and La-Co-Al metallic glasses show an unimodal distribution. Results show that shear yield strain and activation energy of shear transformation zone decrease whereas the volume of shear transformation zone increases with increasing homologous temperature, indicating that it is the activation energy rather than the volume of shear transformation zone that controls shear yield strain. (C) 2015 Elsevier B.V. All rights reserved.

Role of different scattering mechanisms on the temperature dependence of transport in graphene

Detailed experimental and theoretical studies of the temperature dependence of the effect of different scattering mechanisms on electrical transport properties of graphene devices are presented. We find that for high mobility devices the transport properties are mainly governed by completely screened short range impurity scattering. On the other hand, for the low mobility devices transport properties are determined by both types of scattering potentials - long range due to ionized impurities and short range due to completely screened charged impurities. The results could be explained in the framework of Boltzmann transport equations involving the two independent scattering mechanisms.

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.

Electric field and temperature dependence of the local structural disorder in the lead-free ferroelectric Na0.5Bi0.5TiO3: An EXAFS study

The complex nature of the structural disorder in the lead-free ferroelectric Na1/2Bi1/2TiO3 has a profound impact on the perceived global structure and polar properties. In this paper, we have investigated the effect of electric field and temperature on the local structure around theBi and Ti atoms using extended x-ray absorption fine structure. Detailed analysis revealed that poling brings about a noticeable change in the bond distances associated with the Bi-coordination sphere, whereas the Ti coordination remains unaffected. We also observed discontinuity in the Bi-O bond lengths across the depolarization temperature of the poled specimen. These results establish that the disappearance of the monoclinic-like (Cc) global distortion, along with the drastic suppression of the short-ranged in-phase octahedral tilt after poling B. N. Rao et al., Phys. Rev. B 88, 224103 (2013)] is a result of the readjustment of theA-O bonds by the electric field, so as to be in conformity with the rhombohedral R3c structure.