Every 8-Traceable Oriented Graph Is Traceable

A digraph of order n is k-traceable if n ≥ k and each of its induced subdigraphs of order k is traceable. It is known that if 2 ≤ k ≤ 6, every k-traceable oriented graph is traceable but for k = 7 and for each k ≥ 9, there exist k-traceable oriented graphs that are nontraceable. We show that every 8...

Full description

Bibliographic Details
Main Author: Aardt Susan A. van
Format: Article
Language:English
Published: University of Zielona Góra 2017-11-01
Series:Discussiones Mathematicae Graph Theory
Subjects:
Online Access:https://doi.org/10.7151/dmgt.1966
Description
Summary:A digraph of order n is k-traceable if n ≥ k and each of its induced subdigraphs of order k is traceable. It is known that if 2 ≤ k ≤ 6, every k-traceable oriented graph is traceable but for k = 7 and for each k ≥ 9, there exist k-traceable oriented graphs that are nontraceable. We show that every 8-traceable oriented graph is traceable.
ISSN:2083-5892