Acyclic Edge Coloring of Graphs with Maximum Degree 4

An acyclic edge coloring of a graph is a proper edge coloring such that there are no bichromatic cycles. The acyclic chromatic index of a graph is the minimum number k such that there is an acyclic edge coloring using k colors and is denoted by a'(G). It was conjectured by Alon, Sudakov, and Zaks that for any simple and finite graph G, a'(G) <= Delta+2, where Delta=Delta(G) denotes the maximum degree of G. We prove the conjecture for connected graphs with Delta(G)<= 4, with the additional restriction that m <= 2n-1, where n is the number of vertices and m is the number of edges in G. Note that for any graph G, m <= 2n, when Delta(G)<= 4. It follows that for any graph G if Delta(G)<= 4, then a'(G) <= 7.

Improvement On Brooks Chromatic Bound For A Class Of Graphs

Brooks' Theorem says that if for a graph G,Δ(G)=n, then G is n-colourable, unless (1) n=2 and G has an odd cycle as a component, or (2) n>2 and Kn+1 is a component of G. In this paper we prove that if a graph G has none of some three graphs (K1,3;K5−e and H) as an induced subgraph and if Δ(G)greater-or-equal, slanted6 and d(G)<Δ(G), then χ(G)<Δ(G). Also we give examples to show that the hypothesis Δ(G)greater-or-equal, slanted6 can not be non-trivially relaxed and the graph K5−e can not be removed from the hypothesis. Moreover, for a graph G with none of K1,3;K5−e and H as an induced subgraph, we verify Borodin and Kostochka's conjecture that if for a graph G,Δ(G)greater-or-equal, slanted9 and d(G)<Δ(G), then χ(G)<Δ(G).

Discussion of enthalpy, entropy and free energy of formation of GaN

Presented in this letter is a critical discussion of a recent paper on experimental investigation of the enthalpy, entropy and free energy of formation of gallium nitride (GaN) published in this journal [T.J. Peshek, J.C. Angus, K. Kash, J. Cryst. Growth 311 (2008) 185-189]. It is shown that the experimental technique employed detects neither the equilibrium partial pressure of N-2 corresponding to the equilibrium between Ga and GaN at fixed temperatures nor the equilibrium temperature at constant pressure of N-2. The results of Peshek et al. are discussed in the light of other information on the Gibbs energy of formation available in the literature. Entropy of GaN is derived from heat-capacity measurements. Based on a critical analysis of all thermodynamic information now available, a set of optimized parameters is identified and a table of thermodynamic data for GaN developed from 298.15 to 1400 K.

Embodied energy of service trading in Hong Kong

Purpose Energy is a resource of strategic importance for high density cities. International trade reshapes the urban economy and industrial structure of a city, which will indirectly affect energy use. As an international trade hub, Hong Kong relies on the import and export of services. Energy performance in the international trading of these services needs to be properly understood and assessed for Hong Kong’s urban renewal efforts. Design/methodology/approach This study evaluates Hong Kong’s embodied energy in service trades based on an input-output analysis. The three criteria used for assessment include trading areas, industry sector, and trade balance. Findings Analyzed by region, results show that Mainland China and the USA are the two largest sources of embodied energy in imports of services, while Mainland China and Japan are the two largest destinations of exports. In terms of net embodied energy transfer, Hong Kong mainly receives net energy import from Mainland China and the USA and supplies net energy export to Japan, the UK and Taiwan. Among industry sectors, Manufacturing services, Transport and Travel contribute most significantly to the embodied energy in Hong Kong’s imported services, while Transport and Travel contribute most to the energy embodied in exported services. Originality/value This study identifies the characteristics of energy consumption of service trading and establishes a feasible approach to analyze energy performance of service trade in energy-deficient Hong Kong for the first time. It provides necessary understanding and foundation for developing energy strategies in a service-based, high density urban economy.

