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

Regular homogeneously traceable nonhamiltonian graphs

  • East China Normal University

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

摘要

A graph is called homogeneously traceable if every vertex is an endpoint of a Hamilton path. In 1979 Chartrand, Gould and Kapoor proved that for every integer n≥9, there exists a homogeneously traceable nonhamiltonian graph of order n. The graphs they constructed are irregular. Thus it is natural to consider the existence problem of regular homogeneously traceable nonhamiltonian graphs. We prove two results: (1) For every even integer n≥10, there exists a cubic homogeneously traceable nonhamiltonian graph of order n; (2) for every integer p≥18, there exists a 4-regular homogeneously traceable graph of order p and circumference p−4. Unsolved problems are posed.

源语言英语
页(从-至)60-64
页数5
期刊Discrete Applied Mathematics
310
DOI
出版状态已出版 - 31 3月 2022

指纹

探究 'Regular homogeneously traceable nonhamiltonian graphs' 的科研主题。它们共同构成独一无二的指纹。

引用此