Geodesic
Traceability of locally hamiltonian and locally traceable graphs
Discrete mathematics & theoretical computer science, Tome 17 (2015-2016) no. 3.

Voir la notice de l'article provenant de la source Episciences

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. 
@article{DMTCS_2016_17_3_a0,
     author = {De Wet, Johan and Van Aardt, Susan},
     title = {Traceability of locally hamiltonian and locally traceable graphs},
     journal = {Discrete mathematics & theoretical computer science},
     publisher = {mathdoc},
     volume = {17},
     number = {3},
     year = {2015-2016},
     doi = {10.46298/dmtcs.2144},
     language = {en},
     url = {http://geodesic.mathdoc.fr/articles/10.46298/dmtcs.2144/}
}
TY  - JOUR
AU  - De Wet, Johan
AU  - Van Aardt, Susan
TI  - Traceability of locally hamiltonian and locally traceable graphs
JO  - Discrete mathematics & theoretical computer science
PY  - 2015-2016
VL  - 17
IS  - 3
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/articles/10.46298/dmtcs.2144/
DO  - 10.46298/dmtcs.2144
LA  - en
ID  - DMTCS_2016_17_3_a0
ER  - 
%0 Journal Article
%A De Wet, Johan
%A Van Aardt, Susan
%T Traceability of locally hamiltonian and locally traceable graphs
%J Discrete mathematics & theoretical computer science
%D 2015-2016
%V 17
%N 3
%I mathdoc
%U http://geodesic.mathdoc.fr/articles/10.46298/dmtcs.2144/
%R 10.46298/dmtcs.2144
%G en
%F DMTCS_2016_17_3_a0
De Wet, Johan; Van Aardt, Susan. Traceability of locally hamiltonian and locally traceable graphs. Discrete mathematics & theoretical computer science, Tome 17 (2015-2016) no. 3. doi : 10.46298/dmtcs.2144. http://geodesic.mathdoc.fr/articles/10.46298/dmtcs.2144/

Cité par Sources :