Self-complementary magic squares of doubly even orders

A magic square $M$ in which the entries consist of consecutive integers from $1,2,\dots ,n^2$ is said to be self-complementary of order$n$ if the resulting square obtained from $M$ by replacing each entry $i$ by $n^2+1?i$ is equivalent to $M$ (under rotation or reflection). We present a new construction for self-complementary magic squares of order $n$ for each $n\ge 4$, where $n$ is a multiple of $4$.     

两类图的(d,1)-全标号

主要讨论了W_n与C_m的笛卡尔积和均衡完全r-部图K_r(n)的(d,1)-全标号,并得出了(d,1)-全数λ_d~T(W_n□C_m)和λ_d~T(K_(r(n)))的确切值.     

一种非刚性医学图像点匹配方法

提出了一种非刚性点匹配的算法并把其运用于医学图像配准．该算法采用信号滤波的方法来获得点集间的匹配信息，并运用松弛标记法将各点邻域关系对模糊的匹配信息进行迭代获得明确的匹配关系．在此基础上，利用高斯径向基函数来描述点模式间的弹性形变，在基本的迭代框架下实现问题的求解．实验结果显示在形变程度为5％、出格点比率50％和噪声标准差为5％的情况下该算法的匹配误差能控制在0．13以下，表明了该算法的鲁棒性和有效性，较好地解决了医学非刚性形变的点匹配问题．     

A class of antimagic join graphs

A labeling f of a graph G is a bijection from its edge set E(G) to the set {1, 2, . . . , |E(G)|}, which is antimagic if for any distinct vertices x and y, the sum of the labels on edges incident to x is different from the sum of the labels on edges incident to y. A graph G is antimagic if G has an f which is antimagic. Hartsfield and Ringel conjectured in 1990 that every connected graph other than K 2 is antimagic. In this paper, we show that if G 1 is an n-vertex graph with minimum degree at least r, and G 2 is an m-vertex graph with maximum degree at most 2r-1 (m ≥ n), then G1 ∨ G2 is antimagic.     

On L(d,1)-labelings of graphs

Given a graph G and a positive integer d, an L(d,1)-labeling of G is a function f that assigns to each vertex of G a non-negative integer such that if two vertices u and v are adjacent, then |f(u)−f(v)|d; if u and v are not adjacent but there is a two-edge path between them, then |f(u)−f(v)|1. The L(d,1)-number of G, λ_d(G), is defined as the minimum m such that there is an L(d,1)-labeling f of G with f(V){0,1,2,…,m}. Motivated by the channel assignment problem introduced by Hale (Proc. IEEE 68 (1980) 1497–1514), the L(2,1)-labeling and the L(1,1)-labeling (as d=2 and 1, respectively) have been studied extensively in the past decade. This article extends the study to all positive integers d. We prove that λ_d(G)Δ²+(d−1)Δ for any graph G with maximum degree Δ. Different lower and upper bounds of λ_d(G) for some families of graphs including trees and chordal graphs are presented. In particular, we show that the lower and the upper bounds for trees are both attainable, and the upper bound for chordal graphs can be improved for several subclasses of chordal graphs.     

截断切割问题的数学模型

本文就 1 997年全国大学生数学建模竞赛中 B题所给的截断切割问题建立了一个数学模型 ,并给出了求解的方法 .     

龙图的奇优美性

根据复杂网络研究的需要,定义(k,m)-奇优美龙图和一致(k,m)-龙图作为复杂网络的模型.这些龙图的奇优美性得到研究,其中证明方法可算法化.     

Proximity‐preserving labeling schemes

This article considers informative labeling schemes for graphs. Specifically, the question introduced is whether it is possible to label the vertices of a graph with short labels in such a way that the distance between any two vertices can be inferred from inspecting their labels. A labeling scheme enjoying this property is termed a proximity‐preserving labeling scheme. It is shown that, for the class of n‐vertex weighted trees with M‐bit edge weights, there exists such a proximity‐preserving labeling scheme using O(M log n + log²n) bit labels. For the family of all n‐vertex unweighted graphs, a labeling scheme is proposed that using O(log² n · κ · n^1/κ) bit labels can provide approximate estimates to the distance, which are accurate up to a factor of In particular, using O(log³n) bit labels, the scheme can provide estimates accurate up to a factor of $\sqrt{2 \log n}$. (For weighted graphs, one of the log n factors in the label size is replaced by a factor logarithmic in the network's diameter.) © 2000 John Wiley & Sons, Inc. J Graph Theory 33: 167–176, 2000     

Boundary labeling: Models and efficient algorithms for rectangular maps

We introduce boundary labeling, a new model for labeling point sites with large labels. According to the boundary-labeling model, labels are placed around an axis-parallel rectangle that contains the point sites, each label is connected to its corresponding site through a polygonal line called leader, and no two leaders intersect. Although boundary labeling is commonly used, e.g., for technical drawings and illustrations in medical atlases, this problem has not yet been studied in the literature. The problem is interesting in that it is a mixture of a label-placement and a graph-drawing problem.

In this paper we investigate several variants of the boundary-labeling problem. We consider labels of identical or different size, straight-line or rectilinear leaders, fixed or sliding ports for attaching leaders to sites and attaching labels to one, two or all four sides of the bounding rectangle. For any variant of the boundary labeling model, we aim at highly esthetical placements of labels and leaders. We present simple and efficient algorithms that minimize the total leader length or, in the case of rectilinear leaders, the total number of bends.     

几类特殊图的优美性

证明了对任意大于1的自然数n,p,当m≥2p＋2时,非连通图Fm∪Kn,p和Fm,2 m∪Kn,p是优美图;当m≥3时,图Fm∪St（n）是优美图;当m≥4,图Fm,2 m∪St（n）和Fm,2 m∪Gr是优美图.