图的二维带宽及其Laplacian特征值

图的二维带宽问题是将图G嵌入平面网格图，并使基于该嵌入的函数取得最优值（通常是最小值）。本文研究了图的二维带宽与其Laplacian特征值之间的关系。     

图的强乘积的带宽

本文讨论了由两个图的强乘积所导出的一些特殊图的带宽.     

路和圈上的卡氏乘积图的关联着色数(英文)

本文给出了路与路,路与圈的卡氏乘积图的关联着色数的完整刻画.对于圈与圈的卡氏乘积图的情形,也给出了其关联着色数的上界为乘积图的最大度加三,并且又给出了几类其关联着色数小于其最大度加三的圈与圈的卡氏乘积图类.     

二维带宽的浓度下界

二维带宽问题是确定图Ｇ在平面格子图中的一个嵌入，使最长的边尽可能短，本文研究若干个下界以及它们应用于带宽的估值。所有结果均建立在一种平面组合几何的方法之上，其中的浓度下界改进了文献（３）的结果。     

关于L∞—模距离的二维带宽问题

二维宽带问题是将图G嵌入平面格子图,使其最长的连边尽可能短,迄今为止,在平面格子图中考虑的距离为矩线距离,即L1－模距离,在本文中,我们研究在L∞－模距离意义下的二维带宽问题。     

张量乘积图的同构因子分解

本文讨论了两个可分图的张量乘积图的同构因子分解问题.给出了张量乘积图可同构因子分解的判定条件.     

关于笛卡尔乘积图的优美性

研究了笛卡尔乘积图Pm×Pn×P1的优美标号算法,并且给出了他们都是优美图的证明,同时推广了笛卡尔乘积图Pm×Pn是优美图的结论.     

图的割宽问题

本文建立了Ｈａｒｐｅｒ型割宽下界估计式，由此求出了轮形图Ｗｎ、完全二部图Ｋ（ｍ，ｎ）、圈幂Ｃｎｒ、格子图：Ｐｍ×Ｐｎ、Ｐｍ×Ｃｎ、Ｃｍ×Ｃｎ以及乘积图：Ｋｍ×Ｐｎ、Ｋｍ×Ｃｎ、Ｃｍｓ×Ｃｎｒ、Ｋｍ×Ｋｎ和强乘积图Ｐｍ　Ｐｎ的割宽。     

关于完全多部图的带宽和的一个注记

本文得到完全多部图的带宽和的一个递推方程；并由此给出带宽和的一些精确值．     

二次图构形的边搜索法及其Orlik-Solomon代数的上同调

本文研究了一类特殊的图构形,即二次图构形.首先,给出了弦图的边搜索法,用边搜索法可以决定弦图所对应的超平面构形中超平面的哪些排序使构形是二次均.其次,对二次图构形的Orlik-Solomon代数作为线性空间的维数进行了计算,得到了它的Poincare多项式的表达式.最后,对二次图构形Orlik-Solomon代数的上同调进行了研究,对边缘算子集中在秩为二的模元时,得到了二次图构形的Orlik-Solomon代数的上同调的维数计算公式.     

Ramsey numbers for bipartite graphs with small bandwidth

We estimate Ramsey numbers for bipartite graphs with small bandwidth and bounded maximum degree. In particular we determine asymptotically the two and three color Ramsey numbers for grid graphs. More generally, we determine asymptotically the two color Ramsey number for bipartite graphs with small bandwidth and bounded maximum degree and the three color Ramsey number for such graphs with the additional assumption that the bipartite graph is balanced.     

Representing products of manifolds by edge-coloured graphs: the boundary case

In this paper we generalize the construction - introduced by Gagliardi and Grasselli in the closed case - of a coloured-graph representing the product of two manifolds, starting by two coloured graphs representing the manifolds themselves, to the boundary case. In particular we study the genus of the graph product of low dimensional manifold ( resp. n-spheres ) with m-disks. Received September 28, 1998; in final form January 5, 2000 / Published online October 11, 2000     

Heat kernel bounds for the Laplacian on metric graphs of polygonal tilings

We obtain an upper heat kernel bound for the Laplacian on metric graphs arising as one skeletons of certain polygonal tilings of the plane, which reflects the one dimensional as well as the two dimensional nature of these graphs.     

Optimal acyclic edge colouring of grid like graphs

We determine the values of the acyclic chromatic index of a class of graphs referred to as d-dimensional partial tori. These are graphs which can be expressed as the cartesian product of d graphs each of which is an induced path or cycle. This class includes some known classes of graphs like d-dimensional meshes, hypercubes, tori, etc. Our estimates are exact except when the graph is a product of a path and a number of odd cycles, in which case the estimates differ by an additive factor of at most 1. Our results are also constructive and provide an optimal (or almost optimal) acyclic edge colouring in polynomial time.     

Bandwidth of bipartite permutation graphs in polynomial time

We give the first polynomial-time algorithm that computes the bandwidth of bipartite permutation graphs. Bandwidth is an NP-complete graph layout problem that is notorious for its difficulty even on small graph classes. For example, it remains NP-complete on caterpillars of hair length at most 3, a very restricted subclass of trees. Much attention has been given to designing approximation algorithms for computing the bandwidth, as it is NP-hard to approximate the bandwidth of general graphs with a constant factor guarantee. The problem is considered important even for approximation on restricted classes, with several distinguished results in this direction. Prior to our work, polynomial-time algorithms for exact computation of bandwidth were known only for caterpillars of hair length at most 2, chain graphs, cographs, and most interestingly, interval graphs.     

Laplace eigenvalues and bandwidth-type invariants of graphs

For (weighted) graphs several labeling properties and their relation to the eigenvalues of the Laplacian matrix of a graph are considered. Several upper and lower bounds on the bandwidth and other min-sum problems are derived. Most of these bounds depend on Laplace eigenvalues of the graphs. The results are applied in the study of bandwidth and the min-sums of random graphs, random regular graphs, and Kneser graphs. © John Wiley & Sons, Inc.     

图的笛卡儿积及字典式积的连通性

文章给出了两个图的笛卡儿积及字典式的积为最大边连通的、最大连通的、super-λ,super-κ及hyper-κ的充分条件,同时证明了其中一些条件也是必要的.此外,对这两种积的局部割集和广义割集的性质也进行了考虑.     

Notes on APN functions, semibiplanes and dimensional dual hyperovals

Two geometric objects, incidence graphs of semibiplanes and dimensional dual hyperovals, are respectively associated with APN and quadratic APN functions. From Proposition 2 (resp. Proposition 5), two APN (resp. quadratic APN) functions are CCZ (resp. extended affine) equivalent if and only if the associated graphs (resp. dimensional dual hyperovals) are isomorphic. The former graphs for almost bent functions are distance regular graphs by Proposition 4. The structures of automorphism groups of these geometric objects are investigated in Proposition 3 and Lemma 7. In particular, (Edel and Pott, Adv Math Commun 3:59–81 (2009), Question 2) is negatively answered.     

On Harpers' Result Concerning the Bandwidths of Graphs

In this paper, we improve the result by Harper on the lower bound of the bandwidth of connected graphs. In addition, we prove that considerating the interior boundary and the exterior boundary when estimating the bandwidth of connected graphs gives the same results.