An Inverse Problem for Differential Operators of the Orr‐Sommerfeld Type

We study the inverse problem of recovering differential operators of the Orr‐Sommerfeld type from the Weyl matrix. Properties of the Weyl matrix are investigated, and an uniqueness theorem for the solution of the inverse problem is proved.     

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     

An inverse problem for Sturm‐Liouville operators on trees with partial information given on the potentials

We consider Sturm‐Liouville operators on geometrical graphs without cycles (trees) with singular potentials from the class . We suppose that the potentials are known on a part of the graph, and study the so‐called partial inverse problem, which consists in recovering the potentials on the remaining part of the graph from some parts of several spectra. The main results of the paper are the uniqueness theorem and a constructive procedure for the solution of the partial inverse problem. Our method is based on the completeness and the Riesz‐basis property of special systems of vector functions and the reduction of the partial inverse problem to the complete one on a part of the graph.     

An inverse problem for space‐fractional backward diffusion problem

In this paper, an inverse problem for space‐fractional backward diffusion equation, which is highly ill‐posed, is considered. This problem is obtained from the classical diffusion equation by replacing the second‐order space derivative with a Riesz–Feller derivative of order α ∈ (0,2]. We show that such a problem is severely ill‐posed, and further present a simplified Tikhonov regularization method to deal with this problem. Convergence estimate is presented under a priori choice of regularization parameter. Numerical experiments are given to illustrate the accuracy and efficiency of the proposed method. Copyright © 2013 John Wiley & Sons, Ltd.     

Inverse spectral problem of fourth‐order boundary value problems with finite spectrum

In the present paper, we consider a class of inverse spectral problem of fourth‐order boundary value problems. Under the so‐called “Atkinson type” conditions, the problem has finite spectrum and corresponding matrix representations. By using the method of inverse matrix eigenvalue problems of two‐banded matrix, the leading coefficient and potential functions are reconstructed from the given three sets of interlacing real numbers satisfying certain conditions.     

Determination of a time‐ and space‐dependent heat flux relaxation function by means of a restricted Dirichlet‐to‐Neumann operator

We consider an inverse problem to recover a space‐ and time‐dependent relaxation function of heat flux in a three‐dimensional body on the basis of the restriction of the Dirichlet‐to‐Neumann operator of the related equation of heat flow onto a set of Dirichlet data of the form of a product of a fixed time‐dependent coefficient and a free space‐dependent function. Uniqueness of the solution of this inverse problem is proved. Copyright © 2004 John Wiley & Sons, Ltd.     

Two Tikhonov‐type regularization methods for inverse source problem on the Poisson equation

In this paper, we investigate a problem of the identification of an unknown source on Poisson equation from some fixed location. A conditional stability estimate for an inverse heat source problem is proved. We show that such a problem is mildly ill‐posed and further present two Tikhonov‐type regularization methods (a generalized Tikhonov regularization method and a simplified generalized Tikhonov regularization method) to deal with this problem. Convergence estimates are presented under the a priori choice of the regularization parameter. Numerical results are presented to illustrate the accuracy and efficiency of our methods. Copyright © 2012 John Wiley & Sons, Ltd.     

The k‐piece packing problem

