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.
Type de document :
Article dans une revue
Discrete Mathematics and Theoretical Computer Science, DMTCS, 2016, Vol. 17 no. 3 (3), pp.245-262
Liste complète des métadonnées

Littérature citée [11 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/hal-01352838
Contributeur : Coordination Episciences Iam <>
Soumis le : mardi 16 août 2016 - 17:45:46
Dernière modification le : jeudi 7 septembre 2017 - 01:03:45
Document(s) archivé(s) le : jeudi 17 novembre 2016 - 10:35:29

Fichier

2800-9958-1-PB.pdf
Accord explicite pour ce dépôt

Identifiants

  • HAL Id : hal-01352838, version 1

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. 〈hal-01352838〉

Partager

Métriques

Consultations de la notice

61

Téléchargements de fichiers

75