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.     

A semidefinite program approach for computing the maximum eigenvalue of a class of structured tensors and its applications in hypergraphs and copositivity test

Finding the maximum eigenvalue of a symmetric tensor is an important topic in tensor computation and numerical multilinear algebra. In this paper, we introduce a new class of structured tensors called W‐tensors, which not only extends the well‐studied nonnegative tensors by allowing negative entries but also covers several important tensors arising naturally from spectral hypergraph theory. We then show that finding the maximum H‐eigenvalue of an even‐order symmetric W‐tensor is equivalent to solving a structured semidefinite program and hence can be validated in polynomial time. This yields a highly efficient semidefinite program algorithm for computing the maximum H‐eigenvalue of W‐tensors and is based on a new structured sums‐of‐squares decomposition result for a nonnegative polynomial induced by W‐tensors. Numerical experiments illustrate that the proposed algorithm can successfully find the maximum H‐eigenvalue of W‐tensors with dimension up to 10,000, subject to machine precision. As applications, we provide a polynomial time algorithm for computing the maximum H‐eigenvalues of large‐size Laplacian tensors of hyperstars and hypertrees, where the algorithm can be up to 13 times faster than the state‐of‐the‐art numerical method introduced by Ng, Qi, and Zhou in 2009. Finally, we also show that the proposed algorithm can be used to test the copositivity of a multivariate form associated with symmetric extended Z‐tensors, whose order may be even or odd.     

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     

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.     

On evolutionary equations with material laws containing fractional integrals