A k‐piece of a graph G is a connected subgraph of G all of whose nodes have degree at most k and at least one node has degree equal to k. We consider the problem of covering the maximum number of nodes of a graph by node disjoint k‐pieces. When k = 1 this is the maximum matching problem, and when k = 2 this is the problem, recently studied by Kaneko [ 19 [, of covering the maximum number of nodes by disjoint paths of length greater than 1. We present a polynomial time algorithm for the problem as well as a Tutte‐type existence theorem and a Berge‐type min‐max formula. We also solve the problem in the more general situation where the “pieces” are defined in terms of lower and upper bounds on the degrees. © 2006 Wiley Periodicals, Inc. J Graph Theory     

Schur complement‐based domain decomposition preconditioners with low‐rank corrections

This paper introduces a robust preconditioner for general sparse matrices based on low‐rank approximations of the Schur complement in a Domain Decomposition framework. In this ‘Schur Low Rank’ preconditioning approach, the coefficient matrix is first decoupled by a graph partitioner, and then a low‐rank correction is exploited to compute an approximate inverse of the Schur complement associated with the interface unknowns. The method avoids explicit formation of the Schur complement. We show the feasibility of this strategy for a model problem and conduct a detailed spectral analysis for the relation between the low‐rank correction and the quality of the preconditioner. We first introduce the SLR preconditioner for symmetric positive definite matrices and symmetric indefinite matrices if the interface matrices are symmetric positive definite. Extensions to general symmetric indefinite matrices as well as to nonsymmetric matrices are also discussed. Numerical experiments on general matrices illustrate the robustness and efficiency of the proposed approach. Copyright © 2016 John Wiley & Sons, Ltd.     

TV‐like regularization for backward parabolic problems

This paper investigates an inverse problem for parabolic equations backward in time, which is solved by total‐variation‐like (TV‐like, in abbreviation) regularization method with cost function ∥u_x∥². The existence, uniqueness and stability estimate for the regularization problem are deduced in the linear case. For numerical illustration, the variational adjoint method, which presents a simple method to derive the gradient of the optimization functional, is introduced to reconstruct the unknown initial condition for both linear and nonlinear parabolic equations. The conjugate gradient method is used to iteratively search for the optimal approximation. Numerical results validate the feasibility and effectiveness of the proposed algorithm. Copyright © 2016 John Wiley & Sons, Ltd.     

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     

On Switching to H‐Free Graphs

In this article, we study the problem of deciding if, for a fixed graph H, a given graph is switching equivalent to an H‐free graph. Polynomial‐time algorithms are known for H having at most three vertices or isomorphic to P₄. We show that for H isomorphic to a claw, the problem is polynomial, too. On the other hand, we give infinitely many graphs H such that the problem is NP‐complete, thus solving an open problem [Kratochvíl, Ne?et?il and Zýka, Ann Discrete Math 51 (1992)]. Further, we give a characterization of graphs switching equivalent to a K_{1, 2}‐free graph by ten forbidden‐induced subgraphs, each having five vertices. We also give the forbidden‐induced subgraphs for graphs switching equivalent to a forest of bounded vertex degrees.     

Clique‐inverse graphs of K3‐free and K4‐free graphs

The clique graph K(G) of a given graph G is the intersection graph of the collection of maximal cliques of G. Given a family ℱ of graphs, the clique‐inverse graphs of ℱ are the graphs whose clique graphs belong to ℱ. In this work, we describe characterizations for clique‐inverse graphs of K₃‐free and K₄‐free graphs. The characterizations are formulated in terms of forbidden induced subgraphs. © 2000 John Wiley & Sons, Inc. J Graph Theory 35: 257–272, 2000     

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.     

The plane‐width of graphs

Map the vertices of a graph to (not necessarily distinct) points of the plane so that two adjacent vertices are mapped at least unit distance apart. The plane‐width of a graph is the minimum diameter of the image of its vertex set over all such mappings. We establish a relation between the plane‐width of a graph and its chromatic number. We also connect it to other well‐known areas, including the circular chromatic number and the problem of packing unit discs in the plane. © 2011 Wiley Periodicals, Inc. J Graph Theory 68: 229‐245, 2011     

The quasi‐reversibility method for a final value problem of the time‐fractional diffusion equation with inhomogeneous source

This paper is devoted to discuss a multidimensional backward heat conduction problem for time‐fractional diffusion equation with inhomogeneous source. This problem is ill‐posed. We use quasi‐reversibility regularization method to solve this inverse problem. Moreover, the convergence estimates between regularization solution and the exact solution are obtained under the a priori and the a posteriori choice rules. Finally, the numerical examples for one‐dimensional and two‐dimensional cases are presented to show that our method is feasible and effective.     

Forbidden minors for wye‐delta‐wye reducibility

A graph is Y Δ Y reducible if it can be reduced to a single vertex by a sequence of series‐parallel reductions and Y Δ Y transformations. The class of Y Δ Y reducible graphs is minor closed. We found a large number of minor minimal Y Δ Y irreducible graphs: a family of 57578 31‐edge graphs and another 40‐edge graph. It is still an open problem to characterize Y Δ Y reducible graphs in terms of a finite set of forbidden minors. © 2004 Wiley Periodicals, Inc. J Graph Theory 47: 317–321, 2004     

Inverse problem with a time‐integral condition for a fractional diffusion equation

We find the conditions for the unique solvability of the inverse problem for a time‐fractional diffusion equation with Schwarz‐type distributions in the right‐hand sides. This problem is to find a generalized solution of the Cauchy problem and an unknown space‐dependent part of an equation's right‐hand side under a time‐integral overdetermination condition.     

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     

A data assimilation process for linear ill‐posed problems

In this paper, an iteration process is considered to solve linear ill‐posed problems. Based on the randomness of the involved variables, this kind of problems is regarded as simulation problems of the posterior distribution of the unknown variable given the noise data. We construct a new ensemble Kalman filter‐based method to seek the posterior target distribution. Despite the ensemble Kalman filter method having widespread applications, there has been little analysis of its theoretical properties, especially in the field of inverse problems. This paper analyzes the propagation of the error with the iteration step for the proposed algorithm. The theoretical analysis shows that the proposed algorithm is convergence. We compare the numerical effect with the Bayesian inversion approach by two numerical examples: backward heat conduction problem and the first kind of integral equation. The numerical tests show that the proposed algorithm is effective and competitive with the Bayesian method. Copyright © 2017 John Wiley & Sons, Ltd.