Hamiltonian cycles in bipartite quadrangulations on the torus

In this article, we shall prove that every bipartite quadrangulation G on the torus admits a simple closed curve visiting each face and each vertex of G exactly once but crossing no edge. As an application, we conclude that the radial graph of any bipartite quadrangulation on the torus has a hamiltonian cycle. Copyright © 2011 Wiley Periodicals, Inc. J Graph Theory 69:143‐151, 2012     

Approximation on the sphere using radial basis functions plus polynomials

In this paper we analyse a hybrid approximation of functions on the sphere by radial basis functions combined with polynomials, with the radial basis functions assumed to be generated by a (strictly) positive definite kernel. The approximation is determined by interpolation at scattered data points, supplemented by side conditions on the coefficients to ensure a square linear system. The analysis is first carried out in the native space associated with the kernel (with no explicit polynomial component, and no side conditions). A more refined error estimate is obtained for functions in a still smaller space. Numerical calculations support the utility of this hybrid approximation.      

关于D(F_n)和D(W_n)的点关联邻点可区别全色数

对简单图G(V,E),f是从V(G)∪E(G)到{1,2,…,k}的映射,k是自然数,若满足:1)uv,uω-∈E(G),v≠,-ωf(uv)≠f (uω-);2)uv∈E G,C(u)≠C(v).则称f是G的点关联邻点可区别全染色法,其所用到的最少颜色数称为图G的点关联邻点可区别全色数.这里C(u)=f(u)∪f(uv)uv∈E(G).得到了扇和轮的倍图的点关联邻点可区别全色数.     

N‐flips in even triangulations on the sphere

A triangulation is said to be even if each vertex has even degree. For even triangulations, define the N‐flip and the P2‐flip as two deformations preserving the number of vertices. We shall prove that any two even triangulations on the sphere with the same number of vertices can be transformed into each other by a sequence of N‐ and P2‐flips. © 2005 Wiley Periodicals, Inc. J. Graph Theory     

Boundary integral equations on the sphere with radial basis functions: error analysis

Radial basis functions are used to define approximate solutions to boundary integral equations on the unit sphere. These equations arise from the integral reformulation of the Laplace equation in the exterior of the sphere, with given Dirichlet or Neumann data, and a vanishing condition at infinity. Error estimates are proved. Numerical results supporting the theoretical results are presented.     

Halin图$Q$-谱半径的最大值

The Q-index of a graph G is the largest eigenvalue q(G) of its signless Laplacian matrix Q(G). In this paper, we prove that the wheel graph W_n = K_1 ∨C_(n-1)is the unique graph with maximal Q-index among all Halin graphs of order n. Also we obtain the unique graph with second maximal Q-index among all Halin graphs of order n.     

Tight Lower Bounds on the Size of a Maximum Matching in a Regular Graph

In this paper we study tight lower bounds on the size of a maximum matching in a regular graph. For k ≥3, let G be a connected k-regular graph of order n and let α′(G) be the size of a maximum matching in G. We show that if k is even, then , while if k is odd, then . We show that both bounds are tight. Research supported in part by the South African National Research Foundation and the University of KwaZulu-Natal.     

Regularized traces of a perturbed laplace-beltrami operator on the unit two-dimensional sphere

The paper contains formulas for regularized traces of the Laplace-Beltrami operator on the unit sphere under perturbation determined by a bounded complex-valued potential and a sufficiently complete justification of these formulas. Translated fromMatematicheskie Zametki, Vol. 67, No. 5, pp. 702–705, May, 2000.     

An overlapping additive Schwarz preconditioner for interpolation on the unit sphere with spherical radial basis functions

The problem of interpolation of scattered data on the unit sphere has many applications in geodesy and Earth science in which the sphere is taken as a model for the Earth. Spherical radial basis functions provide a convenient tool for constructing the interpolant. However, the underlying linear systems tend to be ill-conditioned. In this paper, we present an additive Schwarz preconditioner for accelerating the solution process. An estimate for the condition number of the preconditioned system will be discussed. Numerical experiments using MAGSAT satellite data will be presented.     

On the Determination Problem for P 4-Transformation of Graphs

We prove that the P ₄-transformation is one-to-one on the set of graphs with minimum degree at least 3, and if graphs G and G ^' have minimum degree at least 3 then any isomorphism from the P ₄-graph P ₄(G) to the P ₄-graph P ₄(G ^') is induced by a vertex-isomorphism from G to G ^' unless G and G ^' both belong to a special family of graphs. Supported by NSFC, PCSIRT and the “973” program.     

图的倍图与补倍图

