Four‐terminal reducibility and projective‐planar wye‐delta‐wye‐reducible graphs

A graph is YΔY‐reducible if it can be reduced to a vertex by a sequence of series‐parallel reductions and YΔY‐transformations. Terminals are distinguished vertices, that cannot be deleted by reductions and transformations. In this article, we show that four‐terminal planar graphs are YΔY‐reducible when at least three of the vertices lie on the same face. Using this result, we characterize YΔY‐reducible projective‐planar graphs. We also consider terminals in projective‐planar graphs, and establish that graphs of crossing‐number one are YΔY‐reducible. © 2000 John Wiley & Sons, Inc. J Graph Theory 33: 83–93, 2000     

Weak‐quasi‐Stone algebras

In this paper we shall introduce the variety WQS of weak‐quasi‐Stone algebras as a generalization of the variety QS of quasi‐Stone algebras introduced in [9]. We shall apply the Priestley duality developed in [4] for the variety N of ¬‐lattices to give a duality for WQS. We prove that a weak‐quasi‐Stone algebra is characterized by a property of the set of its regular elements, as well by mean of some principal lattice congruences. We will also determine the simple and subdirectly irreducible algebras (© 2009 WILEY‐VCH Verlag GmbH & Co. KGaA, Weinheim)     

Odd‐sized partitions of Russell‐sets

In the setting of ZF, i.e., Zermelo–Fraenkel set theory without the Axiom of Choice (AC), we study partitions of Russell‐sets into sets each with exactly n elements (called n ‐ary partitions), for some integer n. We show that if n is odd, then a Russell‐set X has an n ‐ary partition if and only if |X | is divisible by n. Furthermore, we establish that it is relative consistent with ZF that there exists a Russell‐set X such that |X | is not divisible by any finite cardinal n > 1 (© 2010 WILEY‐VCH Verlag GmbH & Co. KGaA, Weinheim)     

Some 3‐connected 4‐edge‐critical non‐Hamiltonian graphs

Let γ(G) be the domination number of graph G, thus a graph G is k‐edge‐critical if γ (G) = k, and for every nonadjacent pair of vertices u and υ, γ(G + uυ) = k?1. In Chapter 16 of the book “Domination in Graphs—Advanced Topics,” D. Sumner cites a conjecture of E. Wojcicka under the form “3‐connected 4‐critical graphs are Hamiltonian and perhaps, in general (i.e., for any k ≥ 4), (k?1)‐connected, k‐edge‐critical graphs are Hamiltonian.” In this paper, we prove that the conjecture is not true for k = 4 by constructing a class of 3‐connected 4‐edge‐critical non‐Hamiltonian graphs. © 2005 Wiley Periodicals, Inc.     

‐differential equations for ‐classical polynomials and ‐Jacobi–Stirling numbers

We introduce, characterise and provide a combinatorial interpretation for the so‐called q‐Jacobi–Stirling numbers. This study is motivated by their key role in the (reciprocal) expansion of any power of a second order q‐differential operator having the q‐classical polynomials as eigenfunctions in terms of other even order operators, which we explicitly construct in this work. The results here obtained can be viewed as the q‐version of those given by Everitt et al. and by the first author, whilst the combinatorics of this new set of numbers is a q‐version of the Jacobi–Stirling numbers given by Gelineau and the second author.     

The geometry of t‐spreads in k‐walk‐regular graphs

A graph is walk‐regular if the number of closed walks of length ? rooted at a given vertex is a constant through all the vertices for all ?. For a walk‐regular graph G with d+1 different eigenvalues and spectrally maximum diameter D=d, we study the geometry of its d‐spreads, that is, the sets of vertices which are mutually at distance d. When these vertices are projected onto an eigenspace of its adjacency matrix, we show that they form a simplex (or tetrahedron in a three‐dimensional case) and we compute its parameters. Moreover, the results are generalized to the case of k‐walk‐regular graphs, a family which includes both walk‐regular and distance‐regular graphs, and their t‐spreads or vertices at distance t from each other. © 2009 Wiley Periodicals, Inc. J Graph Theory 64:312–322, 2010     

