Ultraconvergence of finite element method by Richardson extrapolation for elliptic problems with inhomogeneous boundary conditions

In this article, Richardson extrapolation technique is employed to investigate the local ultraconvergence properties of Lagrange finite element method using piecewise polynomials of degrees () for the second order elliptic problem with inhomogeneous boundary. A sequence of special graded partition are proposed and a new interpolation operator is introduced to achieve order local ultraconvergence for the displacement and derivative.     

H1-superconvergence of finite difference method based on Q1-element on quasi-uniform mesh for the 3D Poisson equation

In this paper, the finite difference (FD) method is considered for the 3D Poisson equation by using the Q₁-element on a quasi-uniform mesh. First, under the regularity assumption of , the H¹-superconvergence of the FD solution u_h based on the Q₁-element to the first-order interpolation function is obtained. Next, the H¹-superconvergence of the second-order interpolation postprocessing function based on the FD solution u_h to u is provided. Finally, numerical tests are presented to show the H¹-superconvergence result of the FD postprocessing function to u if .     

Numerical analysis for a system coupling curve evolution attached orthogonally to a fixed boundary,to a reaction–diffusion equation on the curve

We consider a semidiscrete finite element approximation for a system consisting of the evolution of a planar curve evolving by forced curve shortening flow inside a given bounded domain , such that the curve meets the boundary orthogonally, and the forcing is a function of the solution of a reaction–diffusion equation that holds on the evolving curve. We prove optimal order error bounds for the resulting approximation and present numerical experiments.     

Superconvergence analysis of an energy stable scheme with three step backward differential formula-finite element method for nonlinear reaction–diffusion equation

A three step backward differential formula scheme is proposed for nonlinear reaction–diffusion equation and superconvergence results are studied with Galerkin finite element method unconditionally. Energy stability is testified for the constructed scheme with an artificial term. Splitting technique is utilized to get rid of the ratio between the time step size and the subdivision parameter . Temporal error estimate in H²-norm is derived, which leads to the boundedness of the solutions of the time-discrete equations. Unconditional spatial error estimate in L²-norm is deduced which help bound the numerical solutions in L^∞-norm. Superconvergent property of in H¹-norm with order is obtained by taking difference between two time levels of the error equations unconditionally. The global superconvergent property is deduced through the above results. Two numerical examples show the validity of the theoretical analysis.     

On the numerical approximation of p‐biharmonic and ∞‐biharmonic functions

The ∞ ‐Bilaplacian is a third‐order fully nonlinear PDE given by (1) In this work, we build a numerical method aimed at quantifying the nature of solutions to this problem, which we call ∞ ‐biharmonic functions. For fixed p we design a mixed finite element scheme for the prelimiting equation, the p‐Bilaplacian (2) We prove convergence of the numerical solution to the weak solution of and show that we are able to pass to the limit p → ∞ . We perform various tests aimed at understanding the nature of solutions of and we prove convergence of our discretization to an appropriate weak solution concept of this problem that of ‐solutions.     

Fast high order difference schemes for the time fractional telegraph equation

In this paper, a fast high order difference scheme is first proposed to solve the time fractional telegraph equation based on the ℱℒ 2-1_σ formula for the Caputo fractional derivative, which reduces the storage and computational cost for calculation. A compact scheme is then presented to improve the convergence order in space. The unconditional stability and convergence in maximum norm are proved for both schemes, with the accuracy order and , respectively. Difficulty arising from the two Caputo fractional derivatives is overcome by some detailed analysis. Finally, we carry out numerical experiments to show the efficiency and accuracy, by comparing with the ℒ 2-1_σ method.     

Fractal graphs

The lexicographic sum of graphs is defined as follows. Let be a graph. With each associate a graph . The lexicographic sum of the graphs over is obtained from by substituting each by . Given distinct , we have all the possible edges in the lexicographic sum between and if , and none otherwise. When all the graphs are isomorphic to some graph , the lexicographic sum of the graphs over is called the lexicographic product of by and is denoted by . We say that a graph is fractal if there exists a graph , with at least two vertices, such that . There is a simple way to construct fractal graphs. Let be a graph with at least two vertices. The graph is defined on the set of functions from to as follows. Given distinct is an edge of if is an edge of , where is the smallest integer such that . The graph is fractal because . We prove that a fractal graph is isomorphic to a lexicographic sum over an induced subgraph of , which is itself fractal.     

