Colouring series-parallel graphs

We establish a minimax formula for the chromatic index of series-parallel graphs; and also prove the correctness of a greedy algorithm for finding a vertex-colouring of a series-parallel graph.     

Boxicity of series-parallel graphs

We show that there exist series-parallel graphs with boxicity 3.     

Combinatorial problems on series-parallel graphs

This paper outlines the results and motivation of the paper [1], in which we showed, in a unified manner, that there exist linear time algorithms for many combinatorial problems defined on the class of series-parallel graphs.     

系列平行图SHMeredith图的关联着色

图的关联着色是从关联集到颜色集的一个映射,使得关联集中任何两个相邻的关联都具有不同的像.确定了Meredith图的关联色数,证明了对任意系列平行图都存在一个(Δ 2,2)-关联着色.     

List total colorings of series-parallel graphs

A total coloring of a graph G is a coloring of all elements of G, i.e., vertices and edges, in such a way that no two adjacent or incident elements receive the same color. Let L(x) be a set of colors assigned to each element x of G. Then a list total coloring of G is a total coloring such that each element x receives a color contained in L(x). The list total coloring problem asks whether G has a list total coloring. In this paper, we first show that the list total coloring problem is NP-complete even for series-parallel graphs. We then give a sufficient condition for a series-parallel graph to have a list total coloring, that is, we prove a theorem that any series-parallel graph G has a list total coloring if |L(v)|min{5,Δ+1} for each vertex v and |L(e)|max{5,d(v)+1,d(w)+1} for each edge e=vw, where Δ is the maximum degree of G and d(v) and d(w) are the degrees of the ends v and w of e, respectively. The theorem implies that any series-parallel graph G has a total coloring with Δ+1 colors if Δ4. We finally present a linear-time algorithm to find a list total coloring of a given series-parallel graph G if G satisfies the sufficient condition.     

A new graceful labeling for pendant graphs

A graceful labeling of a graph G with q edges is an injective assignment of labels from {0, 1, . . . , q} to the vertices of G so that when each edge is assigned the absolute value of the difference of the vertex labels it connects, the resulting edge labels are distinct. A labeling of the first kind for coronas ${C_n \odot K_1}$ occurs when vertex labels 0 and q = 2n are assigned to adjacent vertices of the n-gon. A labeling of the second kind occurs when q = 2n is assigned to a pendant vertex. Previous research has shown that all coronas ${C_n \odot K_1}$ have a graceful labeling of the second kind. In this paper we show that all coronas ${C_n \odot K_1}$ with ${n \equiv 3, 4\, {\rm (mod\, 8)}}$ also have a graceful labeling of the first kind.     

A note on compact graphs

An undirected simple graph G is called compact iff its adjacency matrix A is such that the polytope S(A) of doubly stochastic matrices X which commute with A has integral-valued extremal points only. We show that the isomorphism problem for compact graphs is polynomial. Furthermore, we prove that if a graph G is compact, then a certain naive polynomial heuristic applied to G and any partner G′ decides correctly whether G and G′ are isomorphic or not. In the last section we discuss some compactness preserving operations on graphs.     

系列平行图上带时间约束的Steiner最小树问题

对一类特殊系列平行图上带有时间约束的Steiner最小树问题,证明了其复杂性为NPC,并给出了一个完全多项式时间近似方案.     

On the two-dimensional orthogonal drawing of series-parallel graphs

It has been known that every planar 4-graph has a 2-bend 2-D orthogonal drawing, with the only exception being the octahedron, every planar 3-graph has a 1-bend 2-D orthogonal drawing with the only exception being K₄, and every outerplanar 3-graph with no triangles has a 0-bend 2-D orthogonal drawing. We show in this paper that every series-parallel 4-graph has a 1-bend 2-D orthogonal drawing.     

A compact difference scheme for the fractional diffusion-wave equation

This article is devoted to the study of high order difference methods for the fractional diffusion-wave equation. The time fractional derivatives are described in the Caputo’s sense. A compact difference scheme is presented and analyzed. It is shown that the difference scheme is unconditionally convergent and stable in _L∞$L_{\infty }$-norm. The convergence order is O(τ^3-α+h⁴)$O({\tau }^{3-\alpha }+h^4)$. Two numerical examples are also given to demonstrate the theoretical results.     

On compact median graphs

