连通图的临界性

通过连通图的研究给出μ－临界m-连通m－正则图的一种构造方法。并给出关于μ－临界图的结论：G是4－连通（p,q)图，P≥9，如果存在线x=uv及S包含于V（G）使G－x-S有两个支A，B，u∈A，v∈B，则当|A| ≥3或|B|≥3时，G不是μ－临界图。     

每点都与3度点相邻的最大临界3棱连通图的结构

没G=(V,E)是3棱连通图,若对每个x∈V(G),G-x 不是3棱连通的,则称G 为临界3棱连通图.p 阶临界3棱连通图的全体记为(?)_3(p),G∈(?)_3(p)称为最大的,如果不存在H∈(?)_3(p),使|E(H)|>|E(G)|.本文给出每个点都与3度点相邻的p 阶最大临界3棱连通图的结构.     

具有二分划(A1,A2)的2－连通偶图为(A1,A2)Hamilton连通的一个充分条件

给出具有二分划 (A1,A2 )的n阶 2连通偶图G(A1,A2 )为 (A1,A2 )Hamilton连通的定义 ,其中 |A1|=|A2 |·采用反证法 ,将图G分为若干情形 ,利用图G是 2连通的偶图 ,及 |A1|=|A2 |,证明了 ,若n≤ 2δ +2δ - 2时 ,则G是 (A1,A2 )Hamilton连通图 ,其中δ =min{d(x) |x∈V(G) } ,δ =min{max(d(x) ,d(y) ) |d(x ,y) =2 ,x ,y∈V(G) }·     

具有二分划(A_1;A_2)的2-连通偶图为(A_1;A_2)Hamilton连通的一个充分条件

给出具有二分划(A1,A2)的n阶2连通偶图G(A1,A2)为(A1,A2)Hamilton连通的定义,其中|A1|=|A2|·采用反证法,将图G分为若干情形,利用图G是2连通的偶图,及|A1|=|A2|,证明了,若n≤2δ+2δ-2时,则G是(A1,A2)Hamilton连通图,其中δ=min{d(x)|x∈V(G)},δ=min{max(d(x),d(y))|d(x,y)=2,x,y∈V(G)}·     

群色临界图的一些性质

群色数χ1(G)是最小数m,使得对任意Abel群A,若|A|≥m,则G是A-可着色的.称G是群色临界的,若对于G的任一真子图H,有χ1(H)<χ1(G).研究了群色临界图的一些性质,给出某些群色临界图的刻划,证明了k群色临界图G的最小度为k-1,且若G是3群色临界图当且仅当G是圈.     

关于Euler生成子图极大边数的一个注记

若图G存在欧拉生成子图,则称G是超欧拉图(supereulerian).常用SL表示全体超欧拉图组成的集合 设G是有n个点的简单图,G∈SL,如果δ(G)≥ 4且δ≥n5-1,则G存在欧拉生成子图H,使得 |E(H) | / |E(G) |≥ 3/5     

可扩图的一些性质

设G是一个连通的简单图且具有完美匹配。如果G的任一基数为n(n≤(|V(G)|-2)/2的匹配都能扩充为G的一个完美匹配，则称G为n-可扩的。对于S包含于V(G),记M是G[S]的基数为r的最大匹配，并令T＝S－V（M）。对连通的非二部的n-可扩图G（n≥2），得到以下结果：（1）若r≤n且|T|≥2，则|V(G)|≥2(n r |T|--1)。（2）若r≤n-2且|T|≥2，则|V(G)|≥2(n r |T|)。（3）若|V(G)|≤4n-2，则对于任一u∈V(G),G[Г(u)]都有一个基数为n的匹配。     

混合图的双向连通定向

无向图的双向连通定向对单行道路系统的构造有着重要意义。本文讨论的问题实际上是无向图的双向连通定向问题的一种推广。本文主要结果有:1.设 B 为混合图 M 的任一 k-断集,则 M 有双向连通定向的充要条件为 M 是混合连通且 k≥2。2.设图 M 有混合 Euler-迹,又 M 中任一断集 B 有|B|≥2k,则 M 有一个 k-弧连通定向。3.设无环图 M 为混台连通,又 b∈E(M)∪A(M),有 M-b 为混合连通,则 M 的 DFS-图是双向连通。     

混合图的双向连通定向

无向图的双向连通定向对单行道路系统的构造有着重要意义。本文讨论的问题实际上是无向图的双向连通定向问题的一种推广。本文主要结果有:1.设 B 为混合图 M 的任一 k-断集,则 M 有双向连通定向的充要条件为 M 是混合连通且 k≥2。2.设图 M 有混合 Euler-迹,又 M 中任一断集 B 有|B|≥2k,则 M 有一个 k-弧连通定向。3.设无环图 M 为混合连通,又(?)b∈E(M)∪A(M),有 M-b 为混合连通,则 M 的 DFS-图是双向连通。     

一类图的次小与第三小能量

图的能量记为E(G),它等于G的特征多项式特征根的绝对值之和.μn表示连通的(n,n)-图(n个顶点,n条边的连通图).对于G∈μn:如果对于圈上的任意一点v有d(v)=r(r≥2),那么称G为圈-r-正则(n,n)-图.本文给出了C3-3-正则(n,n)-图(μ3n(3))能量的次小值与第三小值及对应的图.