关于图的带宽的一些定理

引言 设G是有N个顶点的图,V(G)是G的全体顶点的集合,称任一个1—1对应的函数f:V(G)→{1,2,…,N}为G(或V(G))上的一个标号,记 B(f)=max{f(u)-f(v):u与v是G上相邻顶点},称B(f)为标号f的带宽.又记 B(G)=min{B(f):f是V(G)上的标号},称 B(G)为图G的带宽.若f是V(G)上的一个标号且B(f)=B(G),则称f为V(G)     

关于乘积图的二维带宽问题

给出一般乘积图的二维带宽的界，并解决一类乘积图的二维带宽问题．最后给出完全ｋ部图的二维带宽。     

图的弱准带宽和前沿带宽

引入图的弱准带宽和前沿带宽,并将其应用于研究图的带宽、拓扑带宽、填充、侧廓、路宽和树宽等.     

关于图与补图的带宽的一个简单证明

关于图与补图的带宽,P.Z.Chinn,F.R.K.Chung,P.Erd?s和R.L.Graham证明了B(G)+B(G)≥n-2.本文给出一个简单证明.     

图带宽的若干刻划

本文研究图的带宽的若干等价刻划以及相关的理论结果。     

图的循环带宽和

Abstract. Let G be a simple graph. The cyclic bandwidth sum problem is to determine a labeling of graph G in a cycle such that the total length of edges is as small as possible. In this paper, some upper and lower bounds on cyclic bandwidth sum of graphs are studied.     

图带宽和与其对偶超图带宽和的关系

设H=（E1,E2,…,Em）是集合X上的一个超图,一个1-1映射f:X→{1,2,…,|X|}称为H的一个标号,对H的任一标号f,BS（H,f）=∑(E∈H)max{|f(u)-f(v)|;u,v∈E}称为超图H的关于标号f的带宽和BS(H)=min{BS(H,f)|f是超图H的标号|}称为H的带宽和．论文研究图带宽和与其对偶超图的带宽和这两个参数间的关系．     

图的强乘积的带宽

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

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

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

图的带宽问题的Harper方法

本文讨论特殊图的带宽问题。在这方面,Harper定理是具有开创性的。随后的研究又有所发展,以至形成一种普遍的研究方法。§1.Harper定理的推广给定一个无向图G=(V,E),其中|V|=n。任意一个双射f:V→{1,2,…,n}都称为一个“标号”。对标号f,所有边两端的最大标号差     

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

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

关于带宽极值问题的一些结果

本文研究的问题是确定f(p,B）的值，也就是给定顶点数p和带宽B，求满足最大度不超过B的连通图的最小边数，本文给出了一些f(p,B）的值及相应极图。     

图加一条边后的带宽和

令$BS(G,f)=\sum\limits_{uv\in E(G)}|f(u)-f(v)|$, 其中$f$为$V(G)\rightarrow\{1,2,\cdots,|V(G)|\}$的双射, 并称$BS(G)=\min\limits_{f}BS(G,f)$为图$G$的带宽和. 讨论顶点数为$n$的简单图$G$加上一条边$e\in\overline{E(G)}$后, 带宽和$BS(G+e)$与$BS(G)$的关系, 得其关系式$BS(G)+1\leq BS(G+e)\leq BS(G)+n-1$. 并证明此不等式中等号可取到, 即存在图$G_{1}$和$G_{2}$使得$BS(G_{1}+e)=BS(G_{1})+1$, $BS(G_{2}+e)=BS(G_{2})+n-1$.     

关于带宽极值问题的两个结果

本文研究的问题是确定ｅ＊（ｐ,Ｂ）的值,也就是确定顶点数为ｐ、带宽为Ｂ的连通图Ｇ的最小边数,本文给出当Ｂ＝ｐ＋３／２和Ｂ＝ｐ／２＋２时的精确结果。     

关于等高k-毛虫树的带宽

图的带宽问题是图论的一个重要课题。然而 ,即使对毛长不等的单毛虫树 ,其带宽问题也是NP_完全的。利用Chv偄ｔａｌ的直径型带宽下界为工具 ,我们可以确定等高k_毛虫树的带宽     

球面上n条经线所构成的图的带宽

设G是个图,V(G)是G的全体顶点的集合,|V(G)|=p.称任一个1—1对应的函数f:V(G)→{1,2,…,p}为V(G)上的一个标号。记 B(f)=max{f(u)-f(v):u与v是G上相邻顶点},称B(f)为标号f的带宽。记 B(G)=min{B(f):f是V(G)上的标号}, 称B(G)为图G的带宽。若f是V(G)上的一个标号且B(f)=B(G),则称f为V(G)上的最佳标号。如何计算一个给定的图的带宽?这是一个很有实际意义而引人注目的问题。但一般的图的带宽的计算往往十分困难,只有几种较为简单的图的带宽已经求出。例如,已     

带宽等于最小度的图的最小边数

本文对带宽等于最小度的图的边数极值问题进行了研究,主要结果如下:对任意给定的正整数n及r(r相似文献   

乘积图Tl_1l_2l_3×P_n的带宽

求一般图甚至求一般树的带宽问题已被证明属于NP-完全问题。目前仍只有一些较简单的图类的带宽已被求出,其中有一些是关于乘积图的。设P_n,C_n及K_n分别为n个顶点的路,圈及完全图,J.Chvtalov等人求出了P_m×P_n及P_m×C_n的带宽,李乔等人求出了C_m×C_n的带宽,罗海鹏求出了K_m×P_n及K_m×C_n的带宽,麦结华等人求出了K_m×K_n的带宽。更复杂一些的图的乘积的带宽问题则仍难于解决。因此,我们尝试解决一个较简单的树T_(ι_1ι_2ι_3)与路P_n的乘积的带宽的问题。     

关于图的运算与图的Pfaffian性

关于一般的图的完美匹配计数的问题已证实是NP-hard问题.但Pfaffian图的完美匹配计数问题(以及其它相关问题)却能够在多项式时间内解决.由此可见图的Pfaffian性的重要性.在这篇文章中,我们研究了若干种影响图的Pfaffian性的运算.