不超过7阶的3-关系图的刻画

给定一个图G,如果存在一个边标号树T,使得树T的叶子集等于图G的顶点集,并且树T任何叶子x到叶子y的唯一路径上的边标号之和为3当且仅当xy为图G的边,那么称图G是一个3-关系图.该文讨论了什么样的图是3-关系图,证明了图G是3-关系图的必要条件为图G是二部图,即只要图G包含奇圈,则图G不是3-关系图.更进一步,完全刻画了圈为3-关系图的充要条件,即一个圈是3-关系图当且仅当圈为偶圈,并且给出了偶圈相对应的边标号树.最后讨论了比较小的图为3-关系图的条件,即证明了阶至多为7的图是3-关系图的充分必要条件为图G是二部图.     

图的符号边控制数的下界

对于任意的n阶图G, 当存在一个最大的奇元素子图是图G的导出子图, 给出了图G的符号边控制数的一个下界. 此外, 还改进了任意非平凡的n阶树T的符号边控制数的下界.     

Heawood反例图的全部四着色

本文首次报告了Heawood反例图的全部四着色.它可以用一个树林来描述.树林的每个分支是一棵四着色树.四着色树是一个根树.根节点Cr是Heawood反例图的一个四着色.根树其它节点都是经过一个或多个二色变换从Cr变来的.Heawood反例图有37个四着色树.其中有35个偶四色树(包括24个是仅有根结点的退化型四色树),2个奇四色树.偶四着色总计112,奇四着色总计144,全部四着色总共256个.这些结果都是用Maple编程得到的.     

饱和二部图

没有完美匹配的二部图G,若给它任意增加一条新的边,结果得到的二部图有完美匹配,则称图G是饱和的.设X(∈)V(G),T(X)表示V(G)中与X中至少一个顶点相邻的所有顶点组成的集合.本文证明了一个二部图G=(U,W)是饱和的当且仅当(a)存在唯一X(∈)U,使得|X|＞Γ(X)|,|X|-1＞|Γ(X)|且G的导出子图G[X∪Γ (X)]是完全二部图;(6)G的导出子图G[(U-X)∪(W-Γ(X))]是完全二部图,且满足|U-X|+1=|W-Γ(X)|;(c)U-X中每个顶点与W中的每个顶点都相邻,且X∪(W-Γ(X))是图G的一个独立集.     

给定分支点数目树的离心率总和

设G=(V,E)是简单连通图,简单连通图G的离心率总和定义为图G中所有顶点的离心率总和。若树T中某个顶点的度大于等于3,则称这个点为T的分支点。刻画了给定分支点数为r顶点数为n的树的离心率总和的上界和下界。     

折叠超立方体的广义3-连通度

设图G是一个连通图,S⊆V(G)。图G的一棵S-斯坦纳树是一棵包含S中所有顶点的树T=(V ',E '),使得S⊆V '。如果连接S的两棵斯坦纳树T和T ',满足E(T)∩E(T ')=且V(T)∩V(T ')=S,则称T和T '是内部不交的。定义κ(S)为图G中内部不相交S-斯坦纳树的最大数目。广义k-连通度(2≤k≤n)定义为κ_k(G)=min{κ(S)|S⊆V(G)且|S|=k},显然,κ₂(G)=κ(G)。证明了κ₃(FQ_n)=n,其中FQ_n是n-维折叠超立方体。     

与支配集有关的上可嵌入图

结合图的支配集与其他相关条件,证明了如下结果:(1)设G是无环连通图,如果G中含有一个子图为轮W,且V(W)={x,y1,y2,,yt}(t≥3)为图G的一个支配集,则图G是上可嵌入的.(2)设G是无环连通图,如果G中含有一个子图为完全二部图D=(X,Y;E),且V(D)=X∪Y为图G的一个支配集(其中|X|≥3,|Y|≥4),则图G是上可嵌入的.     

树图的外围维纳指标的下界

设G=(V,E)为简单连通图.对v∈V(G),顶点v的离心率ε(v)=max{d(u,v)│u∈V(G)}, d(u,v)为图G中顶点u,v间的距离.图G的直径为d(G)=max{ε(v)│v∈V(G)}.外围顶点集P(G)指图G中满足ε(v)=d(G)的所有v=V(G).图G的外围维纳指标为■.首先讨论了当树图T的外围顶点个数确定时,它的第二下界;然后讨论了当树图T的顶点数目确定时,其对应的PW(T)的最小值,及达到其最小值的极图.     

不含某些图作为导出子图的图的色数

