Complexity of clique‐coloring odd‐hole‐free graphs

In this paper we investigate the problem of clique‐coloring, which consists in coloring the vertices of a graph in such a way that no monochromatic maximal clique appears, and we focus on odd‐hole‐free graphs. On the one hand we do not know any odd‐hole‐free graph that is not 3‐clique‐colorable, but on the other hand it is NP‐hard to decide if they are 2‐clique‐colorable, and we do not know if there exists any bound k₀ such that they are all k₀ ‐clique‐colorable. First we will prove that (odd hole, codiamond)‐free graphs are 2‐clique‐colorable. Then we will demonstrate that the complexity of 2‐clique‐coloring odd‐hole‐free graphs is actually Σ₂ P‐complete. Finally we will study the complexity of deciding whether or not a graph and all its subgraphs are 2‐clique‐colorable. © 2009 Wiley Periodicals, Inc. J Graph Theory 62: 139–156, 2009     

An adaptive sampling method for high‐dimensional shift‐invariant signals

In this paper, an adaptive method for sampling and reconstructing high‐dimensional shift‐invariant signals is proposed. First, the integrate‐and‐fire sampling scheme and an approximate reconstruction algorithm for one‐dimensional bandlimited signals are generalized to shift‐invariant signals. Then, a high‐dimensional shift‐invariant signal is reduced to be a sequence of one‐dimensional shift‐invariant signals along the trajectories parallel to some coordinate axis, which can be approximately reconstructed by the generalized integrate‐and‐fire sampling scheme. Finally, an approximate reconstruction for the high‐dimensional shift‐invariant signal is obtained by solving a series of stable linear systems of equations. The main result shows that the final reconstructed error is completely determined by the initial threshold in integrate‐and‐fire sampling scheme, which is generally very small. Copyright © 2017 John Wiley & Sons, Ltd.     

Analytical and numerical solutions of a two‐dimensional multi‐term time‐fractional Oldroyd‐B model

In this paper, we consider a two‐dimensional multi‐term time‐fractional Oldroyd‐B equation on a rectangular domain. Its analytical solution is obtained by the method of separation of variables. We employ the finite difference method with a discretization of the Caputo time‐fractional derivative to obtain an implicit difference approximation for the equation. Stability and convergence of the approximation scheme are established in the L_∞ ‐norm. Two examples are given to illustrate the theoretical analysis and analytical solution. The results indicate that the present numerical method is effective for this general two‐dimensional multi‐term time‐fractional Oldroyd‐B model.     

Clique‐coloring some classes of odd‐hole‐free graphs

We consider the problem of clique‐coloring, that is coloring the vertices of a given graph such that no maximal clique of size at least 2 is monocolored. Whereas we do not know any odd‐hole‐free graph that is not 3‐clique‐colorable, the existence of a constant C such that any perfect graph is C‐clique‐colorable is an open problem. In this paper we solve this problem for some subclasses of odd‐hole‐free graphs: those that are diamond‐free and those that are bull‐free. We also prove the NP‐completeness of 2‐clique‐coloring K₄‐free perfect graphs. © 2006 Wiley Periodicals, Inc. J Graph Theory 53: 233–249, 2006     

Strong convergence of the split‐step θ‐method for stochastic age‐dependent population equations

In this paper, we constructed the split‐step θ (SSθ)‐method for stochastic age‐dependent population equations. The main aim of this paper is to investigate the convergence of the SS θ‐method for stochastic age‐dependent population equations. It is proved that the proposed method is convergent with strong order 1/2 under given conditions. Finally, an example is simulated to verify the results obtained from the theory, and comparative analysis with Euler method is given, the results show the higher accuracy of the SS θ‐method. Copyright © 2014 John Wiley & Sons, Ltd.     

On cubic non‐Cayley vertex‐transitive graphs

