Boxicity of line graphs

The boxicity of a graph H, denoted by box(H), is the minimum integer k such that H is an intersection graph of axis-parallel k-dimensional boxes in R(k). In this paper we show that for a line graph G of a multigraph, box(G) <= 2 Delta (G)(inverted right perpendicularlog(2) log(2) Delta(G)inverted left perpendicular + 3) + 1, where Delta(G) denotes the maximum degree of G. Since G is a line graph, Delta(G) <= 2(chi (G) - 1), where chi (G) denotes the chromatic number of G, and therefore, box(G) = 0(chi (G) log(2) log(2) (chi (G))). For the d-dimensional hypercube Q(d), we prove that box(Q(d)) >= 1/2 (inverted right perpendicularlog(2) log(2) dinverted left perpendicular + 1). The question of finding a nontrivial lower bound for box(Q(d)) was left open by Chandran and Sivadasan in [L. Sunil Chandran, Naveen Sivadasan, The cubicity of Hypercube Graphs. Discrete Mathematics 308 (23) (2008) 5795-5800]. The above results are consequences of bounds that we obtain for the boxicity of a fully subdivided graph (a graph that can be obtained by subdividing every edge of a graph exactly once). (C) 2011 Elsevier B.V. All rights reserved.

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.

Distinct Roles of FANCO/RAD51C Protein in DNA Damage Signaling and Repair Implications for Fanconi Anemia and Breast Cancer Susceptibility

RAD51C, a RAD51 paralog, has been implicated in homologous recombination (HR), and germ line mutations in RAD51C are known to cause Fanconi anemia (FA)-like disorder and breast and ovarian cancers. The role of RAD51C in the FA pathway of DNA interstrand cross-link (ICL) repair and as a tumor suppressor is obscure. Here, we report that RAD51C deficiency leads to ICL sensitivity, chromatid-type errors, and G(2)/M accumulation, which are hallmarks of the FA phenotype. We find that RAD51C is dispensable for ICL unhooking and FANCD2 monoubiquitination but is essential for HR, confirming the downstream role of RAD51C in ICL repair. Furthermore, we demonstrate that RAD51C plays a vital role in the HR-mediated repair of DNA lesions associated with replication. Finally, we show that RAD51C participates in ICL and double strand break-induced DNA damage signaling and controls intra-S-phase checkpoint through CHK2 activation. Our analyses with pathological mutants of RAD51C that were identified in FA and breast and ovarian cancers reveal that RAD51C regulates HR and DNA damage signaling distinctly. Together, these results unravel the critical role of RAD51C in the FA pathway of ICL repair and as a tumor suppressor.

Rainbow Connection Number and Connectivity

The rainbow connection number, rc(G), of a connected graph G is the minimum number of colors needed to color its edges, so that every pair of vertices is connected by at least one path in which no two edges are colored the same. Our main result is that rc(G) <= inverted right perpendicularn/2inverted left perpendicular for any 2-connected graph with at least three vertices. We conjecture that rc(G) <= n/kappa + C for a kappa-connected graph G of order n, where C is a constant, and prove the conjecture for certain classes of graphs. We also prove that rc(G) < (2 + epsilon)n/kappa + 23/epsilon(2) for any epsilon > 0.

Boxicity and Poset Dimension