Bipartite spanning sub(di)graphs induced by 2-partitions

For a given -partition of the vertices of a (di)graph , we study properties of the spanning bipartite subdigraph of induced by those arcs/edges that have one end in each . We determine, for all pairs of nonnegative integers , the complexity of deciding whether has a 2-partition such that each vertex in (for ) has at least (out-)neighbours in . We prove that it is -complete to decide whether a digraph has a 2-partition such that each vertex in has an out-neighbour in and each vertex in has an in-neighbour in . The problem becomes polynomially solvable if we require to be strongly connected. We give a characterisation of the structure of -complete instances in terms of their strong component digraph. When we want higher in-degree or out-degree to/from the other set, the problem becomes -complete even for strong digraphs. A further result is that it is -complete to decide whether a given digraph has a -partition such that is strongly connected. This holds even if we require the input to be a highly connected eulerian digraph.     

Distance matching extension and local structure of graphs

A matching in a graph is said to be extendable if there exists a perfect matching of containing . Also, is said to be a distance matching if the shortest distance between a pair of edges in is at least . A graph is distance matchable if every distance matching is extendable in , regardless of its size. In this paper, we study the class of distance matchable graphs. In particular, we prove that for every integer with , there exists a positive integer such that every connected, locally -connected -free graph of even order is distance matchable. We also prove that every connected, locally -connected -free graph of even order is distance matchable. Furthermore, we make more detailed analysis of -free graphs and study their distance matching extension properties.     

The Ramsey number of loose cycles versus cliques

Let be the Ramsey number of an -uniform loose cycle of length versus an -uniform clique of order . Kostochka et al. showed that for each fixed , the order of magnitude of is up to a polylogarithmic factor in . They conjectured that for each we have . We prove that , and more generally for every that . We also prove that for every and , if is odd, which improves upon the result of Collier-Cartaino et al. who proved that for every and we have .     

Superconvergence analysis of a nonconforming finite element method for monotone semilinear elliptic optimal control problems

A nonconforming finite element method (FEM) is proposed for optimal control problems (OCPs) governed by monotone semilinear elliptic equations. The state and adjoint state are approximated by the nonconforming elements, and the control is approximated by the orthogonal projection of the adjoint state, respectively. Some global supercloseness and superconvergence estimates are achieved by making full use of the distinguish characters of this element, such as the interpolation equals to its Ritz projection, and the consistency error is 1 − ε ( is small enough) order higher than its interpolation error in the broken energy norm when the exact solution belongs to H^{3 − ε}(Ω). Finally, some numerical results are presented to verify the theoretical analysis.     

Online Ramsey theory for a triangle on -free graphs

Given a class of graphs and a fixed graph , the online Ramsey game for H on is a game between two players Builder and Painter as follows: an unbounded set of vertices is given as an initial state, and on each turn Builder introduces a new edge with the constraint that the resulting graph must be in , and Painter colors the new edge either red or blue. Builder wins the game if Painter is forced to make a monochromatic copy of at some point in the game. Otherwise, Painter can avoid creating a monochromatic copy of forever, and we say Painter wins the game. We initiate the study of characterizing the graphs such that for a given graph , Painter wins the online Ramsey game for on -free graphs. We characterize all graphs such that Painter wins the online Ramsey game for on the class of -free graphs, except when is one particular graph. We also show that Painter wins the online Ramsey game for on the class of -minor-free graphs, extending a result by Grytczuk, Hałuszczak, and Kierstead [Electron. J. Combin. 11 (2004), p. 60].     

The average degree of a subcubic edge-chromatic critical graph

A graph is here called 3- critical if , and for every edge of . The 3-critical graphs include (the Petersen graph with a vertex deleted), and subcubic graphs that are Hajós joins of copies of . Building on a recent paper of Cranston and Rabern, it is proved here that if is 3-critical and not nor a Hajós join of two copies of , then has average degree at least ; this bound is sharp, as it is the average degree of a Hajós join of three copies of .     

The size-Ramsey number of powers of paths

Given graphs and and a positive integer , say that is -Ramsey for , denoted , if every -coloring of the edges of contains a monochromatic copy of . The size-Ramsey number of a graph is defined to be . Answering a question of Conlon, we prove that, for every fixed , we have , where is the th power of the -vertex path (ie, the graph with vertex set and all edges such that the distance between and in is at most ). Our proof is probabilistic, but can also be made constructive.     

