检索结果-南通市图书馆

图的哈密尔顿连通性和从任意点出发都可迹的充分条件

维普期刊数据库博看期刊评论

在线全文

学校读者我要写书评

暂无评论

中国科学技术大学学报 2020年第2期50卷 100-105页

作者：王礼想余桂东徐弈安庆师范大学数理学院安徽安庆246133 合肥幼儿师范高等专科学校公共教学部安徽合肥230013

图的哈密尔顿路是指通过图的所有顶点的路.如果图G的任意两点都有一条哈密顿尔路,称此G为哈密尔顿连通的.如果图G从任意点出发都有一条哈密尔顿路,称G从任意点出发都是可迹的.根据图G的边数、谱半径和无符号拉普拉斯谱半径,分别给出哈... 详细信息

图的哈密尔顿路是指通过图的所有顶点的路.如果图G的任意两点都有一条哈密顿尔路,称此G为哈密尔顿连通的.如果图G从任意点出发都有一条哈密尔顿路,称G从任意点出发都是可迹的.根据图G的边数、谱半径和无符号拉普拉斯谱半径,分别给出哈密尔顿连通图以及从任意点出发都可迹图的一些充分条件.

关键词：哈密尔顿连通可迹谱半径无符号拉普拉斯谱半径

原图是平面图的4-连通线图的哈密尔顿连通性（英文）

在线全文

学校读者我要写书评

暂无评论

数学进展 2019年第1期48卷 29-34页

作者：王茂群杨卫华太原理工大学数学学院太原山西030024

