Johan De Wet ; Susan Van Aardt - Traceability of locally hamiltonian and locally traceable graphs

dmtcs:2144 - Discrete Mathematics & Theoretical Computer Science, July 1, 2016, Vol. 17 no. 3 - https://doi.org/10.46298/dmtcs.2144
Traceability of locally hamiltonian and locally traceable graphsArticle

Authors: Johan De Wet ; Susan Van Aardt

    If $\mathcal{P}$ is a given graph property, we say that a graph $G$ is <i>locally</i> $\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. <b>Question 1</b> Is 9 the smallest order of a connected nontraceable locally traceable graph? <b>Question 2</b> 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.


    Volume: Vol. 17 no. 3
    Section: Graph Theory
    Published on: July 1, 2016
    Submitted on: May 3, 2015
    Keywords: nonhamiltonian, locally hamiltonian,locally traceable, nontraceable,[INFO.INFO-DM] Computer Science [cs]/Discrete Mathematics [cs.DM]

    Consultation statistics

    This page has been seen 484 times.
    This article's PDF has been downloaded 419 times.