Well‐posedness for the incompressible magneto‐hydrodynamic system

This paper is concerned with well‐posedness of the incompressible magneto‐hydrodynamics (MHD) system. In particular, we prove the existence of a global mild solution in BMO^?1 for small data which is also unique in the space C([0, ∞); BMO^?1). We also establish the existence of a local mild solution in bmo^?1 for small data and its uniqueness in C([0, T); bmo^?1). In establishing our results an important role is played by the continuity of the bilinear form which was proved previously by Kock and Tataru. In this paper, we give a new proof of this result by using the weighted L^p‐boundedness of the maximal function. Copyright © 2006 John Wiley & Sons, Ltd.     

A lower‐epiperimetric inequality for area‐minimizing surfaces

The epiperimetric inequality introduced by E. R. Reifenberg in [3] gives a rate of decay at a point for the decreasing k‐density of area of an area‐minimizing integral k‐cycle. While dilating the cycle at that point, this rate of decay holds once the configuration is close to a tangent cone configuration and above the limiting density corresponding to that configuration. This is why we propose to call the Reifenberg epiperimetric inequality an upper‐epiperimetric inequality. A direct consequence of this upper‐epiperimetric inequality is the statement that any point possesses a unique tangent cone. The upper‐epiperimetric inequality was proven by B. White in [5] for area‐minimizing 2‐cycles in ?ⁿ. In the present paper we introduce the notion of a lower‐epiperimetric inequality. This inequality gives this time a rate of decay for the decreasing k‐density of area of an area‐minimizing integral k‐cycle, while dilating the cycle at a point once the configuration is close to a tangent cone configuration and below the limiting density corresponding to that configuration. Our main result in the present paper is to prove the lower‐epiperimetric inequality for area‐minimizing 2‐cycles in ?ⁿ. As a consequence of this inequality we prove the “splitting before tilting” phenomenon for calibrated 2‐rectifiable cycles, which plays a crucial role in the proof of the regularity of 1‐1 integral currents in [4]. © 2004 Wiley Periodicals, Inc.     

H‐self‐adjoint matrices. Application to radiosity

In computer graphics, in the radiosity context, a linear system Φx=b must be solved and there exists a diagonal positive matrix H such that H Φ is symmetric. In this article, we extend this property to complex matrices: we are interested in matrices which lead to Hermitian matrices under premultiplication by a Hermitian positive‐definite matrix H. We shall prove that these matrices are self‐adjoint with respect to a particular innerproduct defined on ?ⁿ. As a result, like Hermitian matrices, they have real eigenvalues and they are diagonalizable. We shall also show how to extend the Courant–Fisher theorem to this class of matrices. Finally, we shall give a new preconditioning matrix which really improves the convergence speed of the conjugate gradient method used for solving the radiosity problem. Copyright © 2002 John Wiley & Sons, Ltd.     

Genus polynomials and crosscap‐number polynomials for ring‐like graphs

An H‐linear graph is obtained by transforming a collection of copies of a fixed graph H into a chain. An H‐ring‐like graph is formed by binding the two end‐copies of H in such a chain to each other. Genus polynomials have been calculated for bindings of several kinds. In this paper, we substantially generalize the rules for constructing sequences of H‐ring‐like graphs from sequences of H‐linear graphs, and we give a general method for obtaining a recursion for the genus polynomials of the graphs in a sequence of ring‐like graphs. We use Chebyshev polynomials to obtain explicit formulas for the genus polynomials of several such sequences. We also give methods for obtaining recursions for partial genus polynomials and for crosscap‐number polynomials of a bar‐ring of a sequence of disjoint graphs.     

Reliable,goal‐oriented postprocessing for FE‐discretizations

In this article we present strategies to improve the quality of adaptive FE‐approximations measured in terms of linear functionals. The ideas are based on the so called dual‐weighted‐residual (DWR) approach to a posteriori error control for FE‐schemes. In more details, we exploit those parts of an underlying error representation, which are completely computable, to improve the FE‐solution. Furthermore, the remaining parts of the error identity can be estimated by well‐established a posteriori energy estimates yielding reliable error bounds for the postprocessed values. © 2004 Wiley Periodicals, Inc. Numer Methods Partial Differential Eq, 2005     

