Boxicity of Circular Arc Graphs

A k-dimensional box is a Cartesian product R(1)x...xR(k) where each R(i) is a closed interval on the real line. The boxicity of a graph G, denoted as box(G), is the minimum integer k such that G can be represented as the intersection graph of a collection of k-dimensional boxes. That is, two vertices are adjacent if and only if their corresponding boxes intersect. A circular arc graph is a graph that can be represented as the intersection graph of arcs on a circle. We show that if G is a circular arc graph which admits a circular arc representation in which no arc has length at least pi(alpha-1/alpha) for some alpha is an element of N(>= 2), then box(G) <= alpha (Here the arcs are considered with respect to a unit circle). From this result we show that if G has maximum degree Delta < [n(alpha-1)/2 alpha] for some alpha is an element of N(>= 2), then box(G) <= alpha. We also demonstrate a graph having box(G) > alpha but with Delta = n (alpha-1)/2 alpha + n/2 alpha(alpha+1) + (alpha+2). For a proper circular arc graph G, we show that if Delta < [n(alpha-1)/alpha] for some alpha is an element of N(>= 2), then box(G) <= alpha. Let r be the cardinality of the minimum overlap set, i.e. the minimum number of arcs passing through any point on the circle, with respect to some circular arc representation of G. We show that for any circular arc graph G, box(G) <= r + 1 and this bound is tight. We show that if G admits a circular arc representation in which no family of k <= 3 arcs covers the circle, then box(G) <= 3 and if G admits a circular arc representation in which no family of k <= 4 arcs covers the circle, then box(G) <= 2. We also show that both these bounds are tight.

Role of electrolyte additives on in-vitro electrochemical behavior of micro arc oxidized titania films on Cp Ti

The present work is aimed at studying the influence of electrolyte chemistry on the voltage-time (V-T) response characteristics, phase structure, surface morphology, film growth rate and corrosion properties of titania films fabricated by micro arc oxidation (MAO) on Cp Ti. The titania films were developed with a sodium phosphate based reference electrolyte comprising the additives such as sodium carbonate (Na2CO3), sodium nitrite (NaNO2) and urea (CO(NH2)(2)). The phase composition, surface morphology, elemental composition and thickness of the films were assessed by X-ray diffraction (XRD), scanning electron microscopy (SEM) and energy dispersive spectroscopy (EDS) techniques. The corrosion characteristics of the fabricated films were studied under Kokubo simulated body fluid (SBF) condition by potentiodynamic polarization, long term potential and linear polarization resistance (LPR) measurements and electrochemical impedance spectroscopy (EIS) methods. In addition, the corrosion characteristics of the grown films were analyzed by EIS curve fitting and equivalent circuit modeling. Salt spray test (SST) as per ASTM B 117 standard was also conducted to verify the corrosion resistance of the grown films. The XRD results showed that the titania films were composed of both anatase and rutile phases at different proportions. Besides, the films grown in carbonate and nitrite containing electrolyte systems showed an enhanced growth of their rutile phase in the 1 0 1] direction which could be attributed to the modifications introduced in the growth process by the abundant oxygen available during the process. The SEM-EDX and elemental mapping results showed that the respective electrolyte borne elements were incorporated and distributed uniformly in all the films. Among all the grown films under study, the film developed in carbonate containing electrolyte system exhibited considerably improved corrosion resistance due to suitable modifications in its structural and morphological characteristics. The rate of anatase to rutile phase transformation and the rutile growth direction were strongly influenced by the abundant oxidizing species available during the film growth process. (C) 2012 Elsevier B. V. All rights reserved.

A constant factor approximation algorithm for boxicity of circular arc graphs

