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.     

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     

Acyclic 4‐Choosability of Planar Graphs with No 4‐ and 5‐Cycles

Every planar graph is known to be acyclically 7‐choosable and is conjectured to be acyclically 5‐choosable (O. V. Borodin, D. G. Fon‐Der‐Flaass, A. V. Kostochka, E. Sopena, J Graph Theory 40 (2002), 83–90). This conjecture if proved would imply both Borodin's (Discrete Math 25 (1979), 211–236) acyclic 5‐color theorem and Thomassen's (J Combin Theory Ser B 62 (1994), 180–181) 5‐choosability theorem. However, as yet it has been verified only for several restricted classes of graphs. Some sufficient conditions are also obtained for a planar graph to be acyclically 4‐ and 3‐choosable. In particular, the acyclic 4‐choosability was proved for the following planar graphs: without 3‐, 4‐, and 5‐cycles (M. Montassier, P. Ochem, and A. Raspaud, J Graph Theory 51 (2006), 281–300), without 4‐, 5‐, and 6‐cycles, or without 4‐, 5‐, and 7‐cycles, or without 4‐, 5‐, and intersecting 3‐cycles (M. Montassier, A. Raspaud, W. Wang, Topics Discrete Math (2006), 473–491), and neither 4‐ and 5‐cycles nor 8‐cycles having a triangular chord (M. Chen and A. Raspaud, Discrete Math. 310(15–16) (2010), 2113–2118). The purpose of this paper is to strengthen these results by proving that each planar graph without 4‐ and 5‐cycles is acyclically 4‐choosable.     

3‐Flows and Combs

Tutte's 3‐Flow Conjecture states that every 2‐edge‐connected graph with no 3‐cuts admits a 3‐flow. The 3‐Flow Conjecture is equivalent to the following: let G be a 2‐edge‐connected graph, let S be a set of at most three vertices of G; if every 3‐cut of G separates S then G has a 3‐flow. We show that minimum counterexamples to the latter statement are 3‐connected, cyclically 4‐connected, and cyclically 7‐edge‐connected.     

On Finite 2‐Path‐Transitive Graphs

The class of graphs that are 2‐path‐transitive but not 2‐arc‐transitive is investigated. The amalgams for such graphs are determined, and structural information regarding the full automorphism groups is given. It is then proved that a graph is 2‐path‐transitive but not 2‐arc‐transitive if and only if its line graph is half‐arc‐transitive, thus providing a method for constructing new families of half‐arc‐transitive graphs. © 2012 Wiley Periodicals, Inc. J. Graph Theory 73: 225–237, 2013     

Line graphs of multigraphs and Hamilton‐connectedness of claw‐free graphs

We introduce a closure concept that turns a claw‐free graph into the line graph of a multigraph while preserving its (non‐)Hamilton‐connectedness. As an application, we show that every 7‐connected claw‐free graph is Hamilton‐connected, and we show that the well‐known conjecture by Matthews and Sumner (every 4‐connected claw‐free graph is hamiltonian) is equivalent with the statement that every 4‐connected claw‐free graph is Hamilton‐connected. Finally, we show a natural way to avoid the non‐uniqueness of a preimage of a line graph of a multigraph, and we prove that the closure operation is, in a sense, best possible. © 2010 Wiley Periodicals, Inc. J Graph Theory 66:152‐173, 2011     

A state‐dependent Markov‐modulated mechanism for generating events and stochastic models

In this paper, we introduce a versatile block‐structured state‐dependent event (BSDE) approach that provides a methodological tool to construct non‐homogeneous Markov‐modulated stochastic models. Alternatively, the BSDE approach can be used to construct even a part (e.g. the arrival process) of the model. To illustrate the usefulness of the BSDE approach, several arrival patterns as well as queueing and epidemic models are considered. In particular, we deal with a state‐dependent quasi‐birth‐and‐death process that gives a constructive generalization of the scalar birth‐and‐death process and the homogeneous quasi‐birth‐and‐death process. Copyright © 2009 John Wiley & Sons, Ltd.     

New types of hyper MV‐deductive systems in hyper MV‐algebras

The notions of a (weak) hyper MV‐deductive system, a (?, ?; ?)‐hyper MV‐deductive system, a (?, ?; ?)‐ hyper MV‐deductive system, a (?, ?; ?)‐hyper MV‐deductive system, a (?, ?; ?)‐hyper MV‐deductive system and a (∩, ∩; ∩)‐hyper MV‐deductive system are introduced, and then their relations are investigated (© 2010 WILEY‐VCH Verlag GmbH & Co. KGaA, Weinheim)     

