图的树宽的分解定理

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

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

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

树与偏k—的乘积的树宽

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

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

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

图的强乘积的带宽

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

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

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

图的树宽的结构性结果

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

有关完全图的图的紧性

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

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

本文给出了任何简单图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．     

完全图的素圈因子分解

图的因子理论是图论研究中最活跃的课题之一.其中心问题是把一个图分解成具有给定性质的因子.     

Treewidth of Cartesian Products of Highly Connected Graphs

The following theorem is proved: for all k‐connected graphs G and H each with at least n vertices, the treewidth of the cartesian product of G and H is at least . For , this lower bound is asymptotically tight for particular graphs G and H. This theorem generalizes a well‐known result about the treewidth of planar grid graphs.     

Parameters Tied to Treewidth

Treewidth is a graph parameter of fundamental importance to algorithmic and structural graph theory. This article surveys several graph parameters tied to treewidth, including separation number, tangle number, well‐linked number, and Cartesian tree product number. We review many results in the literature showing these parameters are tied to treewidth. In a number of cases we also improve known bounds, provide simpler proofs, and show that the inequalities presented are tight.     

图的字典序积和自同态幺半群

Ｆ．Ｈａｒａｒｙ￣［１］和Ｇ．Ｓａｂｉｄｕｓｓｉ￣［２］考虑过图Ｘ和ｙ的字典序积Ｘ［Ｙ］的自同构群ＡｕｔＸ［Ｙ］与它们各自的自同构群的圈积ＡｕｔＸ［ＡｕｔＹ］的关系，并给出了两者相等的一种刻划．在本文，我们考虑更广意义上的问题，即Ｘ［Ｙ］的自同态幺半群ＥｎｄＸ［Ｙ］与各自的自同态幺半群的圈积ＥｎｄＸ［ＥｎｄＹ］的关系，也给出了两者相等的一种刻划，同时得到了下面结果：如果Ｘ和Ｙ都是不含Ｋ＿３导出子图的连通图，且其中之一图有奇数围长，那么ＥｎｄＸ［Ｙ］＝ＥｎｄＸ［ＥｎｄＹ］．     

完全多部图与完全图Kronercker积的点参数研究

若G1和G2是两个图,G1和G2的Kronecker图定义为V (G1×G2)= V (G1) × V (G2 E(G1 × G2)= {(u1,v1)(u2,v2)。在本文中,我们计算了p-部完全图 m1,m2,...,mp 和完全图Kn 的Kronecker积的顶点参数,m1 ≤ m2 ≤ ... ≤ mp,2 ≤ p ≤ n, and n ≥ 3 ,扩展了Mamut和Vumar的相关结论[Inform. Process. Lett. 106(2008)258-262].     

Decomposition of Complete Graphs into Isomorphic Complete Bipartite Graphs

A decomposition of a complete graph into disjoint copies of a complete bipartite graph is called a ‐design of order n. The existence problem of ‐designs has been completely solved for the graphs for , for , K_{2, 3} and K_{3, 3}. In this paper, I prove that for all , if there exists a ‐design of order N, then there exists a ‐design of order n for all (mod ) and . Giving necessary direct constructions, I provide an almost complete solution for the existence problem for complete bipartite graphs with fewer than 18 edges, leaving five orders in total unsolved.     

交叉数为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.