Let G be a simple, undirected, finite graph with vertex set V (G) and edge set E(G). A k-dimensional box is a Cartesian product of closed intervals [a(1), b(1)] x [a(2), b(2)] x ... x [a(k), b(k)]. The boxicity of G, box(G), is the minimum integer k such that G can be represented as the intersection graph of k-dimensional boxes; i.e., each vertex is mapped to a k-dimensional box and two vertices are adjacent in G if and only if their corresponding boxes intersect. Let P = (S, P) be a poset, where S is the ground set and P is a reflexive, antisymmetric and transitive binary relation on S. The dimension of P, dim(P), is the minimum integer t such that P can be expressed as the intersection of t total orders. Let G(P) be the underlying comparability graph of P; i.e., S is the vertex set and two vertices are adjacent if and only if they are comparable in P. It is a well-known fact that posets with the same underlying comparability graph have the same dimension. The first result of this paper links the dimension of a poset to the boxicity of its underlying comparability graph. In particular, we show that for any poset P, box(G(P))/(chi(G(P)) - 1) <= dim(P) <= 2box(G(P)), where chi(G(P)) is the chromatic number of G(P) and chi(G(P)) not equal 1. It immediately follows that if P is a height-2 poset, then box(G(P)) <= dim(P) <= 2box(G(P)) since the underlying comparability graph of a height-2 poset is a bipartite graph. The second result of the paper relates the boxicity of a graph G with a natural partial order associated with the extended double cover of G, denoted as G(c): Note that G(c) is a bipartite graph with partite sets A and B which are copies of V (G) such that, corresponding to every u is an element of V (G), there are two vertices u(A) is an element of A and u(B) is an element of B and {u(A), v(B)} is an edge in G(c) if and only if either u = v or u is adjacent to v in G. Let P(c) be the natural height-2 poset associated with G(c) by making A the set of minimal elements and B the set of maximal elements. We show that box(G)/2 <= dim(P(c)) <= 2box(G) + 4. These results have some immediate and significant consequences. The upper bound dim(P) <= 2box(G(P)) allows us to derive hitherto unknown upper bounds for poset dimension such as dim(P) = 2 tree width (G(P)) + 4, since boxicity of any graph is known to be at most its tree width + 2. In the other direction, using the already known bounds for partial order dimension we get the following: (1) The boxicity of any graph with maximum degree Delta is O(Delta log(2) Delta), which is an improvement over the best-known upper bound of Delta(2) + 2. (2) There exist graphs with boxicity Omega(Delta log Delta). This disproves a conjecture that the boxicity of a graph is O(Delta). (3) There exists no polynomial-time algorithm to approximate the boxicity of a bipartite graph on n vertices with a factor of O(n(0.5-is an element of)) for any is an element of > 0 unless NP = ZPP.

Rainbow connection number and connected dominating sets

The rainbow connection number of a connected graph is the minimum number of colors needed to color its edges, so that every pair of its vertices is connected by at least one path in which no two edges are colored the same. In this article we show that for every connected graph on n vertices with minimum degree delta, the rainbow connection number is upper bounded by 3n/(delta + 1) + 3. This solves an open problem from Schiermeyer (Combinatorial Algorithms, Springer, Berlin/Hiedelberg, 2009, pp. 432437), improving the previously best known bound of 20n/delta (J Graph Theory 63 (2010), 185191). This bound is tight up to additive factors by a construction mentioned in Caro et al. (Electr J Combin 15(R57) (2008), 1). As an intermediate step we obtain an upper bound of 3n/(delta + 1) - 2 on the size of a connected two-step dominating set in a connected graph of order n and minimum degree d. This bound is tight up to an additive constant of 2. This result may be of independent interest. We also show that for every connected graph G with minimum degree at least 2, the rainbow connection number, rc(G), is upper bounded by Gc(G) + 2, where Gc(G) is the connected domination number of G. Bounds of the form diameter(G)?rc(G)?diameter(G) + c, 1?c?4, for many special graph classes follow as easy corollaries from this result. This includes interval graphs, asteroidal triple-free graphs, circular arc graphs, threshold graphs, and chain graphs all with minimum degree delta at least 2 and connected. We also show that every bridge-less chordal graph G has rc(G)?3.radius(G). In most of these cases, we also demonstrate the tightness of the bounds.

Structural characterization, EPR and thermoluminescence properties of Cd-1 (-) xNixSiO3 nanocrystalline phosphors

Cd-1 - xNixSiO3 (x = 1-7 mol%) nanophosphors have been prepared for the first time by the combustion method using oxylyldihydrizide as a fuel. Powder X-ray diffraction results confirm the formation of monoclinic phase. Scanning electron micrographs show that Ni2+ influences the porosity of samples. The optical energy gap is widened with increase of Ni2+ ion dopant. The electron paramagnetic resonance spectrum of Ni2+ ions in CdSiO3 exhibits a symmetric absorption at g = 2.343 and the site symmetry around Ni2+ ions is predominantly octahedral. The number of spins participating in resonance (N) and the paramagnetic susceptibility (chi) has been evaluated. The thermoluminescence intensity is found to increase up to similar to 20 min ultra-violet exposure and thereafter, decrease with further increase of ultra-violet dose. The kinetic parameters such as activation energy (E), frequency factor (s)and order of kinetics was estimated using glow peak shape method and the results are discussed. (c) 2012 Elsevier Ltd. All rights reserved.

Acyclic Edge Coloring of Triangle-Free Planar Graphs

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 (and much earlier by Fiamcik) that a'(G) ? ? + 2, where ? = ?(G) denotes the maximum degree of the graph. If every induced subgraph H of G satisfies the condition |E(H)| ? 2|V(H)|-1, we say that the graph G satisfies Property A. In this article, we prove that if G satisfies Property A, then a'(G) ? ? + 3. Triangle-free planar graphs satisfy Property A. We infer that a'(G) ? ? + 3, if G is a triangle-free planar graph. Another class of graph which satisfies Property A is 2-fold graphs (union of two forests). (C) 2011 Wiley Periodicals, Inc. J Graph Theory

