几种复合图生成树个数的一般求法

若一个图能够由某一个或某几个运算作用于不相交的图上而得到，则称该图为复合图．记ｔ（Ｇ）为图Ｇ的生成树个数，Ｈ（Ｇ）为图Ｇ的Ｋｉｒｃｈｈｏｆｆ矩阵，用“ｏ”表示图的某种运算，如“＋”，“×”，“合成”等，本文研究了Ｈ（ＧｏＧ′）与Ｈ（Ｇ），Ｈ（Ｇ′）的特征值关系，给出了ｔ（ＧｏＧ′）的一般性公式，提供了几种复合图生成树个数的一般性公式，提供了几种复合图生成树个数的一般求法，大大推广了［２，３］的结果，同时简化了许多图类生成树个数表达式的求法．     

基本圈与图的曲面嵌入

本文研究图的基本圈与图在可定向曲面上的嵌入之间的关系．本文结果表明：一个图G可以嵌入到亏格至少为g的可定向曲面上的充分必要条件是：对于G中任意一个支撑树T,存在一个基本圈序列C1,C2,…,Q2g,使得对于每一个i：1≤i≤g,C2i-1∩C2i≠0．特别地,在T的β（G）个基本圈中有基本圈序列C1,C2…,Q2γM（G）,使得Qt-1∩C2t≠0对于每一个i：1≤i≤γM（G）成立．这里β（G）和γM（G）分别是G的Betti数和最大可定向亏格．这个结果的意义在于：我们可以从任意一个支撑树（可以具有任意奇连通分支数）出发去构造图在可定向曲面上的嵌入．这在本质上有别于Xuong与Liu在最大亏格方面的工作（即,从具有最小奇连通分支数的支撑树出发构造图嵌入）．事实上,这个结果在本质上同时推广了Xuong-Liu与Fu等在最大亏格方面的工作．作为这一结果的直接应用,本文得到以下结果：（1）提出了用于计算图的最大亏格的新条件,它尤其适用于计算具有特定边割（edge—cut）图的最大亏格．并得到一些新的与已知的著名结果（包括Huang在曲面嵌入图方面的工作）．（2）最大亏格问题可以归结为在基本相交图中求最大对集问题．结合Micali-Vazirani的一个有效算法,我们设计出了一个用于计算图的最大亏格的多项式算法,它的复杂度是O（（β（G））^5/2）,这一算法与Furst等人的算法相比更加直接、便于计算．     

关于图的余树的奇连通分支数的内插定理

本文研究了连通图的余树的奇连通分支数与其可定向嵌入的关系.我们先给出了关于连通图的余树的奇连通分支数的内插定理.作为其应用,我们推广了Xuong和刘彦佩关于图的最大亏格的计算公式,并且证明了如下结果:任意一个连通图G一定满足下列条件之一: (a)对于任意的满足γ(G)≤g≤γM(G)整数g,只要图G嵌入到可定向曲面Sg上,就存在支撑树T,使g-1/2β(G)-ω(T)),其中,γ(G)与γM(G)分别是图G的最小和最大亏格,β(G)与ω(T)分别是图G的Betti数和由T确定的余树的奇连通分支数; (b)对连通图G的任意一个支撑树T,G可以嵌入某个可定向曲面上使其恰好有ω(T) 1个面.特别地,我们给出了所有非平面的3-正则的Hamilton图G所嵌入的可定向曲面的亏格的计算公式.     

最小1-因子覆盖集的若干结果

假设G是一个1-可扩图．G的1-因子覆盖是G的某些1-因子的集合M使得∪M∈M M=F（G）．1-因子数目最小的1．因子覆盖称为excessive factorization．一个excessive factorization中的1．因子数目称为图G的excessive index，记为x：（G）．本文我们基于G的耳朵分解和E（C）的依赖关系给出了X＇e（G）的上界．对任意正整数k≥3，我们构造出一个图G使得A（G）=3而X＇e（G）=k．进而，我们考虑了乘积图的excessive index．     

图的倍图与补倍图

