关于非广义多边形路的2连通简单MCD图

令Sn是具有n个顶点没有两个等长圈的简单图的集合,若Sn中不存在图G′使│E（G′）│＞│E（G）│,则称图G是简单MCD图,若简单MCD图G是2连通的,则称G是2连通简单MCD图,若G中一条路P的两个内点u都有dG(v)=2,则称P为G的简单路,一个2连通可平面图G称为广义多边形路,如果用下述方法得到图G是路,对应于G的每个内部面f(G-是G的平图）有一个G＊的顶点f*,G*的两个顶点f*和g*,在G＊中相邻当且仅当G－中相应的两个内部面的边界交于一条G－的简单路,作者证明了下述结果,当且仅当n∈{10,11,14,15,16,21,22}时,存在n个顶点的非广义多边形路的2连通简单MCD图。     

连通图中圈数

用|V（G）|、|E（G）|和f（G）分别表示图G的顶点数、边数和圈数．设F（k）＝｛f（G）;G是满足|E（G）|－|V（G）|＝k的无环连通图｝,n（k）＝minF（k）和N（k）＝maxF（k）．证明了下述结果：（1）n（k）＝k＋1;（2）N（k）≤2k+1;（3）对每个整数k≥1,N（k）≥2k＋k（k－1）＋1且当1≤k≤4时等式成立;（4）对每个整数k≥1是奇数时,N（k）≥2k3;当k≥2是偶数时,     

一类广义多边形树的色性

本文研究了一类广义多边形树的色性，并且证明了这类图是色唯一的．     

图的路连通问题

如果图Ｇ的每对不同顶点ｕ和ｖ之间都有哈密顿路相连，则称Ｇ是哈密顿连通的；而如果对于所有满足条件以ｄ（ｕ，ｖ）≤ｑ≤ｎ－１的整数ｑ，ｕ和ｖ之间有长为ｑ路相连，则和Ｇ是泛连通的，其中以ｄ（ｕ，ｖ）是ｕ和ｖ间的距离，而ｎ是Ｇ的顶点数。本文证明了下述两个结果：（１）２ｋ＋１个顶点的ｋ正则简单图是哈密顿连通的，（２）ｋ连通国中任何两顶点之间存在ｋ－１条长度不同的路；进而如果Ｇ的顶点数小于２ｋ，则Ｇ是泛连通的。     

一类极大临界2连通图的结构

引入图的粘合的概念，讨论了极大临界2连通图G的性质，给出了一个图是这类图的一个充要条件。由此给出该类图的一种新的构造方法，即G能按条件先粘合一系阶大于2的完全图的边，然后粘合四圈C4的t个拷贝得到．     

2连通2部图周长的下界

设 G(A_1,A_2;E)是以(A_1,A_2)为2分划的2连通的2部图.D(u)={v|v∈V(G),d(u,v)=2};δ_0=min{max{d(u),d(v)}|u,v∈V(G)且 d(u,v=2};D(δ_0)={u|u∈V(G)且d(u)≥δ_0};δ~*为 G 中某一项点度且δ~*≥δ_0,当δ~*>δ_0时δ~*还满足:(i)δ~* 尽可能的大,(ü)对 Vu∈D(δ_0)及 D~*(u)={v|v∈(D(u)U{u}),d(v)<δ~*}有|D~*(u)|相似文献   

广义多边形的一个构造定理

W·K·Kator于1986年在文献[2]中给出了构造广义多边形的一个定理,本文另外给出一个。并把构造广义多边形的问题归结到某个集合上建立一种特殊映射的问题。     

一类广义多边形树的色唯一性

讨论了5-桥图F（a,a,a,a,b）（2≤a＜b）的色性,并证明了此类图是色唯一的.     

2-连通正则图中最长ab-路

在 Ｈ．Ａ．Ｊｕｎｇ定理的基础上，讨论Ｔ ２－连通正则图中最长 ａｂ－路 Ｐａｂ的路长。设Ｇ是ｎ阶ｋ正则具有二分类（Ｖ１，Ｖ２）的偶图，对任意ａ，ｂ∈Ｖ（Ｇ）．ａ≠ｂ， 若有或 ａ． ｂ ∈ Ｖ２则称Ｇ有Ｈａｍｉｌｔｏｎ性质。一个非偶图若是Ｈａｍｉｌｔｏｎ连通的，则称为具有Ｈａｍｉｌｔｏｎ性质。限制｛ａ，ｂ｝不是Ｇ的割集，具有上述性质的Ｇ称为有弱Ｈａｍｉｌｔｏｎ性质。作者得到如下定理：令Ｇ是２－连通ｋ正则的图，且｜Ｇ｜≤３ｋ－２（ｋ≥９）．则Ｇ有弱Ｈａｍｉｌｔｏｎ性质。     

由轮生成的Cayley图的广义3-连通度

令S?V(G),κ_G(S)表示图G中内部不交的S-树T_1,T_2,…,T_r的最大数目r,使得对任意i,j∈{1,2,…,r}且i≠j,有V(T_i)∩V(T_j)=S,E(T_i)∩E(T_j)=?.定义κ_k(G)=min{κ_G(S)|S?V(G),且|S|=k}为图G的广义k-连通度,其中k是整数,且2≤k≤n.令Sym(n)是在{1,2,…,n}上的对称群,T是Sym(n)的对换集合.G(T)表示点集是{1,2,…,n},边集是{ij|(ij)∈T}的图.若G(T)是一个轮图,则将Cayley图Cay(Sym(n),T)简记为WG_n.主要研究由轮生成的Cayley图WG_n的广义3-连通度,并证明κ_3(WG_n)=2n-3,其中n≥4.     

图的路分解

Ｇａｌａｉ提出的小路分解（ＳＰＤ）猜想：任一连通图的路分解的路数的最小数目至多为［（ｎ＋１）／２］,迄今还未完全得以解决而这个问题在运筹、网络及信息最优传递过程中有着实际的应用价值本文利用Ｌｏａｓｚ定理证明猜想在一定条件下是成立的     

4连通无爪图的最长圈

设Ｇ为ｎ阶４连通远爪图，δ＝ｍｉｎ（ｄ（ｘ）／ｘ∈Ｖ（Ｇ）），则当ｎ≤６δ－１１时Ｇ为Ｈ图，当ｎ≥６δ－１０时，ｃ（Ｇ）≥５δ－７。     

广义道路与广义圈的绑定数与增强数

对一般的图,求其绑定数和增强数是NP-困难问题,在本文中我们求出了两类图的绑定数和增强数.     

极小n棱连通图的着色与棱数

Mader证明极小n连通图是n+1色可着的,本文证明极小n棱连通图也是n+1色可着的。并且对极小n棱连通图的棱数界进行了估计,证明了若G是p阶极小n棱连通图,则G的棱数e(G)≤n(p-1)。     

有圈二部图覆盖的一个结果

H.Wang猜想,对于任意整数k≥2,存在N(k)使得二部图G=(V1,V2,E)中,V1=V2=n≥N(k),且对于G中任意一对不相邻的顶点x∈V1,y∈V2,有d(x)+d(y)≥n+k,那么,对于G中任意k个独立边e1,e2,e3,…,ek,存在顶点不重的k个圈C1,C2,…,Ck,使得ei∈E(Ci),i∈{1,2,…,k}和V(C1∪C2∪…∪Ck)=V(G).H.Wang及J.A.Bondy对k=2,3时证明了猜想成立,本文对k=4证明了猜想的正确性.     

一类图的最长圈

设Ｇ是２－连通图。对Ｇ中任一对不相邻的顶点ｕ,ｖ,│Ｎ（ｕ）ＵＮ（ｖ）│≥ｓ当ｓ≥５时,对于事任意两个不主的点集Ｅ,Ｆ,│Ｅ│≥ｓ,│Ｆ│≥ｓ／２,Ｇ中有３条点不交的Ｅ－Ｆ路,由Ｇ的最长圈的长ｃ（Ｇ）≥ｍｉｎ｛│Ｖ（Ｇ）│,３ｓ／２｝。     

判定k-点连通图与k-边连通图极小性的定理

主要研究了判定ｋ－点连通图是极小的充要条件和ｋ－边连通图是极小的必要条件。     

S—控制圈的一个充分条件

设Ｇ是ｋ—连通的ｎ阶图，ｋ≥２，若对于Ｇ中的满足（对任意的任意（ｋ＋１）—独立集Ｘ，有则Ｇ中存在Ｓ—控制圈．