对于一个整数.s≥0,如果图G的任何一个点子集S (?) V(G)满足|S|≤s,并且G-S是哈密尔顿的,那么称图G是s-哈密尔顿的.本文证明原图是平面图的4-连通线图是2-哈密尔顿的并且还是哈密尔顿连通的.这一结果推广了赖虹建在[Graph and Combinato... 详细信息

对于一个整数.s≥0,如果图G的任何一个点子集S (?) V(G)满足|S|≤s,并且G-S是哈密尔顿的,那么称图G是s-哈密尔顿的.本文证明原图是平面图的4-连通线图是2-哈密尔顿的并且还是哈密尔顿连通的.这一结果推广了赖虹建在[Graph and Combinatorics,1994, 10:249-253]中的结果.

关键词：哈密尔顿连通线图平面图 2-哈密尔顿

无爪图中不相邻子图P_4和K_1度和条件下的哈密尔顿连通性

在线全文

学校读者我要写书评

暂无评论

运筹学学报 2016年第1期20卷 112-117页

作者：郑伟王力工西北工业大学理学院应用数学系西安710072

研究子图的度和图的哈密尔顿性的关系,证明图G是一个n阶3-连通无爪图且最小度δ(G)≥4,如果图G中任意两个分别同构于P_4,K_1的不相邻子图H_1,H_2满足d(H_1)+d(H_2)≥n,则图G是哈密尔顿连通.

关键词：无爪图不相邻子图子图的度哈密尔顿连通

3-连通且基本9-连通线图是哈密尔顿连通图

在线全文

学校读者我要写书评

暂无评论

3-连通且基本9-连通线图是哈密尔顿连通图

作者：程胜利华中师范大学

学位级别：硕士

图的哈密尔顿性是结构图论的重要研究课题.该课题与著名的四色猜想密切相关.从计算复杂性角度看,判定一个图是否为哈密尔顿图是NP-困难的,所以对哈密尔顿问题的研究主要集中在给出判定图的哈密尔顿性的充分性条件.本文从图的结构上考虑... 详细信息

图的哈密尔顿性是结构图论的重要研究课题.该课题与著名的四色猜想密切相关.从计算复杂性角度看,判定一个图是否为哈密尔顿图是NP-困难的,所以对哈密尔顿问题的研究主要集中在给出判定图的哈密尔顿性的充分性条件.本文从图的结构上考虑,给出禁用子图条件.设日是图G的一个子图,如果G不含同构于日的导出子图,则称日为G的一个禁用子图,也称图G是H-free图.K1,3是最常用到的禁用子图之一,K1,3-free图亦称为无爪图.1984年Matthews和Sumner提出了下述著名猜想：任意4-连通无爪图都是哈密尔顿图.该猜想被连续研究了二十多年(参见文献[12],[4][15]等),但是至今尚未得到证明.于是,Lai et al.开始研究3-连通线图的哈密尔顿性,他在2006年证明了：任意3-连通,且基本11-连通线图是哈密尔顿图Li et al.在2012年证明了：任意3-连通,且基本10-连通线图是哈密尔顿连通图Li et al.之后提出存在最小的正整数k,满足：任意3-连通且基本k-连通线图是哈密尔顿图.本文证明了：任意3-连通,且基本9-连通线图是哈密尔顿连通图.该结果改进了Lai et al.和Li et al.的相关工作.

关键词：连通图禁用子图基本连通哈密尔顿连通

在线全文

同方学位论文库

学校读者我要写书评

暂无评论

笛卡尔积图的哈密尔顿连通性

笛卡尔积图的哈密尔顿连通性

作者：茹仙姑·吾守尔新疆大学

学位级别：硕士

Gould在文献[R. Gould, Advances on the Hamiltonian Problem-A Survey, Graphs and Combinatorics,19(2003)7-52.]中提出如何用自然的条件给出笛卡尔积图的哈密尔顿性的问题.关于柱图(即一个图与K2的笛卡尔积)为哈密尔顿的充要条件由Paulruja在文献[P. Paulraja, A characterization of hamiltonian prisms, J. Graph Theory,17(1993)161-171.]中给出.陆玫等人在文献[M. Lu, H-J. Lai, H. Li, Hamiltonian properties in Cartesian product, Manuscript,2009]给出了一个哈密尔顿图与树图笛卡尔积是哈密尔顿图的充要条件. 在本文中我们研究两个图G和Ⅱ的笛卡尔积G□Ⅱ的哈密尔顿连通性问题.我们给出当G是一个哈密尔顿图时,其柱图是哈密尔顿连通的充要条件以及哈密尔顿连通图G与树图T的笛卡尔积是哈密尔顿连通的充要条件.同时,对柱图的与哈密尔顿性质有关的一些问题进行了研究,给出了哈密尔顿图的柱图是3*-连通的一个充分条件. 下面是我们的主要结果： (i)设G是一个哈密尔顿连通图,T是最大度为△的树图.则两个图的笛卡尔积G□T是哈密尔顿连通的充要条件是△(T)≤|V(G)|-1且T不包含K1,3(n)的剖分图作为子图.其中K1,3(n)是由K1,3的每个一度与K1,n的中心点连接而得到的图. (ii)设图G是哈密尔顿图,则柱图G□K2是哈密尔顿连通的充要条件是：(a)|V(G)|为奇数,或(b)|V(G)|为偶数且G以(?)(1,2k+1,2l+1)为其生成子图.其中(?)(1,2k+1,2l+1)是有一条公共边的两个奇圈的并. (iii)设图G是哈密尔顿图,则柱图G□KK2是3*-连通的,如果：(a)|V(G)|为奇数,或(b)|V(G)|为偶数且G以(?)(1,2k+1,2l+1)为其生成子图.其中(?)(1,2k+1,2l+1)是有一条公共边的两个奇圈的并.

关键词：哈密尔顿连通哈密尔顿路笛卡尔积 3*-连通

在线全文

同方学位论文库

学校读者我要写书评

暂无评论

蜻蜓网络的泛圈性与哈密尔顿性

蜻蜓网络的泛圈性与哈密尔顿性

作者：霍谨太原理工大学

学位级别：硕士

蜻蜓网络使用一组路由器作为虚拟路由器,具有直径小、低延迟、低成本、高带宽等特点,在数据交换方面具有显著优势,因而在高性能计算系统(HPC)的应用中有很大的发展潜力.本文选择无平行链路、相对全局链路连接方式的蜻蜓网络D(n,h)进行研... 详细信息

蜻蜓网络使用一组路由器作为虚拟路由器,具有直径小、低延迟、低成本、高带宽等特点,在数据交换方面具有显著优势,因而在高性能计算系统(HPC)的应用中有很大的发展潜力.本文选择无平行链路、相对全局链路连接方式的蜻蜓网络D(n,h)进行研究.互连网络在图论中可以表示为一个简单无向图,网络中的一个路由器用图中的一个点来表示,两个路由器间的链路则用图中的一条边来表示.这样,对互连网络的拓扑结构的研究就转化为对图的结构进行研究.一个图G中若包含哈密尔顿圈,则称图G是哈密尔顿的.若图G中存在3到|V(G)|长的所有圈,则称图G是泛圈的.若对图G中任意一点u,过点u存在3到|V(G)|长的所有圈,则称图G是点泛圈的.若图G中任意不同的两点间均存在哈密尔顿路,则称图G是哈密尔顿连通的.若去掉不超过l个点后图G依然是哈密尔顿的,则称图G是l-点故障哈密尔顿的.本文主要对蜻蜓网络D(n,h)的哈密尔顿性、泛圈性、点故障哈密尔顿性等进行研究,得到的主要结论如下:1.在第二章中,我们首先证明了当n ≥ 1,h ≥ 2时,蜻蜓网络D(n,h)是哈密尔顿的;随后进一步证明了当n ≥ 4,h≥ 2时,D(n,h)是泛圈的,并且是点泛圈的、哈密尔顿连通的.2.在第三章中,我们首先证明了去掉任意多个组内坐标不为0或n-1的点,D(n,h)总是哈密尔顿的,并在此基础上进一步证明了当n ≥ 4,h≥ 2时,D(n,h)是2-点故障哈密尔顿的.

关键词：蜻蜓网络哈密尔顿泛圈点泛圈哈密尔顿连通点故障哈密尔顿

在线全文

同方学位论文库

学校读者我要写书评

暂无评论

立方图的可圈性

湖北大学学报（自然科学版） 2009年第3期31卷 232-234,240页

作者：陈晶晶胡智全王艳武汉科技学院外经贸学院湖北武汉430079 华中师范大学数学与统计学院湖北武汉430079 军事经济学院基础部湖北武汉430035

图的可圈性是哈密尔顿性的一个推广.设G是有向图,如果对G的每一个定向D,都存在S(D)V(G)使在D中改变所有恰与S(D)中一个顶点相关联的弧的方向后所得到的图为有向哈密尔顿图,则称G为可圈图.证明至少含5个顶点的连通图G的立方图是可圈图当... 详细信息

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

关键词：可圈性哈密尔顿路哈密尔顿连通哈密尔顿图立方图

在线全文

学校读者我要写书评

暂无评论

竞赛图和线图中的不交圈

竞赛图和线图中的不交圈

作者：王茂群太原理工大学

学位级别：硕士

竞赛图和线图是两类经典的图类,而研究竞赛图和线图中不交圈是一个很重要的课题.本文我们首先研究了竞赛图中点不交圈的问题.Bermond和Thomassen 猜想:对于任何正整数r,最小出度至少为2r-1的有向图包含至少r个点不交有向圈.在2014年,Ban... 详细信息

竞赛图和线图是两类经典的图类,而研究竞赛图和线图中不交圈是一个很重要的课题.本文我们首先研究了竞赛图中点不交圈的问题.Bermond和Thomassen 猜想:对于任何正整数r,最小出度至少为2r-1的有向图包含至少r个点不交有向圈.在2014年,Bang-Jensen,Bessy和Thomasse证明该猜想在竞赛图中成立.随后Lichiardopol证明2r-1-正则竞赛图包含至少7/6r-7/3个点不交有向圈.在这篇文章中,我们证明了Lichiardopol的结论在一般竞赛图上仍然成立.在2010年,Lichiardopol又提出猜想:最小出度至少为(q-1)r-1的竞赛图包含至少r个点不交q-圈,这里q ≥ 3,r ≥ 1.在本文中,我们证明当r = 2时,Lichiardopol猜想成立.其次,我们还研究了线图的哈密尔顿性及其边不交哈密尔顿圈数目问题.哈密尔顿问题是图论中的经典问题,但众所周知哈密尔顿圈的存在性问题是一个NP-完全问题.对于任一整数s ≥ 0,如果图G中任何点子集S(?)V(G)满足|S|≤3且G-S是哈密尔顿的,那么称图G是s-哈密尔顿的.在这篇文章中,我们证明原图是平面图的4-连通线图是哈密尔顿连通的和2-哈密尔顿的.该结果推广了赖虹建教授在[Every 4-connected line graph of a planar graph is hamil-tonian,Graph and Combinatorics 10(1994)249-253]中的结果.Bermond 猜想:如果一个图是哈密尔顿可分的那么它的线图也是哈密尔顿可分的.现在围绕这一猜想已有许多结果,在文中我们给出了该猜想的部分结果.众所周知,如果一个图G包含一个生成闭迹,则线图L(G)是哈密尔顿的.最近,李浩教授等人证明了如果最小度至少为4k且至少有k个边不交生成闭迹的图G,其线图L(G)包含k个边不交哈密尔顿圈.在文中,我们证明如果最小度至少为4k且至少有k个边不交哈密尔顿圈的图G,其线图L(G)包含至少2k个边不交哈密尔顿圈.

关键词：竞赛图线图 Lichiardopol猜想 Bermond猜想点不交q-圈哈密尔顿连通平面图 2-哈密尔顿边不交哈密尔顿圈

在线全文

同方学位论文库

学校读者我要写书评

暂无评论

立方图的可圈性

立方图的可圈性

作者：张利华中师范大学

学位级别：硕士

图的可圈性是哈密尔顿性的一个推广,设G是有向图,如果对G的每一个定向D,都存在S(D)(?)V(G)使在D中改变所有恰与S(D)中一个顶点相关联的弧的方向后所得到的图为有向哈密尔顿图,则称G为可圈图,本文将证明至少含五个顶点的连通图G的立方图... 详细信息

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

关键词：可圈性哈密尔顿路哈密尔顿连通哈密尔顿图立方图