On the exact decomposition threshold for even cycles

A graph has a -decomposition if its edge set can be partitioned into cycles of length . We show that if , then has a -decomposition, and if , then has a -decomposition, where and (we assume is large and satisfies necessary divisibility conditions). These minimum degree bounds are best possible and provide exact versions of asymptotic results obtained by Barber, Kühn, Lo and Osthus. In the process, we obtain asymptotic versions of these results when is bipartite or satisfies certain expansion properties.     

On -connected graphs

A graph is called -connected if is -edge-connected and is -edge-connected for every vertex . The study of -connected graphs is motivated by a theorem of Thomassen [J. Combin. Theory Ser. A 110 (2015), pp. 67–78] (that was a conjecture of Frank [SIAM J. Discrete Math. 5 (1992), no. 1, pp. 25–53]), which states that a graph has a -vertex-connected orientation if and only if it is (2,2)-connected. In this paper, we provide a construction of the family of -connected graphs for even, which generalizes the construction given by Jordán [J. Graph Theory 52 (2006), pp. 217–229] for (2,2)-connected graphs. We also solve the corresponding connectivity augmentation problem: given a graph and an integer , what is the minimum number of edges to be added to make -connected. Both these results are based on a new splitting-off theorem for -connected graphs.     

Improper coloring of graphs on surfaces

A graph is -colorable if its vertex set can be partitioned into sets , such that for each , the subgraph of induced by has maximum degree at most . The Four Color Theorem states that every planar graph is -colorable, and a classical result of Cowen, Cowen, and Woodall shows that every planar graph is -colorable. In this paper, we extend both of these results to graphs on surfaces. Namely, we show that every graph embeddable on a surface of Euler genus is -colorable and -colorable. Moreover, these graphs are also -colorable and -colorable. We also prove that every triangle-free graph that is embeddable on a surface of Euler genus is -colorable. This is an extension of Grötzsch's Theorem, which states that triangle-free planar graphs are -colorable. Finally, we prove that every graph of girth at least 7 that is embeddable on a surface of Euler genus is -colorable. All these results are best possible in several ways as the girth condition is sharp, the constant maximum degrees cannot be improved, and the bounds on the maximum degrees depending on are tight up to a constant multiplicative factor.     

Half‐inverse problems for the quadratic pencil of the Sturm–Liouville equations with impulse

In this paper, we consider the inverse spectral problem for the impulsive Sturm–Liouville differential pencils on [0, π] with the Robin boundary conditions and the jump conditions at the point . We prove that two potentials functions on the whole interval and the parameters in the boundary and jump conditions can be determined from a set of eigenvalues for two cases: (i) the potentials given on and (ii) the potentials given on , where 0 < α < 1 , respectively. Inverse spectral problems, Sturm–Liouville operator, spectrum, uniqueness.     

The edge-subgraph poset of a graph and the edge reconstruction conjecture

We consider only finite simple graphs in this paper. Earlier we showed that many invariants of a graph can be computed from the isomorphism class of its partially ordered set of distinct unlabeled non-empty induced subgraphs, that is, the subgraphs themselves are not required. In this paper, we consider an analogous problem of reconstructing an arbitrary graph up to isomorphism from its abstract edge-subgraph poset , which we call the -reconstruction problem. We present an infinite family of graphs that are not -reconstructible and show that the edge reconstruction conjecture is true if and only if the graphs in the family are the only graphs that are not -reconstructible. Let be the set of all unlabeled graphs. Let denote the number of homomorphisms from to . Let be a bijection such that for all , we have . We conjecture that is the identity map. Our conjecture is motivated by the homomorphism cancellation results of Lovász. We prove that the conjecture stated above is weaker than the edge reconstruction conjecture.     

On the clique number of the square of a line graph and its relation to maximum degree of the line graph

In 1985, Erdős and Nešetřil conjectured that the square of the line graph of a graph , that is, , can be colored with colors. This conjecture implies the weaker conjecture that the clique number of such a graph, that is, , is at most . In 2015, Śleszyńska-Nowak proved that . In this paper, we prove that . This theorem follows from our stronger result that where .