Rainbow connectivity: hardness and tractability

A path in an edge colored graph is said to be a rainbow path if no two edges on the path have the same color. An edge colored graph is (strongly) rainbow connected if there exists a (geodesic) rainbow path between every pair of vertices. The (strong) rainbow connectivity of a graph G, denoted by (src(G), respectively) rc(G) is the smallest number of colors required to edge color the graph such that G is (strongly) rainbow connected. In this paper we study the rainbow connectivity problem and the strong rainbow connectivity problem from a computational point of view. Our main results can be summarised as below: 1) For every fixed k >= 3, it is NP-Complete to decide whether src(G) <= k even when the graph G is bipartite. 2) For every fixed odd k >= 3, it is NP-Complete to decide whether rc(G) <= k. This resolves one of the open problems posed by Chakraborty et al. (J. Comb. Opt., 2011) where they prove the hardness for the even case. 3) The following problem is fixed parameter tractable: Given a graph G, determine the maximum number of pairs of vertices that can be rainbow connected using two colors. 4) For a directed graph G, it is NP-Complete to decide whether rc(G) <= 2.

Sharp raman anomalies and broken adiabaticity at a pressure induced transition from band to topological insulator in Sb2Se3

The nontrivial electronic topology of a topological insulator is thus far known to display signatures in a robust metallic state at the surface. Here, we establish vibrational anomalies in Raman spectra of the bulk that signify changes in electronic topology: an E-g(2) phonon softens unusually and its linewidth exhibits an asymmetric peak at the pressure induced electronic topological transition (ETT) in Sb2Se3 crystal. Our first-principles calculations confirm the electronic transition from band to topological insulating state with reversal of parity of electronic bands passing through a metallic state at the ETT, but do not capture the phonon anomalies which involve breakdown of adiabatic approximation due to strongly coupled dynamics of phonons and electrons. Treating this within a four-band model of topological insulators, we elucidate how nonadiabatic renormalization of phonons constitutes readily measurable bulk signatures of an ETT, which will facilitate efforts to develop topological insulators by modifying a band insulator. DOI: 10.1103/PhysRevLett.110.107401

ATM- and ATR-mediated phosphorylation of XRCC3 regulates DNA double-strand break-induced checkpoint activation and repair

The RAD51 paralogs XRCC3 and RAD51C have been implicated in homologous recombination (HR) and DNA damage responses. However, the molecular mechanism(s) by which these paralogs regulate HR and DNA damage signaling remains obscure. Here, we show that an SQ motif serine 225 in XRCC3 is phosphorylated by ATR kinase in an ATM signaling pathway. We find that RAD51C but not XRCC2 is essential for XRCC3 phosphorylation, and this modification follows end resection and is specific to S and G(2) phases. XRCC3 phosphorylation is required for chromatin loading of RAD51 and HR-mediated repair of double-strand breaks (DSBs). Notably, in response to DSBs, XRCC3 participates in the intra-S-phase checkpoint following its phosphorylation and in the G(2)/M checkpoint independently of its phosphorylation. Strikingly, we find that XRCC3 distinctly regulates recovery of stalled and collapsed replication forks such that phosphorylation is required for the HR-mediated recovery of collapsed replication forks but is dispensable for the restart of stalled replication forks. Together, these findings suggest that XRCC3 is a new player in the ATM/ATR-induced DNA damage responses to control checkpoint and HR-mediated repair.

Synthesis, characterization, EPR and thermoluminescence properties of CaTiO3 nanophosphor

Calcium titanate (CaTiO3) nanophosphors were synthesized by three different routes namely solution combustion (SC), modified solid-state reaction (MSS) and solid-state (SS) methods. Rietveld refinement studies revealed the presence of an orthorhombic structure with traces of CaCO3. The crystallite sizes were found to be in the 43-45 nm range. TEM studies also confirm the nano size with well crystalline nature. EPR spectrum for SS method exhibits a broad resonance signal at g = 2.027 is attributed to TiO6](9-) center, whereas in MSS sample the resonance signals are attributed to surface electron and hole trapping sites. The TL behavior has been investigated for the first time using gamma-irradiation. TL glow peak at 169 degrees C were recorded in CaTiO3 prepared by SC, MSS and SS methods. The trapping parameters such as activation energy (E) and order of kinetics (b) were estimated using peak shape method and results are discussed in detail. (C) 2013 Elsevier Ltd. All rights reserved.