Partitioning 2‐Edge‐Colored Ore‐Type Graphs by Monochromatic Cycles

Consider a graph G on n vertices satisfying the following Ore‐type condition: for any two nonadjacent vertices x and y of G, we have . We conjecture that if we color the edges of G with two colors then the vertex set of G can be partitioned to two vertex disjoint monochromatic cycles of distinct colors. In this article, we prove an asymptotic version of this conjecture.     

New fifth‐order two‐derivative Runge‐Kutta methods with constant and frequency‐dependent coefficients

Two‐derivative Runge‐Kutta methods are Runge‐Kutta methods for problems of the form y′ = f(y) that include the second derivative y′′ = g(y) = f ′(y)f(y) and were developed in the work of Chan and Tsai. In this work, we consider explicit methods and construct a family of fifth‐order methods with three stages of the general case that use several evaluations of f and g per step. For problems with oscillatory solution and in the case that a good estimate of the dominant frequency is known, methods with frequency‐dependent coefficients are used; there are several procedures for constructing such methods. We give the general framework for the construction of methods with variable coefficients following the approach of Simos. We modify the above family to derive methods with frequency‐dependent coefficients following this approach as well as the approach given by Vanden Berghe. We provide numerical results to demonstrate the efficiency of the new methods using three test problems.     

Tetravalent half‐edge‐transitive graphs and non‐normal Cayley graphs

Let X be a vertex‐transitive graph, that is, the automorphism group Aut(X) of X is transitive on the vertex set of X. The graph X is said to be symmetric if Aut(X) is transitive on the arc set of X. suppose that Aut(X) has two orbits of the same length on the arc set of X. Then X is said to be half‐arc‐transitive or half‐edge‐transitive if Aut(X) has one or two orbits on the edge set of X, respectively. Stabilizers of symmetric and half‐arc‐transitive graphs have been investigated by many authors. For example, see Tutte [Canad J Math 11 (1959), 621–624] and Conder and Maru?i? [J Combin Theory Ser B 88 (2003), 67–76]. It is trivial to construct connected tetravalent symmetric graphs with arbitrarily large stabilizers, and by Maru?i? [Discrete Math 299 (2005), 180–193], connected tetravalent half‐arc‐transitive graphs can have arbitrarily large stabilizers. In this article, we show that connected tetravalent half‐edge‐transitive graphs can also have arbitrarily large stabilizers. A Cayley graph Cay(G, S) on a group G is said to be normal if the right regular representation R(G) of G is normal in Aut(Cay(G, S)). There are only a few known examples of connected tetravalent non‐normal Cayley graphs on non‐abelian simple groups. In this article, we give a sufficient condition for non‐normal Cayley graphs and by using the condition, infinitely many connected tetravalent non‐normal Cayley graphs are constructed. As an application, all connected tetravalent non‐normal Cayley graphs on the alternating group A₆ are determined. © 2011 Wiley Periodicals, Inc. J Graph Theory     

The Crank‐Nicolson/Adams‐Bashforth scheme for the time‐dependent Navier‐Stokes equations with nonsmooth initial data

In this article, we study the stability and convergence of the Crank‐Nicolson/Adams‐Bashforth scheme for the two‐dimensional nonstationary Navier‐Stokes equations with a nonsmooth initial data. A finite element method is applied for the spatial approximation of the velocity and pressure. The time discretization is based on the implicit Crank‐Nicolson scheme for the linear terms and the explicit Adams‐Bashforth scheme for the nonlinear term. Moreover, we prove that the scheme is almost unconditionally stable for a nonsmooth initial data u₀ with div u₀ = 0, i.e., the time step τ satisfies: τ ≤ C₀ if u₀ ∈ H¹ ∩ L^∞; τ |log h| ≤ C₀ if u₀ ∈ H¹ for the mesh size h and some positive constant C₀. Finally, we obtain some error estimates for the discrete velocity and pressure under the above stability condition. © 2010 Wiley Periodicals, Inc. Numer Methods Partial Differential Eq, 28: 155‐187, 2012     

