图的树宽的分解定理

图的树宽问题是名的ＮＰ－困难问题。其分解原则在确定树宽的一般算法和特殊算法中有重要应用。本给出这方面的若干定理。     

完全图字典乘积的强半径和强直径

目前针对乘积图的强距离研究已经取得丰富成果,主要给出完全图字典乘积的强距离结果.基于字典乘积图与其因子图的关系,确定了两个完全图字典乘积的最小强半径;利用因子图与字典乘积图的顶点数的关系,得到完全图字典乘积的最大强直径和最大强半径的范围.除此之外,通过字典乘积的结合性,将字典乘积图的相关强距离结果进一步推广到多个完全图的字典乘积.     

树与偏k—的乘积的树宽

本文确宇了一棵树与一个k-连通偏k-树的乘积图的树宽。其中,偏k-树是一个树宽为k的图。     

完全图圈分解的一种新方法

本文给出完全图圈分解的一种新方法，设Ｋｎ（ｎ≥３）是一个ｎ阶完全图，我们得到下列结果：（１）若ｎ为奇数，Ｇ是ｎ阶群，并且｛ｏ（ｘ）│∈Ｇ，ｏ（ｘ）≥３｝＝｛ａ１，…，ａｔ｝，则Ｋｎ＝ｍ１Ｃａ１＋…＋ｍｔＣａｔ。（２）若ｎ为偶数，Ｇ是ｎ阶群，Ｔ＝｛ｘ│ｘ∈Ｇ，ｏ（ｘ）＝２｝＝｛ｘ０，ｘ１，ｙ１，…，ｘｓ，ｙｓ｝，ｏ（ｘｉｙｉ）＝ｂｉ，ｉ＝１，…，ｓ及｛ｏ（ｘ）│ｘ∈Ｇ，ｏ（ｘ）≥｝＝｛ａ１，…，ａｔ     

图的强乘积的带宽

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

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

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

有关完全图的图的紧性

双随机矩阵有许多重要的应用,紧图族可以看作是组合矩阵论中关于双随机矩阵的著名的Birkhoff定理的拓广,具有重要的研究价值.确定一个图是否紧图是个困难的问题,目前已知的紧图族尚且不多,给出了三个结果:任意多个完全图的不交并是紧图;圈C_3与圈C_n(n3)的不交并是非紧图;当n是大于等于3的奇数时,完全图K_n与图K_(n+1)的不交并是非紧图,其中图K_(n+1)是从完全图K_(n+1)删去一因子而得到的图.     

图的树宽的结构性结果

图G的树宽是使得G成为一个k-树的子图的最小整数k．树宽的算法性结果在图子式理论及有关领域中已有深入的研究．本文着重讨论其结构性结果，包括拓扑不变性、子式单调性、可分解性、刻画问题、与其它参数的关系及由此引伸出的性质．     

图的色多项式系数之和问题的研究