Boxicity of a graph G(V, E) is the minimum integer k such that G can be represented as the intersection graph of k-dimensional axis parallel boxes in Rk. Equivalently, it is the minimum number of interval graphs on the vertex set V such that the intersection of their edge sets is E. It is known that boxicity cannot be approximated even for graph classes like bipartite, co-bipartite and split graphs below O(n0.5-ε)-factor, for any ε > 0 in polynomial time unless NP = ZPP. Till date, there is no well known graph class of unbounded boxicity for which even an nε-factor approximation algorithm for computing boxicity is known, for any ε < 1. In this paper, we study the boxicity problem on Circular Arc graphs - intersection graphs of arcs of a circle. We give a (2+ 1/k)-factor polynomial time approximation algorithm for computing the boxicity of any circular arc graph along with a corresponding box representation, where k ≥ 1 is its boxicity. For Normal Circular Arc(NCA) graphs, with an NCA model given, this can be improved to an additive 2-factor approximation algorithm. The time complexity of the algorithms to approximately compute the boxicity is O(mn+n2) in both these cases and in O(mn+kn2) which is at most O(n3) time we also get their corresponding box representations, where n is the number of vertices of the graph and m is its number of edges. The additive 2-factor algorithm directly works for any Proper Circular Arc graph, since computing an NCA model for it can be done in polynomial time.

Fabrication and characterization of micro-arc oxidized fluoride containing titania films on Cp Ti

The present study is focussed at establishing an appropriate electrolyte system for developing electrochemically stable and fluorine (F) containing titania (F-TiO2) films on Cp Ti by micro-arc oxidation (MAO) technique. To fabricate the F-TiO2 films on Cp Ti, different electrolyte solutions of chosen concentrations of tri-sodium orthophosphate (TSOP, Na3PO4 center dot I2H2O), potassium hydroxide (KOH) and various F-containing compounds such as ammonium fluoride (NH4F), potassium fluoride (KF), sodium fluoride (NaF) and potassium fluorotitanate (K2TiF6) are employed. The structural and morphological characteristics, thickness and elemental composition of the developed films have been assessed by X-ray diffraction (XRD), scanning electron microscopy (SEM) and energy dispersive spectroscopy (EDS) techniques. The in-vitro electrochemical corrosion behavior of the films was studied under Kokubo simulated body fluid (SBF) environment by potentiodynamic polarization, long term potential measurement and electrochemical impedance spectroscopy (EIS) methods. The XRD and SEM-EDS results show that the rutile content in the films vary in the range of 15-37 wt% and the F and P contents in the films is found to be in the range of 2-3 at% and 2.9-4.7 at% respectively, suggesting that the anatase to rutile phase transformation and the incorporation of F and P into the films are significantly controlled by the respective electrolyte solution. The SEM elemental mapping results show that the electrolyte borne F and P elements are incorporated and distributed uniformly in all the films. Among all the films under study, the film developed with 5 g TSOP+2 g KOH+3 g K2TiF6 electrolyte system exhibits considerably improved in-vitro corrosion resistance and therefore best suited for biomedical applications. (C) 2012 Elsevier Ltd and Techna Group S.r.l. All rights reserved.

Chromite-silicate chemistry of the Neoarchean Sittampundi Complex, southern India: Implications for subduction-related arc magmatism

The Neoarchean layered anorthositic complex at Sittampundi in southern India is known for its chromitite layers that are mostly associated with anorthosite (An(90-100)). The chromitites contain FeAl-rich chromites concentrated in layers between amphibole-rich layers with a dominant mineralogy of amphibole-spinel-plagiocase+/-sapphirine. The chromite-rich layers contain only amphibole and plagioclase. Mineral compositions illustrated by X-ray composition maps and profiles show subtle chemical differences. The chrome spinels are of refractory grade with Cr2O3 and Al2O3 contents varying between 34-40 wt.% and 23-28 wt.%. The chromite compositions are noticeably different from those in layered igneous intrusions of the Bushveld-Stillwater type. The existence of original highly calcic plagioclase, FeAl-rich chromite, and magmatic amphibole is consistent with derivation from a parental magma of hydrous tholeiitic composition that was most likely generated in a supra-subduction zone arc setting. In terms of mineralogy and field relations, the Sittampundi chromitites are remarkably similar to anorthosite-hosted chromitites in the Neoarchean Fiskensset anorthositic complex, Greenland. We propose that the Sittampundi chromitites formed by partial melting of unusually aluminous harzburgite in a hydrated mantle wedge above a subduction zone. This melting process produced hydrous, aluminous basalt, which fractionated at depth to give rise to a variety of high-alumina basalt compositions from which the anorthositic complex with its cumulate chromite-rich and amphibole-rich layers formed within the magma chamber of a supra-subduction zone arc. (C) 2011 Elsevier B.V. All rights reserved.