In 1983, the second author [D. Maru?i?, Ars Combinatoria 16B (1983), 297–302] asked for which positive integers n there exists a non‐Cayley vertex‐transitive graph on n vertices. (The term non‐Cayley numbers has later been given to such integers.) Motivated by this problem, Feng [Discrete Math 248 (2002), 265–269] asked to determine the smallest valency ?(n) among valencies of non‐Cayley vertex‐transitive graphs of order n. As cycles are clearly Cayley graphs, ?(n)?3 for any non‐Cayley number n. In this paper a goal is set to determine those non‐Cayley numbers n for which ?(n) = 3, and among the latter to determine those for which the generalized Petersen graphs are the only non‐Cayley vertex‐transitive graphs of order n. It is known that for a prime p every vertex‐transitive graph of order p, p² or p³ is a Cayley graph, and that, with the exception of the Coxeter graph, every cubic non‐Cayley vertex‐transitive graph of order 2p, 4p or 2p² is a generalized Petersen graph. In this paper the next natural step is taken by proving that every cubic non‐Cayley vertex‐transitive graph of order 4p², p>7 a prime, is a generalized Petersen graph. In addition, cubic non‐Cayley vertex‐transitive graphs of order 2p^k, where p>7 is a prime and k?p, are characterized. © 2011 Wiley Periodicals, Inc. J Graph Theory 69: 77–95, 2012     

Nowhere‐zero 3‐flows in locally connected graphs

Let G be a graph. For each vertex v ∈V(G), N_v denotes the subgraph induces by the vertices adjacent to v in G. The graph G is locally k‐edge‐connected if for each vertex v ∈V(G), N_v is k‐edge‐connected. In this paper we study the existence of nowhere‐zero 3‐flows in locally k‐edge‐connected graphs. In particular, we show that every 2‐edge‐connected, locally 3‐edge‐connected graph admits a nowhere‐zero 3‐flow. This result is best possible in the sense that there exists an infinite family of 2‐edge‐connected, locally 2‐edge‐connected graphs each of which does not have a 3‐NZF. © 2003 Wiley Periodicals, Inc. J Graph Theory 42: 211–219, 2003     

GPBi‐CGstab(L): A Lanczos‐type product method unifying Bi‐CGstab(L) and GPBi‐CG

Lanczos‐type product methods (LTPMs), in which the residuals are defined by the product of stabilizing polynomials and the Bi‐CG residuals, are effective iterative solvers for large sparse nonsymmetric linear systems. Bi‐CGstab(L) and GPBi‐CG are popular LTPMs and can be viewed as two different generalizations of other typical methods, such as CGS, Bi‐CGSTAB, and Bi‐CGStab2. Bi‐CGstab(L) uses stabilizing polynomials of degree L, while GPBi‐CG uses polynomials given by a three‐term recurrence (or equivalently, a coupled two‐term recurrence) modeled after the Lanczos residual polynomials. Therefore, Bi‐CGstab(L) and GPBi‐CG have different aspects of generalization as a framework of LTPMs. In the present paper, we propose novel stabilizing polynomials, which combine the above two types of polynomials. The resulting method is referred to as GPBi‐CGstab(L). Numerical experiments demonstrate that our presented method is more effective than conventional LTPMs.     

Strang‐type preconditioners applied to ordinary and neutral differential‐algebraic equations

This paper deals with boundary‐value methods (BVMs) for ordinary and neutral differential‐algebraic equations. Different from what has been done in Lei and Jin (Lecture Notes in Computer Science, vol. 1988. Springer: Berlin, 2001; 505–512), here, we directly use BVMs to discretize the equations. The discretization will lead to a nonsymmetric large‐sparse linear system, which can be solved by the GMRES method. In order to accelerate the convergence rate of GMRES method, two Strang‐type block‐circulant preconditioners are suggested: one is for ordinary differential‐algebraic equations (ODAEs), and the other is for neutral differential‐algebraic equations (NDAEs). Under some suitable conditions, it is shown that the preconditioners are invertible, the spectra of the preconditioned systems are clustered, and the solution of iteration converges very rapidly. The numerical experiments further illustrate the effectiveness of the methods. Copyright © 2011 John Wiley & Sons, Ltd.     