Calculations of the free energy of interaction of the c-Fos−c-Jun coiled coil: Effects of the solvation model and the inclusion of polarization effects

The leucine zipper region of activator protein-1 (AP-1) comprises the c-Jun and c-Fos proteins and constitutes a well-known coiled coil protein−protein interaction motif. We have used molecular dynamics (MD) simulations in conjunction with the molecular mechanics/Poisson−Boltzmann generalized-Born surface area [MM/PB(GB)SA] methods to predict the free energy of interaction of these proteins. In particular, the influence of the choice of solvation model, protein force field, and water potential on the stability and dynamic properties of the c-Fos−c-Jun complex were investigated. Use of the AMBER polarizable force field ff02 in combination with the polarizable POL3 water potential was found to result in increased stability of the c-Fos−c-Jun complex. MM/PB(GB)SA calculations revealed that MD simulations using the POL3 water potential give the lowest predicted free energies of interaction compared to other nonpolarizable water potentials. In addition, the calculated absolute free energy of binding was predicted to be closest to the experimental value using the MM/GBSA method with independent MD simulation trajectories using the POL3 water potential and the polarizable ff02 force field, while all other binding affinities were overestimated.

Geometric Representation of Graphs in Low Dimension Using Axis Parallel Boxes

An axis-parallel k-dimensional box is a Cartesian product R-1 x R-2 x...x R-k where R-i (for 1 <= i <= k) is a closed interval of the form [a(i), b(i)] on the real line. For a graph G, its boxicity box(G) is the minimum dimension k, such that G is representable as the intersection graph of (axis-parallel) boxes in k-dimensional space. The concept of boxicity finds applications in various areas such as ecology, operations research etc. A number of NP-hard problems are either polynomial time solvable or have much better approximation ratio on low boxicity graphs. For example, the max-clique problem is polynomial time solvable on bounded boxicity graphs and the maximum independent set problem for boxicity d graphs, given a box representation, has a left perpendicular1 + 1/c log n right perpendicular(d-1) approximation ratio for any constant c >= 1 when d >= 2. In most cases, the first step usually is computing a low dimensional box representation of the given graph. Deciding whether the boxicity of a graph is at most 2 itself is NP-hard. We give an efficient randomized algorithm to construct a box representation of any graph G on n vertices in left perpendicular(Delta + 2) ln nright perpendicular dimensions, where Delta is the maximum degree of G. This algorithm implies that box(G) <= left perpendicular(Delta + 2) ln nright perpendicular for any graph G. Our bound is tight up to a factor of ln n. We also show that our randomized algorithm can be derandomized to get a polynomial time deterministic algorithm. Though our general upper bound is in terms of maximum degree Delta, we show that for almost all graphs on n vertices, their boxicity is O(d(av) ln n) where d(av) is the average degree.

A universal relation for the cohesive energy of nanoparticles

A universal relation between the cohesive energy and the particle size has been predicted based on the liquid-drop model. The universal relation is well supported by other theoretical models and the available experimental data. The universal relations for intermediate size range as well as for particles with very few atoms are discussed. A comparison of onset temperature of evaporation also establishes a universal relation.

Gibbs Energy of Formation of MnO: Measurement and Assessment