计算机科学数据库的关系中遇到了可归为倍图或补倍图的参数和哈密顿圈的问题．对简单图C,如果V（D（G））：V（G）∪V（G′）E（D（G））=E（C）∪E（C″）U{vivj′｜vi∈V（G）,Vj′∈V（G′）且vivj∈E（G））那么,称D（C）是C的倍图,如果V（D（G））=V（C）∪V（G′）,E（D（C））：E（C）∪E（G′）∪{vivj′}vi∈V（G）,vj′∈V（G’）and vivj∈（G））,称D（C）是G的补倍图,这里G′是G的拷贝．本文研究了D（G）和D的色数,边色数,欧拉性,哈密顿性和提出了D（G） 的边色数是D（G）的最大度等公开问题．     

两类Mycielski图及一些平面图的均匀全色数

对于图G(V,E)的正常k-全染色φ称为G(V,E)的k-均匀全染色,当且仅当任意两个色类中的元素总数至多相差1.xvee(G)=m in{k存在图G的一个k-均匀全染色}称为G的均匀全色数.本文得到了两类M ycielsk i图及圈,轮图和扇形的均匀全色数.     

Enumerating the orientable 2‐cell imbeddings of complete bipartite graphs

A formula is developed for the number of congruence classes of 2‐cell imbeddings of complete bipartite graphs in closed orientable surfaces. © 1999 John Wiley & Sons, Inc. J Graph Theory 30: 77–90, 1999     

S_n+W_n的邻点强可区别全色数

设G(V,E)是阶数不小于3的简单连通图,k是自然数,f是从V(G)∪E(G)到1,2,…,k的映射,满足:对任意的uv∈E(G),f(u)≠f(v),f(u)≠f(uv)≠f(v);对任意的uv,uw∈E(G)(v≠w),f(uv)≠f(uw);对任意的uv∈E(G),C(u)≠C(v),其中C(u)={f(u)}∪{f(v)uv∈E(G)}∪{f(uv)uv∈E(G)},则称f是图G的一个邻点强可区别的全染色法,简记作k-AVSDTC,且称χast(G)=min{k G的所有k-AVSDTC}为G的邻点强可区别的全色数.得到了星与轮联图的邻点强可区别的全色数.     

W6*Sn的交叉数

早在20世纪50年代,Zarankiewicz 猜想完全2-部图K_{m,n}(m\leq n)的交叉数为\lfloor\frac{m}{2}\rfloor\times \lfloor\frac{m-1}{2}\rfloor\times\lfloor\frac{n}{2}\rfloor\times\lfloor\frac{n-1}{2}\rfloor (对任意实数x,\lfloor x\rfloor表示不超过x的最大整数). 目前这一猜想的正确性只证明了当m\leq6时成立. 假定著名的Zarankiewicz的猜想对m=7的情形成立,确定了6-轮W_{6}与星S_{n}的笛卡尔积图的交叉是 cr(W_{6}\times S_{n})=9\lfloor\frac{n}{2}\rfloor\times\lfloor\frac{n-1}{2}\rfloor+2n+5\lfloor\frac{n}{2}\rfloor.     

Y‐rotation in k‐minimal quadrangulations on the projective plane

Let G be a quadrangulation on a surface, and let f be a face bounded by a 4‐cycle abcd. A face‐contraction of f is to identify a and c (or b and d) to eliminate f. We say that a simple quadrangulation G on the surface is k‐minimal if the length of a shortest essential cycle is k(≥3), but any face‐contraction in G breaks this property or the simplicity of the graph. In this article, we shall prove that for any fixed integer k≥3, any two k‐minimal quadrangulations on the projective plane can be transformed into each other by a sequence of Y‐rotations of vertices of degree 3, where a Y‐rotation of a vertex v of degree 3 is to remove three edges vv₁, vv₃, vv₅ in the hexagonal region consisting of three quadrilateral faces vv₁v₂v₃, vv₃v₄v₅, and vv₅v₆v₁, and to add three edges vv₂, vv₄, vv₆. Actually, every k‐minimal quadrangulation (k≥4) can be reduced to a (k?1)‐minimal quadrangulation by the operation called Möbius contraction, which is mentioned in Lemma 13. © 2011 Wiley Periodicals, Inc. J Graph Theory 69: 301–313, 2012     

关于图的一般邻点可区别边染色

给出了轮图W_n、扇图F_n、风车图K_2~t、图D_(m,4)、图D_(m,n)、齿轮图W_n的一般邻点可区别色指标.     

图的双控制的一些新结果

图G=(V,E)的每个顶点控制它的闭邻域的每个顶点.S是一个顶点子集合,如果G的每一个顶点至少被S中的两个顶点控制,则称S是G的一个双控制集.把双控制集的最小基数称为双控制数,记为dd(G).本文探讨了双控制数和其它控制参数的一些新关系,推广了[1]的一些结果.并且给出了双控制数的Nordhaus-Gaddum类型的结果.