Electron paramagnetic resonance, magnetic and electrical properties of CoFe2O4 nanoparticles

CoFe2O4 nanoparticles were prepared by solution combustion method. The nanoparticle are characterized by powder X-ray diffraction (PXRD), Fourier transform infrared spectroscopy and scanning electron microscopy (SEM). PXRD reveals single phase, cubic spinel structure with Fd (3) over barm (227) space group. SEM micrograph shows the particles are agglomerated and porous in nature. Electron paramagnetic resonance spectrum exhibits a broad resonance signal g=2.150 and is attributed to super exchange between Fe3+ and Co2+. Magnetization values of CoFe2O4 nanoparticle are lower when compared to the literature values of bulk samples. This can be attributed to the surface spin canting due to large surface-to-volume ratio for a nanoscale system. The variation of dielectric constant, dielectric loss, loss tangent and AC conductivity of as-synthesized nano CoFe2O4 particles at room temperature as a function of frequency has been studied. The magnetic and dielectric properties of the samples show that they are suitable for electronic and biomedical applications.

Asymptotically-good, multigroup decodable space-time block codes

For a family of Space-Time Block Codes (STBCs) C-1, C-2,..., with increasing number of transmit antennas N-i, with rates R-i complex symbols per channel use, i = 1, 2,..., we introduce the notion of asymptotic normalized rate which we define as lim(i ->infinity) R-i/N-i, and we say that a family of STBCs is asymptotically-good if its asymptotic normalized rate is non-zero, i. e., when the rate scales as a non-zero fraction of the number of transmit antennas. An STBC C is said to be g-group decodable, g >= 2, if the information symbols encoded by it can be partitioned into g groups, such that each group of symbols can be ML decoded independently of the others. In this paper we construct full-diversity g-group decodable codes with rates greater than one complex symbol per channel use for all g >= 2. Specifically, we construct delay-optimal, g-group decodable codes for number of transmit antennas N-t that are a multiple of g2left perpendicular(g-1/2)right perpendicular with rate N-t/g2(g-1) + g(2)-g/2N(t). Using these new codes as building blocks, we then construct non-delay-optimal g-group decodable codes with rate roughly g times that of the delay-optimal codes, for number of antennas N-t that are a multiple of 2left perpendicular(g-1/2)right perpendicular, with delay gN(t) and rate Nt/2(g-1) + g-1/2N(t). For each g >= 2, the new delay-optimal and non-delay- optimal families of STBCs are both asymptotically-good, with the latter family having the largest asymptotic normalized rates among all known families of multigroup decodable codes with delay T <= gN(t). Also, for g >= 3, these are the first instances of g-group decodable codes with rates greater than 1 reported in the literature.

Gibbs free energy of formation of rhodium sulfides

Using a solid-state electrochemical technique, thermodynamic properties of three sulfide phases (RhS0.882, Rh3S4, Rh2S3) in the binary system (Rh + S) are measured as a function of temperature over the range from (925 to 1275) K. Single crystal CaF2 is used as the electrolyte. The auxiliary electrode consisting of (CaS + CaF2) is designed in such a way that the sulfur chemical potential converts into an equivalent fluorine potential at each electrode. The sulfur potentials at the measuring electrodes are established by the mixtures of (Rh + RhS0.882), (RhS0.882 + Rh3S4) and (Rh3S4 + Rh2S3) respectively. A gas mixture (H-2 + H2S + Ar) of known composition fixes the sulfur potential at the reference electrode. A novel cell design with physical separation of rhodium sulfides in the measuring electrode from CaS in the auxiliary electrode is used to prevent interaction between the two sulfide phases. They equilibrate only via the gas phase in a hermetically sealed reference enclosure. Standard Gibbs energy changes for the following reactions are calculated from the electromotive force of three cells: 2.2667Rh (s) + S-2 (g) -> 2.2667RhS(0.882) (s), Delta(r)G degrees +/- 2330/(J . mol(-1)) = -288690 + 146.18 (T/K), 4.44RhS(0.882) (s) + S-2 (g) -> 1.48Rh(3)S(4) (s), Delta(r)G degrees +/- 2245/(J . mol(-1)) = -245596 + 164.31 (T/K), 4Rh(3)S(4) (s) + S-2 (g) -> 6Rh(2)S(3) (s), Delta(r)G degrees +/- 2490/(J . mol(-1)) = -230957 + 160: 03 (T/K). Standard entropy and enthalpy of formation of rhodium sulfides from elements in their normal standard states at T = 298.15 K are evaluated. (C) 2013 Elsevier Ltd. All rights reserved.