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...
| Main Author: | |
|---|---|
| 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 |
| _version_ | 1797757698485256192 |
|---|---|
| author | Aardt Susan A. van |
| author_facet | Aardt Susan A. van |
| author_sort | Aardt Susan A. van |
| collection | DOAJ |
| description | 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. |
| first_indexed | 2024-03-12T18:19:20Z |
| format | Article |
| id | doaj.art-85b9dbbeab4d4f6e8345567d92087271 |
| institution | Directory Open Access Journal |
| issn | 2083-5892 |
| language | English |
| last_indexed | 2024-03-12T18:19:20Z |
| publishDate | 2017-11-01 |
| publisher | University of Zielona Góra |
| record_format | Article |
| series | Discussiones Mathematicae Graph Theory |
| spelling | doaj.art-85b9dbbeab4d4f6e8345567d920872712023-08-02T08:59:14ZengUniversity of Zielona GóraDiscussiones Mathematicae Graph Theory2083-58922017-11-0137496397310.7151/dmgt.1966dmgt.1966Every 8-Traceable Oriented Graph Is TraceableAardt Susan A. van0Department of Mathematical Sciences University of South Africa P.O. Box 392, Unisa, 0003 South AfricaA 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.https://doi.org/10.7151/dmgt.1966oriented graphtraceablehypotraceablek-traceablegeneralized tournament |
| spellingShingle | Aardt Susan A. van Every 8-Traceable Oriented Graph Is Traceable Discussiones Mathematicae Graph Theory oriented graph traceable hypotraceable k-traceable generalized tournament |
| title | Every 8-Traceable Oriented Graph Is Traceable |
| title_full | Every 8-Traceable Oriented Graph Is Traceable |
| title_fullStr | Every 8-Traceable Oriented Graph Is Traceable |
| title_full_unstemmed | Every 8-Traceable Oriented Graph Is Traceable |
| title_short | Every 8-Traceable Oriented Graph Is Traceable |
| title_sort | every 8 traceable oriented graph is traceable |
| topic | oriented graph traceable hypotraceable k-traceable generalized tournament |
| url | https://doi.org/10.7151/dmgt.1966 |
| work_keys_str_mv | AT aardtsusanavan every8traceableorientedgraphistraceable |