混合图的双向连通定向

无向图的双向连通定向对单行道路系统的构造有着重要意义。本文讨论的问题实际上是无向图的双向连通定向问题的一种推广。本文主要结果有: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-图是双向连通。     

图是超级-λ3的邻域条件

设G是有限简单无向图, k是正整数,使G-S的每个分支都包含至少k个点的边割S称为G的k-限制边割。若任意最小k-限制边割都孤立一个k阶连通子图,则称图G是超级-λk 的。本文应用邻域条件给出了图是超级-λ3 的充分条件。     

k-连通半无爪图的Hamilton性质

半无爪图是包含无爪图的更大的图类。关于k-连通半无爪图,得到以下结果:G是k-连通的半无爪图(k≥2),如果对于G2的任意基数为k 1的独立集X,都有∑d(v)≥n-k,则G是Hamilton图。     

K-连通无爪图的最长u-路

本文证明了如下结果:设G是p阶K一连通的无爪图,K>2.G中任意K+1个顶点的独立集{V_1,V_2,…V_(k+1),有又设u∈V(G),为G中最长的u一路,则G[R]中不含(K-2)一路连通子图,从而不含K_(k-1),这里R=V(G)\V(P)。     

关于几乎正则2-连通图的Hamilton性的注记

研究几乎正则图的Hamilton性,得到了定理1　设G是2连通的(k,k 1)图,并且k≥V(G)3 13,如果G是偶数阶的图,则G是Hamilton图.定理2　设G是(k,k 2)图,并且k≥n3 103,如果存在G的一个非空独立集B1,使得B1≥n3-133,而且对于G的所有独立集B,都有B≤n2-1,则G是Hamilton图.     

正则2-连通图的最长圈

P.Erdos和A M Hobbs在[1]中提出如下的结论:设k≥6,G是2k个顶点的(k-2)次正则的2-连通图,则G是Hamilton图(以下简称为H图)。本文提出比上述结论更为广泛的定理:定理1 设k≥4,G是n个顶点的(k-2)次正则的2-连通图,则除G是peterson图外,G必有个长至少为min{n,2k}的圈。由于:(i)定理1中的k=4时,G是2-正则2-连通图,G是H图,它有个长为n≥min{n,2k}的圈;(ii)定理1中的k≥5且n≤3(k-2)时,根据[2]中的B.Jackson定理知,这时G是H图,它有个长为n≥min{n,2k}的圈。因此,要证明定理1成立,只要证明如下的定理2成立。定理2 设n≥3k-5≥2k,G是n个顶点的(k-2)次正则的2-连通图,则除G是Peterson图外,G必有个长至少为2k的圈。在证明定理2的过程中,本文作下列的假设:     

k-连通无爪图中存在哈密尔顿圈的一个隐度条件

文中给出了强基本独立集的概念,并证明了如下定理:设G是一个具有n个顶点的k-连通无爪图,其中k≥2.如果对任意一个具有k个顶点的强基本独立集S,都有max{d2(x)|x∈S}≥n 2,则G是哈密尔顿图.此定理在无爪图的条件下推广了已有的几个有关图中哈密尔顿圈存在性的定理.     

k—连通图为Dλ—连通的一个充分条件

本文在对有限简单图给出 D_λ—连通的定义之后,证明了下述定理:设 G 是n 阶 k—连通(k≥3)的有限简单图,如果对任意的 Y∈I_k(G,λ),有sum from i=1 to k (k+i-2)/(k-1)s_i(Y、λ)>n-k(λ-1),则 G 是 D_λ—连通的.     

无爪图的周长

证明了如果G是k-连通的非Hamilton无爪图,k≥2,则G包含一个长度至少为：min{∑x∈Xd（X）＋2k：X是G的独立集,｜X｜=k}的圈。     

k阶限制边连通度最优的一个充分条件

设S是图G的一个边子集,若G-S不连通且每个分支的阶至少为k,则称S为G的一个k-限制边割.若G有k-限制连割,G的最小k-限制边割的边数称为G的k阶限制边连通度,记为λk(G).记ξk(G)=min{|[X,]|∶|X|=k,G|X|连通},若λk(G)=ξk(G),则称G是λK-最优的.证明了若对G中任意一对不相邻的顶点x,y都有d(x) d(y)≥n 2(k-2),且G不是G*k图,则G是λk-最优的.     

混合Euler图的特征性质

本文对任意混合图M建立相伴运输网络N_M的概念,并以此给出M是混合Euler图的充要条件。这结果与文献中同类结果相比,具有更大的实用性。     

混合Euler图的特征性质

本文对任意混合图 M 建立相伴运输网络 N_M 的概念,并以此给出 M 是混合 Euler 图的充要条件。这结果与文献中同类结果相比,具有更大的实用性。     

混合图的边着色

著名学者Daniel Krlá.,Jan Kratochvlí,Heinz-Jürgen Voss等曾在其著名论文《Mixed hypergraphs with bound-ed degree：edge-coloring of mixed multigraphs》中提出任何一个混合超图均可一一对应地转化成一个最大度不超过3的混合超图,且它们的着色亦是一一对应的。因此,研究最大度为3的混合超图的着色问题具有一般性,是困难的;而研究最大度为1的混合超图的着色问题是平凡的;所以我们着力研究最大度为2的混合超图。而最大度为2的混合超图的点着色问题可以一一对应地转化为一个与其对应的混合多重图的边着色问题,因此,文章从特殊的混合多重图-混合图入手,着力研究混合图的边着色。     

正则图分解成重星的一个充分条件

用ｇ（Ｇ）表示图Ｇ的围长。Ｓ（ｋ＿１，ｋ＿２）表示两个非１度顶点分别为ｋ＿１，ｋ＿２的重星。在［２］中证明了：（２ｋ＋１）─正则图Ｇ是Ｓ（ｋ＋１，ｋ＋１）─可分解的充分必要条件是图Ｇ含有１─因子。本文证明的主要结果是：１）设图Ｇ是ｒ（２ｋ＋１）─正则图（ｒ≥２）且ｇ（Ｃ）≥４，如果Ｇ含有ｒ─因子，则图Ｇ是Ｓ（ｋ＋１，ｋ＋１）─可分解的。２）设ｑ＝｜Ｅ（Ｓ（ｋ，ｋ））｜，如果，ｎ＝１（ｍｏｄ２ｑ），则完全图Ｋ＿ｎ是Ｓ（ｋ，ｋ）─可分解的。     

关于临界图的若干结果

Ｖｉｚｉｎｇ’ｓ猜想：ｎ阶Δ－临界图的边数ｍ满足ｍ≥（ｎΔ－ｎ＋３）／２。本文证明了当ｎΔ＝３时猜想也成立以及当５≤Δ〈ｎ／２，ｎΔ＝４时猜想也成立。同时给出了临界图的两个新的性质。     

关于图的星荫度的一个注

图G的曼荫度vas(G)定度为对G进行项点着色且使得G中同色顶点导出的子图的每个连通分支都为星时所需的最少色数,本文证明了平面图和外平面图的曼荫度的平凡上界事实上也是最好的上界.     

能量不超过4的偶图

本文将给出所有能量不超过4的连通简单偶图,并给出关于图的能量与其边的个数的一个不等式。     

完全多部图的G-填充和覆盖

设图G是由P4带一条悬边所组成的五点四边图，本文确定了完全图Kv和完全多部图Kn(t)的图G填充数和覆盖数。     

三次图的收缩及其迭线图的分类

设图G为含有三角形或四边形的三次图,G_△为G的二角形收缩;G_□为G的四边形收缩。本文用计算机辅助证明了,若L(G)是2类的,则L(G_□)是2类的,若L~2(G)为2类的,则L~2(G_△)或L~2(G_□)为2类的。