Skip to Main content Skip to Navigation
Journal articles

Traceability of locally hamiltonian and locally traceable graphs

Abstract : If $\mathcal{P}$ is a given graph property, we say that a graph $G$ is locally $\mathcal{P}$ if $\langle N(v) \rangle$ has property $\mathcal{P}$ for every $v \in V(G)$ where $\langle N(v) \rangle$ is the induced graph on the open neighbourhood of the vertex $v$. Pareek and Skupien (C. M. Pareek and Z. Skupien , On the smallest non-Hamiltonian locally Hamiltonian graph, J. Univ. Kuwait (Sci.), 10:9 - 17, 1983) posed the following two questions. Question 1 Is 9 the smallest order of a connected nontraceable locally traceable graph? Question 2 Is 14 the smallest order of a connected nontraceable locally hamiltonian graph? We answer the second question in the affirmative, but show that the correct number for the first question is 10. We develop a technique to construct connected locally hamiltonian and locally traceable graphs that are not traceable. We use this technique to construct such graphs with various prescribed properties.
Document type :
Journal articles
Complete list of metadata

Cited literature [11 references]  Display  Hide  Download

https://hal.inria.fr/hal-01352838
Contributor : Coordination Episciences Iam Connect in order to contact the contributor
Submitted on : Tuesday, August 16, 2016 - 5:45:46 PM
Last modification on : Monday, October 19, 2020 - 8:00:03 PM
Long-term archiving on: : Thursday, November 17, 2016 - 10:35:29 AM

File

2800-9958-1-PB.pdf
Explicit agreement for this submission

Identifiers

Collections

Citation

Johan de Wet, Susan van Aardt. Traceability of locally hamiltonian and locally traceable graphs. Discrete Mathematics and Theoretical Computer Science, DMTCS, 2016, Vol. 17 no. 3 (3), pp.245-262. ⟨10.46298/dmtcs.2144⟩. ⟨hal-01352838⟩

Share

Metrics

Record views

75

Files downloads

684