计算机科学数据库的关系中遇到了可归为倍图或补倍图的参数和哈密顿圈的问题．对简单图C，如果V（D（G））：V（G）∪V（G′）E（D（G））=E（C）∪E（C″）U{vivj′｜vi∈V（G），Vj′∈V（G′）且vivj∈E（G））那么，称D（C）是C的倍图，如果V（D（G））=V（C）∪V（G′），E（D（C））：E（C）∪E（G′）∪{vivj′}vi∈V（G），vj′∈V（G’）and vivj∈（G）），称D（C）是G的补倍图，这里G′是G的拷贝．本文研究了D（G）和D的色数，边色数，欧拉性，哈密顿性和提出了D（G） 的边色数是D（G）的最大度等公开问题．     

具有最大控制数的连勇图的刻画

设G为一个P阶图,γ（G）表示G的控制数。显然γ（G）≤[p/2]。本文的目的是刻画达到这个上界的连通图。主要结果：⑴当p为偶数时,γ（G）=p/2当且仅当G≌C4或者G为某连通图的冠;⑵当p为奇数时,γ（G）=p-1/2当且仅当G的每棵生成树为定理3.1中所示的两类树之一。     

仙人掌图的L（2，1）-标号

一个图G的L（2，1）-标号是给图G上的顶点分配非负整数标号，使得G上相邻的两个点的标号至少相差2，距离为2的两个点的标号则不同．G的L（2，1）-标号数λ（G）是所有能使图G正常标号的最小标号．如果一个图的任何两个圈不含有公共边，则称这个图为仙人掌图．显然树是它的一个子图类．对于任何树T，有△（T） ＋ 1 ≤λ（T） ≤△A（T）＋2．本文中我们证明了在一些条件下，这个界也适用于仙人掌图．     

导出子图和周长的局部定理

设G是n阶2-连通图，3≤c≤n.本文绘出对于图G的每一个同构于K1.3或Z1的导出子图L，若d（u）且如果dL（u，v）=2有（v）=min{，|M3（u）|/2}这里M3（u）={v|dc（u,v）≤3}，则G包含长至少为c的圈．     

对称空间和齐性等参子流形

本文讨论了对称空间和齐性等参子流形之间的密切关系，并利用Satake图（B，θ）给出对称空间G／K的迷向表示的主K-轨道与齐性等参子流形M之间的一一对应，同时还得到（B，θ）与标有重数的Dynkin图D（M）之间的对应     

图的最大亏格的一个性质

本文所考虑的图均指有限元向图，没有解释的术语和记号同[1]．一个图称为简单图如果不含重边及环．曲面S这里指一个紧的，连通的，2－维闭流形（定向或不可定向），其亏格记为g（S）．连通图G在曲面S上的一个2－胞腔嵌入意指存在一个1－1连续映射h：G→S使得S＼h（G）的每个连通分支与圆盘拓扑同胚．连通图G的定向亏格γ（G）（或不可定向亏格γ（G））是指最小的整数k使得G在亏格为k的定向（或不可走向）曲面S上有2－胞腔嵌入；而图G的最大定向亏格，也常称之为最大亏格，记为γM（G）,是指最大的整数k使得G在亏格为k定向曲面S上有…     

无向图可迹的一个充分条件

无向图G是简单连通图,且最小度为δ.如果G中包含一条生成路,则G是可迹的.无向图G的叶子数L(G)是G中生成树所含的叶子数的最大数.基于L(G)和δ,证明了一个充分条件使得无向图G是可迹的,即设G为连通图,最小度为δ≤4.若δ≥(1/2)(L(G)+2),G是可迹的.     

图的生成树, 基本圈与Betti亏数

G为图且T是G的一棵生成树. 记号ξ(G, T)表示G＼E(T)中边数为奇数的连通分支个数. 文献［2］称ξ(G)=min[DD(X]T[DD)]ξ(G, T)为图G的Betti亏数, 这里min取遍G的所有生成树T. 由文献［2］知, 确定一个图G的最大亏格主要确定这个图的Betii亏数ξ(G).该文研究与Betti亏数有关的图的特征结构, 得到了关于图的最大亏格的若干结果.     

没有5-圈的平面图的BB-染色

设H为G的一个生成子图,（G,H）的一个BB-k-染色是指一个映射f：V（G）→{1,2,…,k},当uv∈E（H）,｜f（u）-f（v）｜≥2;当uv∈E（G）／E（H）,｜f（u）-f（v）｜≥1.定义（G,H）的BB色数x_b（G,H）为最小的整数k,使得（G,H）是BB-k可染的.本文研究了对于任意的连通,非二部平面图G,且G没有5-圈,都存在一棵生成树T,使得x_b（G,T）=4.     

3-连通3-正则图生成树外的可去边

G是3-连通图，e是G中的一条边．若G-e是3-连通图的一个剖分，则称e是3-连通图的可去边．否则，e是G中不可去边．本给出3-连通3-正则图中生成树外可去边的分布情况及数目．     

没有4-圈的平面图的BB-染色

设H为G的一个生成子图,(G,H)的一个BB-k染色是指一个映射f:V(G)→{1,2…,k},满足以下两条:(i)|f(u)-f(u)|≥1,uu∈E(G)\E(H).(ii)|f(u)-f(u)|≥2,uv∈E(H).定义(G,H)的BB-色数xb(G,H)为最小的整数k,使得(G,H)是BB-k可染的.本文证明了...     

有限连通图上随机扩张森林和连通子图的边负相关性

设G为有限连通图．本文研究图G的子图空间G上的三类概率测度,它们分别刻画图的随机扩张树,随机扩张森林和随机连通子图．基于G上均匀扩张树的边负相关性,我们构造G上的一族边负相关的非平凡随机扩张森林和随机连通子图．此外,我们还给出一定条件下图上均匀扩张森林的边负相关性．     

An Extension of the Win Theorem: Counting the Number of Maximum Independent Sets

Win proved a well-known result that the graph G of connectivity κ(G) withα(G) ≤κ(G) + k-1(k ≥ 2) has a spanning k-ended tree, i.e., a spanning tree with at most k leaves. In this paper, the authors extended the Win theorem in case when κ(G) = 1 to the following: Let G be a simple connected graph of order large enough such that α(G) ≤ k + 1(k ≥ 3) and such that the number of maximum independent sets of cardinality k + 1 is at most n-2k-2. Then G has a spanning k-ended tree.     

[a,b]-因子包含给定圈的充分条件

设G是一个图且a,b是非负整数,a≤b.图G的一个[a,b]-因子是图G的一个支撑子图H且满足对所有的x∈V(G),a≤dH(x)≤b都成立.给出了图中[a,b]-因子包含给定圈的一个充分条件.     

包含k-树图的毁裂度条件

连通图G的一个k-树是指图G的一个最大度至多是k的生成树.对于连通图G来说,其毁裂度定义为r(G)=max{ω(G-X)-|X|-m(G-X)|X■V(G),ω(G-X)1}其中ω(G-X)和m(G-X)分别表示G-X中的分支数目和最大分支的阶数.本文结合毁裂度给出连通图G包含一个k-树的充分条件;利用图的结构性质和毁裂度的关系逐步刻画并给出图G包含一个k-树的毁裂度条件.