A median graph is called compact if it does not contain an isometric ray. This property is shown to be equivalent to the finite intersection property for convex sets. We show that a compact median graph contains a finite cube that is fixed by all of its automorphisms, and that each family of commuting endomorphisms of a compact median graph fixes a common cube. © 1996 John Wiley & Sons, Inc.     

Localized and compact data-structure for comparability graphs

We show that every comparability graph of any two-dimensional poset over n elements (a.k.a. permutation graph) can be preprocessed in O(n) time, if two linear extensions of the poset are given, to produce an O(n) space data-structure supporting distance queries in constant time. The data-structure is localized and given as a distance labeling, that is each vertex receives a label of O(logn) bits so that distance queries between any two vertices are answered by inspecting their labels only. This result improves the previous scheme due to Katz, Katz and Peleg [M. Katz, N.A. Katz, D. Peleg, Distance labeling schemes for well-separated graph classes, Discrete Applied Mathematics 145 (2005) 384-402] by a log n factor.As a byproduct, our data-structure supports all-pair shortest-path queries in O(d) time for distance-d pairs, and so identifies in constant time the first edge along a shortest path between any source and destination.More fundamentally, we show that this optimal space and time data-structure cannot be extended for higher dimension posets. More precisely, we prove that for comparability graphs of three-dimensional posets, every distance labeling scheme requires Ω(n^1/3) bit labels.     

A second-order fast compact scheme with unequal time-steps for subdiffusion problems

Numerical Algorithms - In consideration of the initial singularity of the solution, a temporally second-order fast compact difference scheme with unequal time-steps is presented and analyzed for...     

A linearized compact difference scheme for an one-dimensional parabolic inverse problem

The parabolic equation with the control parameter is a class of parabolic inverse problems and is nonlinear. While determining the solution of the problems, we shall determinate some unknown control parameter. These problems play a very important role in many branches of science and engineering. The article is devoted to the following parabolic initial-boundary value problem with the control parameter: ∂u/∂t=∂²u/∂x²+p(t)u+?(x,t),0<x<1,0<t?T$\mathrm{\partial }u/\mathrm{\partial }t={\mathrm{\partial }}^{2}u/\mathrm{\partial }{x}^2+p(t)u+?(x\text{,}t)\text{,}0<x<1\text{,}0<t?T$ satisfying u(x,0)=f(x),0<x<1$u(x\text{,}0)=f(x)\text{,}0<x<1$; u(0,t)=_g0(t)$u(0\text{,}t)=g_0(t)$, u(1,t)=_g1(t)$u(1\text{,}t)=g_1(t)$, u(x^∗,t)=E(t),0?t?T$u(x^{\ast }\text{,}t)=E(t)\text{,}0?t?T$ where ?(x,t),f(x),_g0(t),_g1(t)$?(x\text{,}t)\text{,}f(x)\text{,}{g}_0(t)\text{,}{g}_1(t)$ and E(t)$E(t)$ are known functions, u(x,t)$u(x\text{,}t)$ and p(t)$p(t)$ are unknown functions. A linearized compact difference scheme is constructed. The discretization accuracy of the difference scheme is two order in time and four order in space. The solvability of the difference scheme is proved. Some numerical results and comparisons with the difference scheme given by Dehghan are presented. The numerical results show that the linearized difference scheme of this article improve the accuracy of the space and time direction and shorten computation time largely. The method in this article is also applicable to the two-dimensional inverse problem.     

A second-order compact difference scheme for the fourth-order fractional sub-diffusion equation

In this paper, the Euler–Maruyama (EM) method with random variable stepsize is studied to reproduce the almost sure stability of the true solutions of stochastic differential equations. Since the choice of the time step is based on the current state of the solution, the time variable is proved to be a stopping time. Then the semimartingale convergence theory is employed to obtain the almost sure stability of the random variable stepsize EM solution. To our best knowledge, this is the first paper to apply the random variable stepsize (with clear proof of the stopping time) to the analysis of the almost sure stability of the EM method.     

A three level linearized compact difference scheme for the Cahn-Hilliard equation

This article is devoted to the study of high order accuracy difference methods for the Cahn-Hilliard equation.A three level linearized compact difference scheme is derived.The unique solvability and unconditional convergence of the difference solution are proved.The convergence order is O(τ 2 + h 4 ) in the maximum norm.The mass conservation and the non-increase of the total energy are also verified.Some numerical examples are given to demonstrate the theoretical results.