本文给出了任何简单图G(V,E)的色多项式P(G，λ)=∑i=1^vαiλ^i系数之和的公式：∑i=1^vαi={0ε≠0 1ε=0;并进行了证明，从而为判别一个多项式不是图的色多项式提供了一个必要条件．同时也分别给出了树、2-树、圈、轮图和完全图的色多项式系数绝对值之和的表达式．最后证明了任何简单连通图的色多项式系数绝对值之和∑i=1^v|αi|与边ε成正比，且必满足2^v-1≤∑i=1^v|αi|≤пi=1^vi．     

图乘积的星色数

星色数的概念最早是由Vince作为图的色数的推广而引入的.本文研究了两类图乘积G×H,G[H]的星色数.     

交叉数为2且因子图为路的笛卡尔积图

M.Kle??和J.Petrillová刻画了当G1为圈且cr (G1G2)=2时,因子图G1和G2所满足的充要条件.在此基础上,该文进一步刻画了在cr (G1G2)=2的前提下,当G1=P4,或者G1=P3且△(G2)=4时,因子图G2应满足的充要条件.     

Non-Cayley Vertex-Transitive Graphs of Order Twice the Product of Two Odd Primes

For a positive integer n, does there exist a vertex-transitive graph Γ on n vertices which is not a Cayley graph, or, equivalently, a graph Γ on n vertices such that Aut Γ is transitive on vertices but none of its subgroups are regular on vertices? Previous work (by Alspach and Parsons, Frucht, Graver and Watkins, Marusic and Scapellato, and McKay and the second author) has produced answers to this question if n is prime, or divisible by the square of some prime, or if n is the product of two distinct primes. In this paper we consider the simplest unresolved case for even integers, namely for integers of the form n = 2pq, where 2 < q < p, and p and q are primes. We give a new construction of an infinite family of vertex-transitive graphs on 2pq vertices which are not Cayley graphs in the case where p ≡ 1 (mod q). Further, if p ? 1 (mod q), p ≡ q ≡ 3(mod 4), and if every vertex-transitive graph of order pq is a Cayley graph, then it is shown that, either 2pq = 66, or every vertex-transitive graph of order 2pq admitting a transitive imprimitive group of automorphisms is a Cayley graph.     

k-树的补图的最小填充和树宽

一个图的最小填充问题是寻求边数最少的弦母图,一个图的树宽问题是寻求团数最小的弦母图,这两个问题分别在稀疏矩阵计算及图的算法设计中有非常重要的作用．一个k-树G的补图G称为k-补树．本文给出了k-补树G的最小填充数f(G) 及树宽TW(G)．     

关于完全t部图的色唯一性

设P(G,λ)是图的色多项式。如果对任意使P(G,λ)=P(H,λ)的图H都与G同构,则称图G是色唯一图.这里通过比较t 1色类的色划分数目,讨论了由Koh和Teo在文献[1]中提出的问题(若|ni-nj|≤2,当min(n1,n2,…,nt)充分大时,完全t部图K(n1,n2,…,nt)是否是色唯一图?)。改进了文献[5]中的结果。证明了若Σ1≤i≤ta2i=T,min{n a1,n a2,…,nt at,n-1}≥(T 1)/2,则K(n a1,n a2,…,n at)是色唯一图(其中ai是实数,n ai是正整数)。从而证明了若|ni-nj|≤k(i,j=1,2,…,t),min{n1,n2,…,nt}≥tk2/8 1,则K(n1,n2,…,nt)是色唯一图。     

关于完全t部图K(n1,n2,…,nt)的色唯一性

设P（G，λ）是图G的色多项式，如果对任意使P（G，λ）=P（H，λ）的图H都与G同构，则称G是色唯一图。这里通过比较图的特征子图的个数，讨论了由Koh和Teo在文献[1]中提出的问题（若｜ni-nj｜≤2，1≤i，j≤t且min{n1，n2，…，nt}充分大，K（n1，n2，…，nt）是否为色唯一图？）。证明了，若｜ni—nj｜≤2且t↑∑↑i=1 ni〉t^2/2＋t√t-1，则K（n1，n2，…，nt）是色唯一图；若αi=0或k，t↑∑↑i=1 n＋αi〉t^2k^2/8＋｜tk｜/2√t-1，则K（n＋α1，n＋α2，…，n＋αt）是色唯一图。其条件比文献[4]中的条件较好一些。     

On a Decomposition of Complete Graphs

It is shown, among other results, that for any prime power q, the complete graph on 1+q+q ²+q ³ vertices can be decomposed into a union of 1+q Siamese Strongly Regular Graphs S R G(1+q+q ²+q ³,q+q ²,q–1,q+1) sharing 1+q ² cliques of size 1+q. Acknowledgments.The authors are indebted to a referee for a very extensive report and for many suggestions which improved the presentation of the paper tremendously.AMS Subject Numbers: 05B05, 05B20, 05E30This work was completed while the first author was on sabbatical leave visiting Institute for studies in theoretical Physics and Mathematics, (IPM), in Tehran, Iran. Support and hospitality is appreciated. Supported by an NSERC operating grant.