Fold‐2‐covering triangular embeddings

For a graph G and a positive integer m, G_(m) is the graph obtained from G by replacing every vertex by an independent set of size m and every edge by m² edges joining all possible new pairs of ends. If G triangulates a surface, then it is easy to see from Euler's formula that G_(m) can, in principle, triangulate a surface. For m prime and at least 7, it has previously been shown that in fact G_(m) does triangulate a surface, and in fact does so as a “covering with folds” of the original triangulation. For m = 5, this would be a consequence of Tutte's 5‐Flow Conjecture. In this work, we investigate the case m = 2 and describe simple classes of triangulations G for which G₍₂₎ does have a triangulation that covers G “with folds,” as well as providing a simple infinite class of triangulations G of the sphere for which G₍₂₎ does not triangulate any surface. © 2003 Wiley Periodicals, Inc. J Graph Theory 43: 79–92, 2003     

Hyper MV ‐ideals in hyper MV ‐algebras

In this paper we define the hyper operations ?, ∨ and ∧ on a hyper MV ‐algebra and we obtain some related results. After that by considering the notions ofhyper MV ‐ideals and weak hyper MV ‐ideals, we prove some theorems. Then we determine relationships between (weak) hyper MV ‐ideals in a hyper MV ‐algebra (M, ⊕, *, 0) and (weak) hyper K ‐ideals in a hyper K ‐algebra (M, °, 0). Finally we give a characterization of hyper MV ‐algebras of order 3 or 4 based on the (weak) hyper MV ‐ideals (© 2010 WILEY‐VCH Verlag GmbH & Co. KGaA, Weinheim)     

Large Kr‐free subgraphs in Ks‐free graphs and some other Ramsey‐type problems

In this paper we present three Ramsey‐type results, which we derive from a simple and yet powerful lemma, proved using probabilistic arguments. Let 3 ≤ r < s be fixed integers and let G be a graph on n vertices not containing a complete graph K_s on s vertices. More than 40 years ago Erd?s and Rogers posed the problem of estimating the maximum size of a subset of G without a copy of the complete graph K_r. Our first result provides a new lower bound for this problem, which improves previous results of various researchers. It also allows us to solve some special cases of a closely related question posed by Erd?s. For two graphs G and H, the Ramsey number R(G, H) is the minimum integer N such that any red‐blue coloring of the edges of the complete graph K_N, contains either a red copy of G or a blue copy of H. The book with n pages is the graph B_n consisting of n triangles sharing one edge. Here we study the book‐complete graph Ramsey numbers and show that R(B_n, K_n) ≤ O(n³/log^3/2n), improving the bound of Li and Rousseau. Finally, motivated by a question of Erd?s, Hajnal, Simonovits, Sós, and Szemerédi, we obtain for all 0 < δ < 2/3 an estimate on the number of edges in a K₄‐free graph of order n which has no independent set of size n^1‐δ. © 2004 Wiley Periodicals, Inc. Random Struct. Alg., 2005     

Three‐dimensional internal gravity‐capillary waves in finite depth

We consider three‐dimensional inviscid‐irrotational flow in a two‐layer fluid under the effects of gravity and surface tension, where the upper fluid is bounded above by a rigid lid and the lower fluid is bounded below by a flat bottom. We use a spatial dynamics approach and formulate the steady Euler equations as an infinite‐dimensional Hamiltonian system, where an unbounded spatial direction x is considered as a time‐like coordinate. In addition, we consider wave motions that are periodic in another direction z. By analyzing the dispersion relation, we detect several bifurcation scenarios, two of which we study further: a type of 00(is)(iκ₀) resonance and a Hamiltonian Hopf bifurcation. The bifurcations are investigated by performing a center‐manifold reduction, which yields a finite‐dimensional Hamiltonian system. For this finite‐dimensional system, we establish the existence of periodic and homoclinic orbits, which correspond to, respectively, doubly periodic travelling waves and oblique travelling waves with a dark or bright solitary wave profile in the x direction. The former are obtained using a variational Lyapunov‐Schmidt reduction and the latter by first applying a normal form transformation and then studying the resulting canonical system of equations.     

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