Bi‐Presymplectic Representation of Liouville Integrable Systems and Related Separability Theory

Bi‐presymplectic chains of one‐forms of arbitrary co‐rank are considered. The conditions in which such chains represent some Liouville integrable systems and the conditions in which there exist related bi‐Hamiltonian chains of vector fields are presented. To derived the construction of bi‐presymplectic chains, the notions of dual Poisson‐presymplectic pair, d‐compatibility of presymplectic forms and d‐compatibility of Poisson bivectors is used. The completely algorithmic construction of separation coordinates is demonstrated. It is also proved that Stäckel separable systems have bi‐inverse‐Hamiltonian representation, i.e., are represented by bi‐presymplectic chains of closed one‐forms. The co‐rank of related structures depends on the explicit form of separation relations.     

Dynamics and pattern formations in diffusive predator‐prey models with two prey‐taxis

A reaction‐diffusion two‐predator‐one‐prey system with prey‐taxis describes the spatial interaction and random movement of predator and prey species, as well as the spatial movement of predators pursuing preys. The global existence and boundedness of solutions of the system in bounded domains of arbitrary spatial dimension and any small prey‐taxis sensitivity coefficient are investigated by the semigroup theory. The spatial pattern formation induced by the prey‐taxis is characterized by the Turing type linear instability of homogeneous state; it is shown that prey‐taxis can both compress and prompt the spatial patterns produced through diffusion‐induced instability in two‐predator‐one‐prey systems.     

Log‐symmetric regression models: information criteria and application to movie business and industry data with economic implications

This work deals with log‐symmetric regression models, which are particularly useful when the response variable is continuous, strictly positive, and following an asymmetric distribution, with the possibility of modeling atypical observations by means of robust estimation. In these regression models, the distribution of the random errors is a member of the log‐symmetric family, which is composed by the log‐contaminated‐normal, log‐hyperbolic, log‐normal, log‐power‐exponential, log‐slash and log‐Student‐t distributions, among others. One way to select the best family member in log‐symmetric regression models is using information criteria. In this paper, we formulate log‐symmetric regression models and conduct a Monte Carlo simulation study to investigate the accuracy of popular information criteria, as Akaike, Bayesian, and Hannan‐Quinn, and their respective corrected versions to choose adequate log‐symmetric regressions models. As a business application, a movie data set assembled by authors is analyzed to compare and obtain the best possible log‐symmetric regression model for box offices. The results provide relevant information for model selection criteria in log‐symmetric regressions and for the movie industry. Economic implications of our study are discussed after the numerical illustrations.     

Two‐dimensional adaptive Fourier decomposition

One‐dimensional adaptive Fourier decomposition, abbreviated as 1‐D AFD, or AFD, is an adaptive representation of a physically realizable signal into a linear combination of parameterized Szegö and higher‐order Szegö kernels of the context. In the present paper, we study multi‐dimensional AFDs based on multivariate complex Hardy spaces theory. We proceed with two approaches of which one uses Product‐TM Systems; and the other uses Product‐Szegö Dictionaries. With the Product‐TM Systems approach, we prove that at each selection of a pair of parameters, the maximal energy may be attained, and, accordingly, we prove the convergence. With the Product‐Szegö dictionary approach, we show that pure greedy algorithm is applicable. We next introduce a new type of greedy algorithm, called Pre‐orthogonal Greedy Algorithm (P‐OGA). We prove its convergence and convergence rate estimation, allowing a weak‐type version of P‐OGA as well. The convergence rate estimation of the proposed P‐OGA evidences its advantage over orthogonal greedy algorithm (OGA). In the last part, we analyze P‐OGA in depth and introduce the concept P‐OGA‐Induced Complete Dictionary, abbreviated as Complete Dictionary. We show that with the Complete Dictionary P‐OGA is applicable to the Hardy H² space on 2‐torus. Copyright © 2016 John Wiley & Sons, Ltd.     

Hopf bifurcation of a diffusive Gause‐type predator‐prey model induced by time fractional‐order derivatives