Role of electrolyte chemistry on electronic and in vitro electrochemical properties of micro-arc oxidized titania films on Cp Ti

The primary objective of the present work was to study the electronic and in vitro electrochemical properties of micro-arc oxidized titania films on Cp Ti, fabricated independently in various electrolyte solutions consisting of anions such as phosphate (PO43-), borate (B4O72-), citrate (C6H5O73-) and silicate (SiO32-). Further the role of anions on the structural, morphological and compositional properties of the fabricated films was studied. All the titania films were developed by micro-arc oxidation (MAO) technique for a fixed treatment time of 8 min under constant current mode. The surface morphology, elemental distribution, composition and structural characteristics of the films were assessed by scanning electron microscope (SEM) equipped with energy dispersive spectroscopy (EDS) and X-ray diffraction (XRD) techniques. The thermodynamic and kinetic corrosion properties of the films were studied under simulated body fluid (SBF) conditions (pH 7.4 and 37 degrees C) by conducting chronopotentiometric and potentiodynamic polarization tests. Electrochemical impedance spectroscopy (EIS) coupled with equivalent circuit modelling was carried out to analyse the frequency response and Mott-Schottky analysis was performed to study the semiconducting (electronic) properties of the films. Salt spray fog accelerated corrosion test was conducted for 168h as per ASTM B117 standard to corroborate the corrosion and semiconducting properties of the samples based on the visual examination. The XRD results showed that the transformation from the metastable anatase phase to the thermodynamically stable rutile phase and the crystalline growth of the respective phases were strongly influenced by the addition of anions. The SEM-EDS results demonstrated that the phosphorous (P) content in the films varied from 2.4 at% to 5.0 at% indicating that the amount of P in the films could be modified by adding an appropriate electrolyte additive. The electrochemical corrosion test results showed that the film fabricated in citrate (C6H5O73-) containing electrolyte is thermodynamically and kinetically more stable compared to that of all the others. The results of the Mott-Schottky analysis indicated that all the fabricated films showed an n-type semiconducting behaviour and the film developed in citrate (C6H5O73-) containing electrolyte exhibited the lowest donor concentration and the most negative flat band potential that contributed to its highest corrosion resistance in SBF solution. The results of the salt spray accelerated corrosion tests were in agreement with those obtained from the electrochemical and Mott-Schottky analysis.

A constant factor approximation algorithm for boxicity of circular arc graphs

The boxicity (resp. cubicity) of a graph G(V, E) is the minimum integer k such that G can be represented as the intersection graph of axis parallel boxes (resp. cubes) in R-k. Equivalently, it is the minimum number of interval graphs (resp. unit interval graphs) on the vertex set V, such that the intersection of their edge sets is E. The problem of computing boxicity (resp. cubicity) is known to be inapproximable, even for restricted graph classes like bipartite, co-bipartite and split graphs, within an O(n(1-epsilon))-factor for any epsilon > 0 in polynomial time, unless NP = ZPP. For any well known graph class of unbounded boxicity, there is no known approximation algorithm that gives n(1-epsilon)-factor approximation algorithm for computing boxicity in polynomial time, for any epsilon > 0. In this paper, we consider the problem of approximating the boxicity (cubicity) of circular arc graphs intersection graphs of arcs of a circle. Circular arc graphs are known to have unbounded boxicity, which could be as large as Omega(n). We give a (2 + 1/k) -factor (resp. (2 + log n]/k)-factor) polynomial time approximation algorithm for computing the boxicity (resp. cubicity) of any circular arc graph, where k >= 1 is the value of the optimum solution. For normal circular arc (NCA) graphs, with an NCA model given, this can be improved to an additive two approximation algorithm. The time complexity of the algorithms to approximately compute the boxicity (resp. cubicity) is O(mn + n(2)) in both these cases, and in O(mn + kn(2)) = O(n(3)) time we also get their corresponding box (resp. cube) representations, where n is the number of vertices of the graph and m is its number of edges. Our additive two approximation algorithm directly works for any proper circular arc graph, since their NCA models can be computed in polynomial time. (C) 2014 Elsevier B.V. All rights reserved.