跳到主要导航 跳到搜索 跳到主要内容

Forbidden Pairs of disconnected graphs for traceability and hamiltonicity

  • Hongli Liao
  • , Qiang Wang
  • , Liming Xiong*
  • , Zhang Zhang
  • *此作品的通讯作者
  • Beijing Institute of Technology

科研成果: 期刊稿件文章同行评审

摘要

In this paper, we firstly characterize all forbidden pairs {R,S} for graphs with a spanning trail that are traceable and traceable graphs that are hamiltonian. There is no change of forbidden pairs for hamiltonicity if we impose a necessary condition of assumption that the graph is traceable; however, there is some difference of forbidden pairs for traceability if we impose a necessary condition that the graph has a spanning trail: different on two pairs of forbidden subgraphs {K1,3,Z2∪K1},{K1,4,Z1} (where Zi is the graph obtained by identifying a vertex of a K3 with an end-vertex of a Pi+1). As a byproduct, we prove that if G is a connected {K1,4,Z1}-free graph, then every subgraph G[T] induced by a trail T is traceable and every subgraph G[T] induced by a closed trail T is either hamiltonian or K2∨3K1.

源语言英语
页(从-至)105-114
页数10
期刊Discrete Applied Mathematics
371
DOI
出版状态已出版 - 15 8月 2025
已对外发布

指纹

探究 'Forbidden Pairs of disconnected graphs for traceability and hamiltonicity' 的科研主题。它们共同构成独一无二的指纹。

引用此