无哈密尔顿路图的某些图

图G的路图P_k(G)是依下述方法得出的图:以G中的有k个顶点的路P_k作为顶点,且两个顶点相邻当且仅当对应的P_k的并是G中的路P_(k-1)或圈C_k。本文给出了下列结论:1)不存在最大度大于3且具有哈密尔顿P_(3-)图的树;2)不存在最大度大于3且具有哈密尔顿P_(3-)图的单圈图;3)给出了最大度为4且有哈密尔顿P_(3-)图的单圈圉的特征,因而证明了由H.J.Broersma和C.Hoede提出的两个猜测。     

关于一类立方图的可圈性研究

设G为无向图,如果对G的每一个定向D,都存在S（D）包含V（G）使在D中改变所有恰与S（D）中一个顶点相关联的弧的方向后所得的图为有向哈密尔顿图,则称G为可圈图．Klostermeyer和Soltes证明了P4k^3（k≥1）是不可圈图,现证明对任意整数n≥3,Pn^3是可圈图当且仅当n为奇数．     

立方图的可圈性

图的可圈性是哈密尔顿性的一个推广.设G是有向图,如果对G的每一个定向D,都存在S(D) V(G)使在D中改变所有恰与S(D)中一个顶点相关联的弧的方向后所得到的图为有向哈密尔顿图,则称G为可圈图.证明至少含5个顶点的连通图G的立方图是可圈图当且仅当G不同构于任何一条偶路.该结果改进了Klostermeyer的3个定理.     

P3-支配图哈密尔顿性的两个充分条件

在文献[4]中作者引进P3-支配图,并研究了这类图的一些性质.设G是2-连通的P3-支配图,证明了G是哈密尔顿的两个充分条件fan型条件和禁止子图型条件.     

P3——支配图哈密尔顿性的一个充分条件

在文献[4]中作为半无爪图的一个超类,作者引进P3-支配图,并研究了这类图一些性质。设G是2-连通的P3-支配图,我们证明了G是哈密尔顿的一个充分条件局部连通型条件。     

Ore定理的一个注记

对简单图G=(V,E),Ore定理告诉我们如果对G的每一对不相邻的顶点u,v都有d(u)+d(v)≥|V|,则G有哈密尔顿圈.证明了,若G仅包含一对不相邻的顶点u,v,满足d(u)+d(v)＜|V|,G仍有哈密尔顿圈.     

哈密尔顿连通图和邻域并条件（Ⅰ）

记G=(V,E)是简单图,δ表示图G的最小度,NC=min{|N(x)∪N(y)|：x,y∈V（G）mxt∈E（G）|,NC2=min{|N（x）∪N(y)|：x,y∈V(G),d(x,y)=2},1989年Faudree等证明了：若3连通n阶图G,NC≥(2n 1)／3,则G是哈密尔顿连通图。据此进一步研究NC2≥(2n 1)／3,而且研究到2连通图,得到下面结果：若2连通n阶图G,NC2≥(2n 1)／3,则G是哈密尔顿连通图或G=ψ。     

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

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

数理科学与化学——哈密尔顿连通图和邻域并条件(Ⅰ)

记G=(V,E)是简单图,δ表示图G的最小度,NC=min{|N(x)∪N(y)|:x,y∈V(G),xy(?)E(G)},NC_2=min{|N(x)∪N(y)|:x,y∈V(G),d(x,y)=2}。1989年Faudree等证明了:若3连通n阶图G,NC≥(2n+1)/3,则G是哈密尔顿连通图。据此进一步研究NC_2≥(2n+1)/3,而且研究到2连通图,得到下面结果:若2连通n阶图G,NC_2≥(2n+1)/3,则G是哈密尔顿连通图或G=φ。     

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

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

变换图G+——的极大边连通性(英)

证明了对于任意的图G,其变换图G --是极大边连通的当且仅当G至少有两条边且不同构于2K2.     

贪心染色下的随意可染色图

贪心算法用于图的染色问题是一种简单的近似方法.采用贪心算法,证明了将图G的顶点用独立集代替后所得的图GI是随意可染色的当且仅当G本身是随意可染色图;不含K2,3的三正则图是随意可染色图当且仅当它是K4.     

独立点数为2的图的Z_3-连通性

设G是独立点数为2的连通简单图.主要证明两个结论:(1)当边连通为4时,G是Z_3-连通的;(2)当点连通为3时,G是Z_3-连通的当且仅当G■{K_4,W_5}且G不是一类特殊的图.     

与分数k-消去图

设G是一个图,若对于图G的任一边e,G-e都存在一个分数k-因子,则称G是一个分数k-消去图.对于非完全图,证明当顶点数、最小度以及 满足一定条件时G是分数k-消去图.并说明结论在一定意义上是最好的.     

关于f—复盖图

如果图G的每一条边都属于一个f一因子,则称图G是f-复盖的。本文给出了一个图是f-复盖的充分必要条件,并且证明了若图G是m-复盖的及n-复盖的,m,n,k有同样的奇偶性且m相似文献   

σ_2(G)与分数k-消去图

设G是一个图,若对于图G的任一边e,G-e都存在一个分数k-因子,则称G是一个分数k-消去图.对于非完全图,证明当顶点数、最小度以及σ2(G)满足一定条件时G是分数k-消去图.并说明结论在一定意义上是最好的.     

邻接叶边交换森林图的连通性

证明了若图G是2-连通的，则图G的邻接叶边交换森林图是连通的．     

外平面图的平方图的点荫度

图G的平方图G2是以V(G)作为它的点集，两个点在G2中相邻当且仅当它们在G中的距离至多为2.证明了：若G是一个最大度Δ6的外平面图,则G2的点荫度va(G2)=「Δ+12?;特别地，一棵树T的平方图T2的点荫度va(T2)=「Δ+12?.     

联结数与分数（k，n’）一临界消去图

设G是一个图,若删除G中任意n’个顶点的剩余子图依然是分数k-消去图,则称G为分数（k,n＇）-临界消去图．笔者证明了若k≥2,n,≥0,bind（G）≥^（n＇＋1）且6（G）≥k＋n＇＋1,则G是分数（k,n＇）-临界消去图．     

（P,P）图的可嵌性定理

设G是一个简单无向图,称G是(P,P)图,如果|E(G)|=|v(G)|.若G同构于6某个子图,则称G可嵌入6,本文用极其简捷的方法证明了:阶数大于9的(P,P)图可嵌入其补图内的充要条件是G不和图(1)中的任一个图同构。