Since population behaviors possess the characteristic of history memory, we, in this paper, introduce time fractional‐order derivatives into a diffusive Gause‐type predator‐prey model, which is time fractional‐order reaction‐diffusion equations and a generalized form of its corresponding first‐derivative model. For this kind of model, we prove the existence and uniqueness of a global positive solution by using the theory of evolution equations and the comparison principle of time fractional‐order partial differential equations. Besides, we obtain the stability and Hopf bifurcation of the Gause‐type predator‐prey model in the forms of the time fractional‐order ordinary equations and of the time fractional‐order reaction‐diffusion equations, respectively. Our results show that the stable region of the parameters in these 2 models can be enlarged by the time fractional‐order derivatives. Some numerical simulations are made to verify our results.     

Analysis of the energy‐conserved S‐FDTD scheme for variable coefficient Maxwell's equations in disk domains

In this paper, we analyze the energy‐conserved splitting finite‐difference time‐domain (FDTD) scheme for variable coefficient Maxwell's equations in two‐dimensional disk domains. The approach is energy‐conserved, unconditionally stable, and effective. We strictly prove that the EC‐S‐FDTD scheme for the variable coefficient Maxwell's equations in disk domains is of second order accuracy both in time and space. It is also strictly proved that the scheme is energy‐conserved, and the discrete divergence‐free is of second order convergence. Numerical experiments confirm the theoretical results, and practical test is simulated as well to demonstrate the efficiency of the proposed EC‐S‐FDTD scheme. Copyright © 2015 John Wiley & Sons, Ltd.     

Existence and zero‐electron‐mass limit of strong solutions to the stationary compressible Navier‐Stokes‐Poisson equation with large external force

In this study, we consider a viscous compressible model of plasma and semiconductors, which is expressed as a compressible Navier‐Stokes‐Poisson equation. We prove that there exists a strong solution to the boundary value problem of the steady compressible Navier‐Stokes‐Poisson equation with large external forces in bounded domain, provided that the ratio of the electron/ions mass is appropriately small. Moreover, the zero‐electron‐mass limit of the strong solutions is rigorously verified. The main idea in the proof is to split the original equation into 4 parts, a system of stationary incompressible Navier‐Stokes equations with large forces, a system of stationary compressible Navier‐Stokes equations with small forces, coupled with 2 Poisson equations. Based on the known results about linear incompressible Navier‐Stokes equation, linear compressible Navier‐Stokes, linear transport, and Poisson equations, we try to establish uniform in the ratio of the electron/ions mass a priori estimates. Further, using Schauder fixed point theorem, we can show the existence of a strong solution to the boundary value problem of the steady compressible Navier‐Stokes‐Poisson equation with large external forces. At the same time, from the uniform a priori estimates, we present the zero‐electron‐mass limit of the strong solutions, which converge to the solutions of the corresponding incompressible Navier‐Stokes‐Poisson equations.     

Non‐elementary speed‐ups in logic calculi

In this paper we show some non‐elementary speed‐ups in logic calculi: Both a predicative second‐order logic and a logic for fixed points of positive formulas are shown to have non‐elementary speed‐ups over first‐order logic. Also it is shown that eliminating second‐order cut formulas in second‐order logic has to increase sizes of proofs super‐exponentially, and the same in eliminating second‐order epsilon axioms. These are proved by relying on results due to P. Pudlák. (© 2008 WILEY‐VCH Verlag GmbH & Co. KGaA, Weinheim)     

Algebraic multigrid and 4th‐order discrete‐difference equations of incompressible fluid flow

This paper investigates the effectiveness of two different Algebraic Multigrid (AMG) approaches to the solution of 4th‐order discrete‐difference equations for incompressible fluid flow (in this case for a discrete, scalar, stream‐function field). One is based on a classical, algebraic multigrid, method (C‐AMG) the other is based on a smoothed‐aggregation method for 4th‐order problems (SA‐AMG). In the C‐AMG case, the inter‐grid transfer operators are enhanced using Jacobi relaxation. In the SA‐AMG case, they are improved using a constrained energy optimization of the coarse‐grid basis functions. Both approaches are shown to be effective for discretizations based on uniform, structured and unstructured, meshes. They both give good convergence factors that are largely independent of the mesh size/bandwidth. The SA‐AMG approach, however, is more costly both in storage and operations. The Jacobi‐relaxed C‐AMG approach is faster, by a factor of between 2 and 4 for two‐dimensional problems, even though its reduction factors are inferior to those of SA‐AMG. For non‐uniform meshes, the accuracy of this particular discretization degrades from 2nd to 1st order and the convergence factors for both methods then become mesh dependent. Copyright © 2009 John Wiley & Sons, Ltd.