无爪图中2-哈密顿性的一个闭包

《Discrete Mathematics》:A closure for 2-hamiltonicity in claw-free graphs

【字体: 大 中 小 】 时间:2026年09月23日 来源:Discrete Mathematics 1.1

编辑推荐:

   摘要我们引入一种闭包运算,将无爪图G转换为图Gˉ,使得G是Gˉ的生成子图,Gˉ是某个多图的线图,且Gˉ是2-哈密顿的当且仅当G是2-哈密顿的。我们还给出了若干应用。章节摘要术语与符号本文中,用图表示有限简单无向图G=(V(G),E(G));若允许多重边,我们总是称之为多图。我

  

摘要

我们引入一种闭包运算,将无爪图G转换为图Gˉ,使得G是Gˉ的生成子图,Gˉ是某个多图的线图,且Gˉ是2-哈密顿的当且仅当G是2-哈密顿的。我们还给出了若干应用。

章节摘要

术语与符号

本文中,用图表示有限简单无向图G=(V(G),E(G));若允许多重边,我们总是称之为多图。我们通常遵循最通用的图论符号和术语,关于基本概念和符号请参见例如[2]。具体而言,若图F是G的子图,我们记作F?G,若F是G的诱导子图,则记作
。若G不包含图F作为诱导子图的副本,则称G为F-自由图。具体而言,

预备知识

本节总结我们在证明中将用到的一些已知结果。

2-哈密顿性的闭包

本节给出一种构造方法,对于给定的无爪图G,得到它的2-哈密顿闭包(缩写为2h-闭包)。
设G为无爪图,设Gˉ为由以下构造从G得到的图。
  • 1.
    若G不是4-连通的,选取一个顶点割M?V(G),其中|M|≤3,记G1,G2为G?M的连通分支,并令Gˉ=(V(G),E(KV(G1)∪M)∪E(KV(G2)∪M))。
  • 2.
    若G是4-连通且2-哈密顿的,令Gˉ=cl(G)。
  • 3.
    若G是4-连通但不是2-哈密顿的,则Gˉ按如下方式获得。
    • a)

主要结果

以下定理是本文的主要结果。

定理1

设G是连通的无爪图,设Gˉ是它的一个2h-闭包。则
  • 1.
    G是2-哈密顿的当且仅当Gˉ是2-哈密顿的,
  • 2.
    存在一个多图H使得Gˉ=L(H)。

证明

1. 若G不是4-连通的,或者G是4-连通且2-哈密顿的,则陈述1是显然的。若G是4-连通但不是2-哈密顿的(即Gˉ定义的第3步适用),则证明由定理E、定理I以及一个明显的事实得出

应用

1. 以下结果在[9]中得到证明。

定理L

[9] 每个最小度至少为6的5-连线图都是2-哈密顿的。
另一方面,以下结果在[20]中得到证明。

定理M

[20] 以下命题等价:
  • (i)
    每个4-连线图都是哈密顿的。
  • (ii)
    每个4-连通无爪图都是1-哈密顿连通的。
现在,若Thomassen猜想(定理M的陈述(i))为真,则任何5-连通无爪图都是2-哈密顿的,因为删除其任意一个顶点都得到一个4-连通的

结论性评述

注意,有时k-哈密顿性以稍强的方式定义,即当G?X对每个满足|X|≤k的X?V(G)都是哈密顿的时,称G为k-哈密顿的(而不是我们定义中的条件|X|=k)。因此,按此更强意义,图G是k-哈密顿的当且仅当(根据我们的定义)G对所有满足0≤s≤k的s都是s-哈密顿的(其中当然"0-哈密顿"意味着"哈密顿")。然而,[9]中也证明了每个最小度至少为6的5-连通无爪图都是
Zdeněk Ryjá?ek|Petr Vrána|Liming Xiong
相关新闻
生物通微信公众号
微信
新浪微博
  • 搜索
  • 国际
  • 国内
  • 人物
  • 产业
  • 热点
  • 科普

热点排行

    今日动态 | 人才市场 | 新技术专栏 | 中国科学人 | 云展台 | BioHot | 云讲堂直播 | 会展中心 | 特价专栏 | 技术快讯 | 免费试用

    版权所有 生物通

    Copyright© eBiotrade.com, All Rights Reserved

    联系信箱:

    粤ICP备09063491号