Based on the measurements of Alcock and Zador, Grundy et al. estimated an uncertainty of the order of +/- 5 kJ mol(-1) for the standard Gibbs energy of formation of MnO in a recent assessment. Since the evaluation of thermodynamic data for the higher oxides Mn3O4, Mn2O3, and MnO2 depends on values for MnO, a redetermination of its Gibbs energy of formation was undertaken in the temperature range from 875 to 1300 K using a solid-state electrochemical cell incorporating yttria-doped thoria (YDT) as the solid electrolyte and Fe + Fe1-delta O as the reference electrode. The cell can be presented as Pt, Mn + MnO/YDT/Fe + Fe1+delta O, Pt Since the metals Fe and Mn undergo phase transitions in the temperature range of measurement, the reversible emf of the cell is represented by the three linear segments. Combining the emf with the oxygen potential for the reference electrode, the standard Gibbs energy of formation of MnO from alpha-Mn and gaseous diatomic oxygen in the temperature range from 875 to 980 K is obtained as: Delta G(f)(o)/Jmol(-1)(+/- 250) = -385624 + 73.071T From 980 to 1300 K the Gibbs energy of formation of MnO from beta-Mn and oxygen gas is given by: Delta G(f)(o)/Jmol(-1)(+/- 250) = -387850 + 75.36T The new data are in excellent agreement with the earlier measurements of Alcock and Zador. Grundy et al. incorrectly analyzed the data of Alcock and Zador showing relatively large difference (+/- 5 kJ mol(-1)) in Gibbs energies of MnO from their two cells with Fe + Fe1-delta O and Ni + NiO as reference electrodes. Thermodynamic data for MnO is reassessed in the light of the new measurements. A table of refined thermodynamic data for MnO from 298.15 to 2000 K is presented.

Hadwiger Number and the Cartesian Product of Graphs

The Hadwiger number eta(G) of a graph G is the largest integer n for which the complete graph K-n on n vertices is a minor of G. Hadwiger conjectured that for every graph G, eta(G) >= chi(G), where chi(G) is the chromatic number of G. In this paper, we study the Hadwiger number of the Cartesian product G square H of graphs. As the main result of this paper, we prove that eta(G(1) square G(2)) >= h root 1 (1 - o(1)) for any two graphs G(1) and G(2) with eta(G(1)) = h and eta(G(2)) = l. We show that the above lower bound is asymptotically best possible when h >= l. This asymptotically settles a question of Z. Miller (1978). As consequences of our main result, we show the following: 1. Let G be a connected graph. Let G = G(1) square G(2) square ... square G(k) be the ( unique) prime factorization of G. Then G satisfies Hadwiger's conjecture if k >= 2 log log chi(G) + c', where c' is a constant. This improves the 2 log chi(G) + 3 bound in [2] 2. Let G(1) and G(2) be two graphs such that chi(G1) >= chi(G2) >= clog(1.5)(chi(G(1))), where c is a constant. Then G1 square G2 satisfies Hadwiger's conjecture. 3. Hadwiger's conjecture is true for G(d) (Cartesian product of G taken d times) for every graph G and every d >= 2. This settles a question by Chandran and Sivadasan [2]. ( They had shown that the Hadiwger's conjecture is true for G(d) if d >= 3).

On a Special Co-cycle Basis of Graphs

In this paper we consider the problems of computing a minimum co-cycle basis and a minimum weakly fundamental co-cycle basis of a directed graph G. A co-cycle in G corresponds to a vertex partition (S,V ∖ S) and a { − 1,0,1} edge incidence vector is associated with each co-cycle. The vector space over ℚ generated by these vectors is the co-cycle space of G. Alternately, the co-cycle space is the orthogonal complement of the cycle space of G. The minimum co-cycle basis problem asks for a set of co-cycles that span the co-cycle space of G and whose sum of weights is minimum. Weakly fundamental co-cycle bases are a special class of co-cycle bases, these form a natural superclass of strictly fundamental co-cycle bases and it is known that computing a minimum weight strictly fundamental co-cycle basis is NP-hard. We show that the co-cycle basis corresponding to the cuts of a Gomory-Hu tree of the underlying undirected graph of G is a minimum co-cycle basis of G and it is also weakly fundamental.

New approximation algorithms for minimum cycle bases of graphs

