共查询到20条相似文献,搜索用时 558 毫秒
1.
3.
本文给出了路与路,路与圈的卡氏乘积图的关联着色数的完整刻画.对于圈与圈的卡氏乘积图的情形,也给出了其关联着色数的上界为乘积图的最大度加三,并且又给出了几类其关联着色数小于其最大度加三的圈与圈的卡氏乘积图类. 相似文献
4.
5.
二维宽带问题是将图G嵌入平面格子图,使其最长的连边尽可能短,迄今为止,在平面格子图中考虑的距离为矩线距离,即L1-模距离,在本文中,我们研究在L∞-模距离意义下的二维带宽问题。 相似文献
6.
7.
8.
本文建立了Harper型割宽下界估计式,由此求出了轮形图Wn、完全二部图K(m,n)、圈幂Cnr、格子图:Pm×Pn、Pm×Cn、Cm×Cn以及乘积图:Km×Pn、Km×Cn、Cms×Cnr、Km×Kn和强乘积图Pm Pn的割宽。 相似文献
9.
10.
11.
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. 相似文献
12.
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 相似文献
13.
René Pröpper 《Semigroup Forum》2013,86(2):262-271
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. 相似文献
14.
15.
Optimal acyclic edge colouring of grid like graphs 总被引:1,自引:0,他引:1
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. 相似文献
16.
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. 相似文献
17.
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. 相似文献
18.
文章给出了两个图的笛卡儿积及字典式的积为最大边连通的、最大连通的、super-λ,super-κ及hyper-κ的充分条件,同时证明了其中一些条件也是必要的.此外,对这两种积的局部割集和广义割集的性质也进行了考虑. 相似文献
19.
Satoshi Yoshiara 《Designs, Codes and Cryptography》2010,56(2-3):197-218
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. 相似文献
20.
Kin-Keung Poon 《Czechoslovak Mathematical Journal》2004,54(2):401-405
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. 相似文献