A well‐posedness result for a time‐shift invariant class of evolutionary operator equations involving material laws with fractional time‐integrals of order α ? ]0, 1[ is considered. The fractional derivatives are defined via a function calculus for the (time‐)derivative established as a normal operator in a suitable L² type space. Employing causality, we show that the fractional derivatives thus obtained coincide with the Riemann‐Liouville fractional derivative. We exemplify our results by applications to a fractional Fokker‐Planck equation, equations describing super‐diffusion and sub‐diffusion processes, and a Kelvin‐Voigt type model in fractional visco‐elasticity. Moreover, we elaborate a suitable perspective to deal with initial boundary value problems. Copyright © 2014 John Wiley & Sons, Ltd.     

Representations of MV‐algebras by sheaves

In this paper, inspired by methods of Bigard, Keimel, and Wolfenstein ([2]), we develop an approach to sheaf representations of MV‐algebras which combines two techniques for the representation of MV‐algebras devised by Filipoiu and Georgescu ([18]) and by Dubuc and Poveda ([16]). Following Davey approach ([12]), we use a subdirect representation of MV‐algebras that is based on local MV‐algebras. This allowed us to obtain: (a) a representation of any MV‐algebras as MV‐algebra of all global sections of a sheaf of local MV‐algebras on the spectruum of its prime ideals; (b) a representation of MV‐algebras, having the space of minimal prime ideals compact, as MV‐algebra of all global sections of a Hausdorff sheaf of MV‐chains on the space of minimal prime ideals, which is a Stone space; (c) an adjunction between the category of all MV‐algebras and the category of MV‐algebraic spaces, where an MV‐algebraic space is a pair (X, F), where X is a compact topological space and F is a sheaf of MV‐algebras with stalks that are local (© 2011 WILEY‐VCH Verlag GmbH & Co. KGaA, Weinheim)     

Some limit analysis of a three dimensional viscous compressible capillary model for plasma

In this study, we discuss some limit analysis of a viscous capillary model of plasma, which is expressed as a so‐called the compressible Navier‐Stokes‐Poisson‐Korteweg equation. First, the existence of global smooth solutions for the initial value problem to the compressible Navier‐Stokes‐Poisson‐Korteweg equation with a given Debye length λ and a given capillary coefficient κ is obtained. We also show the uniform estimates of global smooth solutions with respect to the Debye length λ and the capillary coefficient κ. Then, from Aubin lemma, we show that the unique smooth solution of the 3‐dimensional Navier‐Stokes‐Poisson‐Korteweg equations converges globally in time to the strong solution of the corresponding limit equations, as λ tends to zero, κ tends to zero, and λ and κ simultaneously tend to zero. Moreover, we also give the convergence rates of these limits for any given positive time one by one.     

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     

Even and odd holes in cap‐free graphs

It is an old problem in graph theory to test whether a graph contains a chordless cycle of length greater than three (hole) with a specific parity (even, odd). Studying the structure of graphs without odd holes has obvious implications for Berge's strong perfect graph conjecture that states that a graph G is perfect if and only if neither G nor its complement contain an odd hole. Markossian, Gasparian, and Reed have proven that if neither G nor its complement contain an even hole, then G is β‐perfect. In this article, we extend the problem of testing whether G(V, E) contains a hole of a given parity to the case where each edge of G has a label odd or even. A subset of E is odd (resp. even) if it contains an odd (resp. even) number of odd edges. Graphs for which there exists a signing (i.e., a partition of E into odd and even edges) that makes every triangle odd and every hole even are called even‐signable. Graphs that can be signed so that every triangle is odd and every triangle is odd and every hole is odd are called odd‐signable. We derive from a theorem due to Truemper co‐NP characterizations of even‐signable and odd‐signable graphs. A graph is strongly even‐signable if it can be signed so that every cycle of length ≥ 4 with at most one chord is even and every triangle is odd. Clearly a strongly even‐signable graph is even‐signable as well. Graphs that can be signed so that cycles of length four with one chord are even and all other cycles with at most one chord are odd are called strongly odd‐signable. Every strongly odd‐signable graph is odd‐signable. We give co‐NP characterizations for both strongly even‐signable and strongly odd‐signable graphs. A cap is a hole together with a node, which is adjacent to exactly two adjacent nodes on the hole. We derive a decomposition theorem for graphs that contain no cap as induced subgraph (cap‐free graphs). Our theorem is analogous to the decomposition theorem of Burlet and Fonlupt for Meyniel graphs, a well‐studied subclass of cap‐free graphs. If a graph is strongly even‐signable or strongly odd‐signable, then it is cap‐free. In fact, strongly even‐signable graphs are those cap‐free graphs that are even‐signable. From our decomposition theorem, we derive decomposition results for strongly odd‐signable and strongly even‐signable graphs. These results lead to polynomial recognition algorithms for testing whether a graph belongs to one of these classes. © 1999 John Wiley & Sons, Inc. J Graph Theory 30: 289–308, 1999     

Finding a subdivision of a prescribed digraph of order 4

The problem of when a given digraph contains a subdivision of a fixed digraph F is considered. Bang‐Jensen et al. [4] laid out foundations for approaching this problem from the algorithmic point of view. In this article, we give further support to several open conjectures and speculations about algorithmic complexity of finding F‐subdivisions. In particular, up to five exceptions, we completely classify for which 4‐vertex digraphs F, the F‐subdivision problem is polynomial‐time solvable and for which it is NP‐complete. While all NP‐hardness proofs are made by reduction from some version of the 2‐linkage problem in digraphs, some of the polynomial‐time solvable cases involve relatively complicated algorithms.     

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.     

T‐joins intersecting small edge‐cuts in graphs

In an earlier paper 3 , we studied cycles in graphs that intersect all edge‐cuts of prescribed sizes. Passing to a more general setting, we examine the existence of T‐joins in grafts that intersect all edge‐cuts whose size is in a given set A ?{1,2,3}. In particular, we characterize all the contraction‐minimal grafts admitting no T‐joins that intersect all edge‐cuts of size 1 and 2. We also show that every 3‐edge‐connected graft admits a T‐join intersecting all 3‐edge‐cuts. © 2007 Wiley Periodicals, Inc. J Graph Theory 56: 64–71, 2007     

Odd 4‐edge‐colorability of graphs

An odd k‐edge‐coloring of a graph G is a (not necessarily proper) edge‐coloring with at most k colors such that each nonempty color class induces a graph in which every vertex is of odd degree. Pyber (1991) showed that every simple graph is odd 4‐edge‐colorable, and Lužar et al. (2015) showed that connected loopless graphs are odd 5‐edge‐colorable, with one particular exception that is odd 6‐edge‐colorable. In this article, we prove that connected loopless graphs are odd 4‐edge‐colorable, with two particular exceptions that are respectively odd 5‐ and odd 6‐edge‐colorable. Moreover, a color class can be reduced to a size at most 2.     

Regular path decompositions of odd regular graphs

Kotzig asked in 1979 what are necessary and sufficient conditions for a d‐regular simple graph to admit a decomposition into paths of length d for odd d>3. For cubic graphs, the existence of a 1‐factor is both necessary and sufficient. Even more, each 1‐factor is extendable to a decomposition of the graph into paths of length 3 where the middle edges of the paths coincide with the 1‐factor. We conjecture that existence of a 1‐factor is indeed a sufficient condition for Kotzig's problem. For general odd regular graphs, most 1‐factors appear to be extendable and we show that for the family of simple 5‐regular graphs with no cycles of length 4, all 1‐factors are extendable. However, for d>3 we found infinite families of d‐regular simple graphs with non‐extendable 1‐factors. Few authors have studied the decompositions of general regular graphs. We present examples and open problems; in particular, we conjecture that in planar 5‐regular graphs all 1‐factors are extendable. © 2009 Wiley Periodicals, Inc. J Graph Theory 63: 114–128, 2010     

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.     

Non‐well‐founded extensions of \documentclass{article}\usepackage{amssymb}\begin{document}\pagestyle{empty}$\mathbf {V}$\end{document}

This paper describes a new and user‐friendly method for constructing models of non‐well‐founded set theory. Given a sufficiently well‐behaved system θ of non‐well‐founded set‐theoretic equations, we describe how to construct a model M_θ for $\mathsf {ZFC}^-$ in which θ has a non‐degenerate solution. We shall prove that this M_θ is the smallest model for $\mathsf {ZFC}^-$ which contains $\mathbf {V}$ and has a non‐degenerate solution of θ.     

Dynamical stability of compressible drops and stars

Interest is directed to linearized free boundary motion of a compressible liquid subject to surface tension and self‐gravitation respectively. Linearization relative to an a‐priori given solution to the non‐linear equations leads to a non‐local second order evolution problem to be posed in a space‐time cylinder with variable cross section subject to Fréchet boundary conditions along the lateral boundary part. Well‐posedness of the corresponding initial value problem in a natural weak formulation is proved. Copyright © 2005 John Wiley & Sons, Ltd.     

Large‐time behavior of a two‐scale semilinear reaction–diffusion system for concrete sulfatation

We study the large‐time behavior of (weak) solutions to a two‐scale reaction–diffusion system coupled with a nonlinear ordinary differential equations modeling the partly dissipative corrosion of concrete (or cement)‐based materials with sulfates. We prove that as t → ∞ , the solution to the original two‐scale system converges to the corresponding two‐scale stationary system. To obtain the main result, we make use essentially of the theory of evolution equations governed by subdifferential operators of time‐dependent convex functions developed combined with a series of two‐scale energy‐like time‐independent estimates. Copyright © 2014 John Wiley & Sons, Ltd.     

Perturbation analysis in finite LD‐QBD processes and applications to epidemic models

In this paper, our interest is in the perturbation analysis of level‐dependent quasi‐birth‐and‐death (LD‐QBD) processes, which constitute a wide class of structured Markov chains. An LD‐QBD process has the special feature that its space of states can be structured by levels (groups of states), so that a tridiagonal‐by‐blocks structure is obtained for its infinitesimal generator. For these processes, a number of algorithmic procedures exist in the literature in order to compute several performance measures while exploiting the underlying matrix structure; among others, these measures are related to first‐passage times to a certain level L(0) and hitting probabilities at this level, the maximum level visited by the process before reaching states of level L(0), and the stationary distribution. For the case of a finite number of states, our aim here is to develop analogous algorithms to the ones analyzing these measures, for their perturbation analysis. This approach uses matrix calculus and exploits the specific structure of the infinitesimal generator, which allows us to obtain additional information during the perturbation analysis of the LD‐QBD process by dealing with specific matrices carrying probabilistic insights of the dynamics of the process. We illustrate the approach by means of applying multitype versions of the susceptible‐infective (SI) and susceptible‐infective‐susceptible (SIS) epidemic models to the spread of antibiotic‐sensitive and antibiotic‐resistant bacterial strains in a hospital ward.