A new two‐phase structure‐preserving doubling algorithm for critically singular M‐matrix algebraic Riccati equations

Among numerous iterative methods for solving the minimal nonnegative solution of an M‐matrix algebraic Riccati equation, the structure‐preserving doubling algorithm (SDA) stands out owing to its overall efficiency as well as accuracy. SDA is globally convergent and its convergence is quadratic, except for the critical case for which it converges linearly with the linear rate 1/2. In this paper, we first undertake a delineatory convergence analysis that reveals that the approximations by SDA can be decomposed into two components: the stable component that converges quadratically and the rank‐one component that converges linearly with the linear rate 1/2. Our analysis also shows that as soon as the stable component is fully converged, the rank‐one component can be accurately recovered. We then propose an efficient hybrid method, called the two‐phase SDA, for which the SDA iteration is stopped as soon as it is determined that the stable component is fully converged. Therefore, this two‐phase SDA saves those SDA iterative steps that previously have to have for the rank‐one component to be computed accurately, and thus essentially, it can be regarded as a quadratically convergent method. Numerical results confirm our analysis and demonstrate the efficiency of the new two‐phase SDA. Copyright © 2015 John Wiley & Sons, Ltd.     

Lorenz‐gauged vector potential formulations for the time‐harmonic eddy‐current problem with L∞‐regularity of material properties

In this paper, we consider some Lorenz‐gauged vector potential formulations of the eddy‐current problem for the time‐harmonic Maxwell equations with material properties having only L^∞‐regularity. We prove that there exists a unique solution of these problems, and we show the convergence of a suitable finite element approximation scheme. Moreover, we show that some previously proposed Lorenz‐gauged formulations are indeed formulations in terms of the modified magnetic vector potential, for which the electric scalar potential is vanishing. Copyright © 2007 John Wiley & Sons, Ltd.     

Sufficient conditions for graphs to be λ′‐optimal,super‐edge‐connected,and maximally edge‐connected

The restricted‐edge‐connectivity of a graph G, denoted by λ′(G), is defined as the minimum cardinality over all edge‐cuts S of G, where G‐S contains no isolated vertices. The graph G is called λ′‐optimal, if λ′(G) = ξ(G), where ξ(G) is the minimum edge‐degree in G. A graph is super‐edge‐connected, if every minimum edge‐cut consists of edges adjacent to a vertex of minimum degree. In this paper, we present sufficient conditions for arbitrary, triangle‐free, and bipartite graphs to be λ′‐optimal, as well as conditions depending on the clique number. These conditions imply super‐edge‐connectivity, if δ (G) ≥ 3, and the equality of edge‐connectivity and minimum degree. Different examples will show that these conditions are best possible and independent of other results in this area. © 2005 Wiley Periodicals, Inc. J Graph Theory 48: 228–246, 2005     

Optimal combinational quota‐share and excess‐of‐loss reinsurance policies in a dynamic setting

In this paper, we describe a large insurance company's surplus by a Brownian motion with positive drift, which is the approximation of a classical risk process. The problem of minimizing the probability of ruin by controlling the combinational quota‐share and excess‐of‐loss reinsurance strategy is considered. We show that the optimal combinational reinsurance strategy must be the pure excess‐of‐loss reinsurance strategy. Moreover, we give an explicit solution for the optimal reinsurance strategy. Copyright © 2006 John Wiley & Sons, Ltd.     

Even‐hole‐free graphs part I: Decomposition theorem

We prove a decomposition theorem for even‐hole‐free graphs. The decompositions used are 2‐joins and star, double‐star and triple‐star cutsets. This theorem is used in the second part of this paper to obtain a polytime recognition algorithm for even‐hole‐free graphs. © 2002 John Wiley & Sons, Inc. J Graph Theory 39: 6–49, 2002     

Spatial behaviour of solutions of the dual‐phase‐lag heat equation

