Chordal bipartite completion of colored graphs

Golumbic, Kaplan, and Shamir [Graph sandwich problems, J. Algorithms 19 (1995) 449-473], in their paper on graph sandwich problems published in 1995, left the status of the sandwich problems for strongly chordal graphs and chordal bipartite graphs open. It was recently shown [C.M.H. de Figueiredo, L. Faria, S. Klein, R. Sritharan, On the complexity of the sandwich problems for strongly chordal graphs and chordal bipartite graphs, Theoret. Comput. Sci., accepted for publication] that the sandwich problem for strongly chordal graphs is NP-complete. We show that given graph G with a proper vertex coloring c, determining whether there is a supergraph of G that is chordal bipartite and also is properly colored by c is NP-complete. This implies that the sandwich problem for chordal bipartite graphs is also NP-complete.     

On the complexity of deciding whether the distinguishing chromatic number of a graph is at most two

In an article Cheng (2009) [3] published recently in this journal, it was shown that when k≥3, the problem of deciding whether the distinguishing chromatic number of a graph is at most k is NP-hard. We consider the problem when k=2. In regards to the issue of solvability in polynomial time, we show that the problem is at least as hard as graph automorphism, but no harder than graph isomorphism.     

Exact controllability for the magnetohydrodynamic equations

We study the local exact controllability of the steady state solutions of the magnetohydrodynamic equations. The main result of the paper asserts that the steady state solutions of these equations are locally controllable if they are smooth enough. We reduce the local exact controllability of the steady state solutions of the magnetohydrodynamic equations to the global exact controllability of the null solution of the linearized magnetohydrodynamic system via a fixed‐point argument. The treatment of the reduced problem relies on two Carleman‐type inequalities for the backward adjoint system. © 2003 Wiley Periodicals, Inc.     

Large deviations for the two-dimensional Navier–Stokes equations with multiplicative noise

A Wentzell–Freidlin type large deviation principle is established for the two-dimensional Navier–Stokes equations perturbed by a multiplicative noise in both bounded and unbounded domains. The large deviation principle is equivalent to the Laplace principle in our function space setting. Hence, the weak convergence approach is employed to obtain the Laplace principle for solutions of stochastic Navier–Stokes equations. The existence and uniqueness of a strong solution to (a) stochastic Navier–Stokes equations with a small multiplicative noise, and (b) Navier–Stokes equations with an additional Lipschitz continuous drift term are proved for unbounded domains which may be of independent interest.     

Navier-Stokes equation with hereditary viscosity

We rigorously study the Navier-Stokes equation with a hereditary viscous term which depends on the past history. Such models arise in the dynamics of non-Newtonian fluids and also as viscoelastic models for the dynamics of turbulence statistics in Newtonian fluids. This problem is mathematically harder than the conventional Navier-Stokes problem due to the lack of certain global estimates. We prove the local solvability theorem using a suitable intermediate m-accretive quantization of the nonlinear term. Finite speed of propagation property of the vorticity field is also proved.     

A Min–Max Property of Chordal Bipartite Graphs with Applications

We show that if G is a bipartite graph with no induced cycles on exactly 6 vertices, then the minimum number of chain subgraphs of G needed to cover E(G) equals the chromatic number of the complement of the square of line graph of G. Using this, we establish that for a chordal bipartite graph G, the minimum number of chain subgraphs of G needed to cover E(G) equals the size of a largest induced matching in G, and also that a minimum chain subgraph cover can be computed in polynomial time. The problems of computing a minimum chain cover and a largest induced matching are NP-hard for general bipartite graphs. Finally, we show that our results can be used to efficiently compute a minimum chain subgraph cover when the input is an interval bigraph.     

Twin-microstructure enhanced magnetoresistance in La0.67Ba0.33MnO3 oxides

The grain growth dependence of microstructure and its effects on magnetic and transport properties are studied in the polycrystalline La_0.67Ba_0.33MnO₃ oxides. It is found that a lateral growth manner along a certain direction and a concentric terrace pattern along three orthogonal axes occur in the samples sintered at 1573 and 1673 K, respectively. Lamella-like twin microstructure forms in the concentric terrace growth pattern and the magnetoresistance properties can be enhanced by the twin microstructure. It suggests that the twin-boundaries in twin-grains may possibly induce spin-dependent scattering of electrons that is field reduced, or spin-polarized tunneling of electrons that is field enhanced, thus strengthening the effect of grain boundaries.