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

Disconnected forbidden pairs force supereulerian graphs to be hamiltonian

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

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

摘要

A graph is said to be supereulerian if it has a spanning eulerian subgraph, i.e., a spanning connected even subgraph. A graph is called hamiltonian if it contains a spanning cycle. A graph is said to be {R,S}-free if it does not contain R or S as an induced subgraph. Yang et al. characterized all pairs of connected graphs R,S such that every supereulerian {R,S}-free graph is hamiltonian. In this paper, we consider disconnected forbidden graph R,S. We characterize all pairs of disconnected graphs R,S such that every supereulerian {R,S}-free graph of sufficiently large order is hamiltonian. Applying this result, we also characterize all forbidden pairs for the existence of a Hamiltonian cycle in 2-edge connected graphs.

源语言英语
文章编号114301
期刊Discrete Mathematics
348
2
DOI
出版状态已出版 - 2月 2025

指纹

探究 'Disconnected forbidden pairs force supereulerian graphs to be hamiltonian' 的科研主题。它们共同构成独一无二的指纹。

引用此