Erods证明了对于任意一个图G,χ(G)-ω(G)可以任意大。因此,对一般图而言,其色数不一定能找到一个与团数有关的上界。文章主要讨论一类特殊的F-free图的色数和团数的关系。设图G=(V,E)是一个不含K1,k+1+e、C4和C4+e为导出子图的连通图,不是星图和奇圈。若α(G)≥k≥3,则χ(G)≤(k(k-1)/2)ω(G)。     

无K_(1,t)图的L(d,1)-T标号

给定一个连通图G=(V,E)及其一棵支撑树T,图G的一个L(d,1)-T标号即函数g:V(G)→{0,1,2,…},满足:(1)如果xy∈E(G),则|g(x)-g(y)|≥1;(2)如果dG(x,y)=2,则|g(x)-g(y)|≥1;(3)如果xy∈E(T),则|g(x)-g(y)|≥d.假设图G有一个L(d,1)-T标号函数g:g(V){0,1,2,…,k},则图G的所有L(d,1)-T标号函数中最小的整数k记为L(d,1)-T标号数λdT(G,T).本文证明了若G是无K1,t(3≤t≤n)的连通图,其最大度为Δ,|G|=n,T为G的任意支撑树,则λdT(G,T)≤tt--12Δ2+Δ+2d-2.     

某些伪类环图的生成树数

连通图的生成树是指该图的极小连通生成子图.通过Cayley公式、递推关系式及伪类环图与伪类环图生成树数之间的关系式给出伪类环图-Sn,-An的生成树数.     

平面图的无圈边染色

利用差值转移的方法证明了,如果g（G）≥4则有X′a≤Δ（G）＋4.图G=（V,E）是简单图,映射C：E→[k],被称作是图G的一个无圈k边染色.如果任意相邻的两个边染有不同的颜色,以及图G中不含有2-色圈,换句话说即图G中任何染两种颜色的边的导出子图是一棵森林.     

树扩图生成树数的界

连通图的生成树是指该图的极小连通生成子图．在Cayley公式的基础上，给出树扩图生成树数的上下界．     

关于判定超欧拉图的收缩法

P.A.Catlin提出一个问题：设H是图G的一个连通子图，如果G关于H的收缩图G/H有一个欧拉生成子图，那么在什么条件下G也有一个欧拉生成子图？研究了这一问题，讨论了Catlin提出的用收缩法判定超欧拉图的两个定理，给出了一些实用的超欧拉图的判别方法。     

蕴含一类图论性质的可图序列

设σ（Tm,k,n）是最小正偶数,使得所有满足σ（π）=d1＋d2＋…＋dn≥σ（Tm,k,n）的n项可图序列π是蕴含Tm,K可图的,即π（d1,d2,…,dn）有一个实现含一直径为k的m阶树．考虑了σ（Tm,k,n）之值问题,并确定了当k=3且n充分大时σ（Tm,3,n）的值．     

T3-受限图的路可扩性

剖分无爪图K1.3的一边所得到的图形称为L图，如果图G中任意一个与T3同构的导出子图的3个1度顶点之间至少有一条边，则称图G为T3-受限图．证明了连通、局部3-连通的L-受限图是路可扩的．     

某类联图中保Wiener指数的树

Wiener指数是指一个连通图中所有顶点之间的距离之和。给定一个连通图G,若存在G中一棵子树T,使得W(G)=W(T),则称T为G的一棵保Wiener指数的树,本文给出了对于满足特定条件的某类m+2k阶联图中均有保Wiener指数的子树。     

RP图的特征刻划

设T是图G的一颗支撑树,若某顶点u满足;对任意顶点υ均有dG(u,υ）=dT(u,υ）,则称u对于支撑树T是RP,如果对G的任一棵支撑树都至少存在一个RP点,则称图G是RP图,Gagliardi等在1997年证明了K2,n是一类RP图,并猜想：“K2,n以及在其顶点上加上若干树状结构所得的图是仅有的RP图”。但容易验证圈Cn也是一类RP图,因此上述猜想需要修正,本文证明了RP图的如下特征刻划：除树外,简单图中只有K2,n和Cn 以及在某若干顶点上分别外接互不相交的树状结构所得的图是RP的。     

一些特殊树的对偶带宽

图G的对偶带宽是指图G中相邻两点最小标号差的最大值。确定了一些特殊树的对偶带宽，主要结果如下：(1)如果树T有n个顶点，并且其最大度△(T)不小于[n/2]，那么树T的对偶带宽等于n一△(T)的充要条件为T是双层星且其内星的中心为最大度顶点；(2)完全二叉树T2,k的对偶带宽等于2^k-1；(3)等高单毛虫树Pm,n的对偶带宽为[mn/2]。