Abstract
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.
| Original language | English |
|---|---|
| Pages (from-to) | 60-64 |
| Number of pages | 5 |
| Journal | Discrete Applied Mathematics |
| Volume | 310 |
| DOIs | |
| State | Published - 31 Mar 2022 |
Keywords
- Circumference
- Homogeneously traceable
- Regular graph
Fingerprint
Dive into the research topics of 'Regular homogeneously traceable nonhamiltonian graphs'. Together they form a unique fingerprint.Cite this
- APA
- Author
- BIBTEX
- Harvard
- Standard
- RIS
- Vancouver