In this paper we study the spatial behaviour of solutions of some problems for the dual‐phase‐lag heat equation on a semi‐infinite cylinder. The theory of dual‐phase‐lag heat conduction leads to a hyperbolic partial differential equation with a third derivative with respect to time. First, we investigate the spatial evolution of solutions of an initial boundary‐value problem with zero boundary conditions on the lateral surface of the cylinder. Under a boundedness restriction on the initial data, an energy estimate is obtained. An upper bound for the amplitude term in this estimate in terms of the initial and boundary data is also established. For the case of zero initial conditions, a more explicit estimate is obtained which shows that solutions decay exponentially along certain spatial‐time lines. A class of non‐standard problems is also considered for which the temperature and its first two time derivatives at a fixed time T are assumed proportional to their initial values. Copyright © 2004 John Wiley & Sons, Ltd.     

Algebraization of the Three‐valued BCK‐logic

In this paper a definition of n‐valued system in the context of the algebraizable logics is proposed. We define and study the variety V₃, showing that it is definitionally equivalent to the equivalent quasivariety semantics for the “Three‐valued BCK‐logic”. As a consequence we find an axiomatic definition of the above system.     

New fast divide‐and‐conquer algorithms for the symmetric tridiagonal eigenvalue problem

In this paper, two accelerated divide‐and‐conquer (ADC) algorithms are proposed for the symmetric tridiagonal eigenvalue problem, which cost O(N²r) flops in the worst case, where N is the dimension of the matrix and r is a modest number depending on the distribution of eigenvalues. Both of these algorithms use hierarchically semiseparable (HSS) matrices to approximate some intermediate eigenvector matrices, which are Cauchy‐like matrices and are off‐diagonally low‐rank. The difference of these two versions lies in using different HSS construction algorithms, one (denoted by ADC1) uses a structured low‐rank approximation method and the other (ADC2) uses a randomized HSS construction algorithm. For the ADC2 algorithm, a method is proposed to estimate the off‐diagonal rank. Numerous experiments have been carried out to show their stability and efficiency. These algorithms are implemented in parallel in a shared memory environment, and some parallel implementation details are included. Comparing the ADCs with highly optimized multithreaded libraries such as Intel MKL, we find that ADCs could be more than six times faster for some large matrices with few deflations. Copyright © 2016 John Wiley & Sons, Ltd.     

Global solutions to the Navier‐Stokes‐Landau‐Lifshitz system

This paper is dedicated to the study of the Navier‐Stokes‐Landau‐Lifshitz system. We obtain the global existence of a unique solution for this system without any small conditions imposed on the third component of the initial velocity field. Our methods mainly rely upon the Fourier frequency localization and Bony's paraproduct decomposition.     

Extension of GKB‐FP algorithm to large‐scale general‐form Tikhonov regularization

In a recent paper an algorithm for large‐scale Tikhonov regularization in standard form called GKB‐FP was proposed and numerically illustrated. In this paper, further insight into the convergence properties of this method is provided, and extensions to general‐form Tikhonov regularization are introduced. In addition, as alternative to Tikhonov regularization, a preconditioned LSQR method coupled with an automatic stopping rule is proposed. Preconditioning seeks to incorporate smoothing properties of the regularization matrix into the computed solution. Numerical results are reported to illustrate the methods on large‐scale problems. Copyright © 2013 John Wiley & Sons, Ltd.     

A non‐commutative Landau‐Zener formula

We study semi‐classical measures of families of solutions to a 2 × 2 Dirac system with 0 mass, which presents bands crossing. We focus on constant electro‐magnetic fields. The fact that these fields are orthogonal or not leads to different geometric situations. In the first case, one reduces to some well‐understood model problem. For studying the second case, we introduce some two‐scale semi‐classical measures associated with symplectic submanifold. These measures are operator‐valued measures and the transfer of energy at the crossing is described by a non‐commutative Landau‐Zener formula for these measures. (© 2004 WILEY‐VCH Verlag GmbH & Co. KGaA, Weinheim)