We consider the problem of computing an approximate minimum cycle basis of an undirected edge-weighted graph G with m edges and n vertices; the extension to directed graphs is also discussed. In this problem, a {0,1} incidence vector is associated with each cycle and the vector space over F-2 generated by these vectors is the cycle space of G. A set of cycles is called a cycle basis of G if it forms a basis for its cycle space. A cycle basis where the sum of the weights of the cycles is minimum is called a minimum cycle basis of G. Cycle bases of low weight are useful in a number of contexts, e.g. the analysis of electrical networks, structural engineering, chemistry, and surface reconstruction. We present two new algorithms to compute an approximate minimum cycle basis. For any integer k >= 1, we give (2k - 1)-approximation algorithms with expected running time 0(kmn(1+2/k) + mn((1+1/k)(omega-1))) and deterministic running time 0(n(3+2/k)), respectively. Here omega is the best exponent of matrix multiplication. It is presently known that omega < 2.376. Both algorithms are o(m(omega)) for dense graphs. This is the first time that any algorithm which computes sparse cycle bases with a guarantee drops below the Theta(m(omega)) bound. We also present a 2-approximation algorithm with O(m(omega) root n log n) expected running time, a linear time 2-approximation algorithm for planar graphs and an O(n(3)) time 2.42-approximation algorithm for the complete Euclidean graph in the plane.

Fracture process zone size and true fracture energy of concrete using acoustic emission

Acoustic emission (AE) energy, instead of amplitude, associated with each of the event is used to estimate the fracture process zone (FPZ) size. A steep increase in the cumulative AE energy of the events with respect to time is correlated with the formation of FPZ. Based on the AE energy released during these events and the locations of the events, FPZ size is obtained. The size-independent fracture energy is computed using the expressions given in the boundary effect model by least squares method since over-determined system of equations are obtained when data from several specimens are used. Instead of least squares method a different method is suggested in which the transition ligament length, measured from the plot of histograms of AE events plotted over the un-cracked ligament, is used directly to obtain size-independent fracture energy. The fracture energy thus calculated seems to be size-independent.

Free energy of mixing of divalent basic oxides with silica

An expression derived for the free energy of mixing of a divalent basic oxide (MO) with SiO2 based on a model of silicate structure, takes into account the distribution of O2- (from MO) into the silica network, the mixing of silicate ions with O2- and the enthalpy of mixing. The resulting expression is ΔGmix=RT{N11n (2N1-N)2/4N1(1-N)+N21n N 2-N/1-N}, where N={(β+N1)-√(β+N 1)2-8βN1N2}/2β β=characteristic constant for the system N1=mol fraction of silica N2=mol fraction of MO. For the proper choice of β, calculated values of the activity of MO for the system PbO-SiO2, MnO-SiO2, FeO-SiO2 and CaO-SiO2 are in good agreement with experiment. The model predicts that the activity of the basic oxide decreases with increase in temperature.

Use of metastable equilibria for determination of Gibbs energy of solids

Attempts are made to measure activities of both components of a binary alloy (A�B) at 650 K using a solid-state galvanic cell incorporating a new composite solid electrolyte. Since the ionic conductivity of the composite solid electrolyte is three orders of magnitude higher than that of pure CaF2, the cell can be operated at lower temperatures. The alloy phase is equilibrated in separate experiments with flourides of each component and fluorine potential is measured. The mixture of the alloy (A�B) and the fluoride of the more reactive component (BF2) is stable, while (A�B) + AF2 mixture is metastable, Factors governing the possible use of metastable equilibria have been elucidated in this study. In the Co�Ni system, where the difference in Gibbs energies of formation of the fluorides is 21.4 kJ/mol, emf of the cell with metastable phases at the electrode is constant for periods ranging from 90 to 160 ks depending on alloy composition. Subsequently, the emf decreases because of the onset of the displacement reaction. In the Ni�Mn system, measurement of the activity of Ni using metastable equilibria is not fully successful at 650 K because of the large driving force for the displacement reaction (208.8 kJ/mol). Critical factors in the application of metastable equilibria are the driving force for displacement reaction and diffusion coefficients in both the alloy and fluoride solid solution.