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

来源 :新疆大学 | 被引量 : 0次 | 上传用户:skyman9907
下载到本地 , 更方便阅读
声明 : 本文档内容版权归属内容提供方 , 如果您对本文有版权争议 , 可与客服联系进行内容授权或下架
论文部分内容阅读
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)是有一条公共边的两个奇圈的并.
其他文献
移动机器人是提高生产力,解放劳动力,提高人们生活水平的重要手段,因此如何最大限度赋予移动机器人智能,实现自主导航与控制,深受国内外研究人员的关注。路径规划作为移动机
甜瓜是世界十大水果之一。甜瓜具有丰富的表型变异和遗传变异基础,特别是果实性状,如果实形状,果实皮色,果面沟、网纹、皱纹、裂纹,果肉厚度、颜色及糖酸含量等,而这些性状大多为重要的农艺性状,因此,果实性状的遗传改良一直是育种专家们共同关注的目标。种子形态特征也是甜瓜中一类重要的性状,不同材料种子大小、形状、颜色差异较大,饱满健康的种子是甜瓜苗期健壮发育以及后期产量和品质的基本保障。采用群体遗传学的方法
目的观察超声引导下前锯肌平面阻滞(serratus anterior plane block,SAPB)对胸腔镜手术老年患者应激反应及术后早期康复的影响。方法选取本院行择期胸腔镜下肺叶切除术老年患者80例,并使用随机数字表的方法将其分为2组(n=40):全身麻醉组(GA组)、SAPB联合全身麻醉组(SAPB组)。SAPB组患者在麻醉诱导前行SAPB。记录麻醉诱导前(T_0)、切皮即刻(T_1)、拔
太赫兹生物医学是当前光谱研究领域的前沿热点,其主要难点在于如何实现复杂生物体系组分的精准分析。本文旨在拓展太赫兹时域光谱技术在物质检测领域中的应用,选取典型的溶液
第三人撤销之诉制度是我国第三人事后保障程序中的关键内容,在一定程度上能遏制恶意诉讼、虚假诉讼等情形发生。考察制度的入法历程,2013年《民事诉讼法》的前两稿并未提及第三人撤销之诉,直到表决前夕才将其列入第三修正稿。第三人撤销之诉制度的设立是应急性的,缺乏实践调研与理论积累便草草入法。由于民事法律关系的复杂性、制度设计的模糊性以及过于追求运行的效率性,制度面临适格主体难以认定、与再审制度衔接不畅以及
在化学中有一些分子结构具有拓扑性质,我们想通过数学的方法研究这些分子结构的拓扑性质.拓扑指标是从化合物的结合图衍生出来的一种数学不变量,Harary指标与其它拓扑指标结
图的谱理论是代数图论的主要研究领域之一,起源于量子化学.1931年,E.Huickel提出了分子轨道理论,建立了分子轨道能级和分子图的谱之间的联系,大大推进了图的谱理论研究.图的
有向图D=(V,E)被称为是最优弧连通的,如果λ(D)=δ(D).此外,有向图D被称为是超弧连通的,如果每个最小的弧割都是其某个点的入弧集或者出弧集.以X1和X2为两部的一个有向二部图
本文是在前人对化学图类中六边形链的研究基础之上,研究了八边形链的Kekule结构与一类Caterpillar树的Hosoya指标之间的关系,最后将结果推广到多边形链中,降低了计算的复杂度
目的:探讨应用RNA恒温扩增实时荧光检测(SAT)技术检测儿童肺炎支原体(MP)感染病例咽拭子标本中MP-RNA的转阴时间规律、可能影响因素,及该检测方法对儿童MP感染的临床价值。方法:选取2019.06至2019.12于我院门诊及住院符合本研究纳入标准的儿童MP感染病例50例及同期最终排除MP近期感染的其他病原体感染者10例,收集其病例资料。针对最终入组的50例患儿,自入组后以发病时间为起点计每