Indexed by:
Abstract:
A digraph D of order n is k-traceable if n >= k and every induced subdigraph of D of order k is traceable. An oriented graph is a digraph without directed cycles of length two. The Traceability Conjecture (van Aardt et al. (2008) [6]) states that any k-traceable oriented graph of order at least 2k-1 is traceable for k >= 2.In this paper, we study the Traceability Conjecture under forbidden subdigraphs conditions. We firstly verify that any k-traceable oriented graph D without directed cycles of length 4 but containing induced directed cycles of length at least 5 has order at most 2k-3. This strengthens a result of van Aardt et al. (2011) [5] as well as a result of Lichiardopol (2016) [10]. We also show that every k-traceable oriented graph of order n >= 3k-3 without two directed triangles mutually sharing a unique common arc is traceable, which in a sense extends another result of Lichiardopol.(c) 2023 Elsevier B.V. All rights reserved.
Keyword:
Reprint 's Address:
Email:
Version:
Source :
DISCRETE MATHEMATICS
ISSN: 0012-365X
Year: 2024
Issue: 1
Volume: 347
0 . 7 0 0
JCR@2023
CAS Journal Grade:4
Cited Count:
SCOPUS Cited Count:
ESI Highly Cited Papers on the List: 0 Unfold All
WanFang Cited Count:
Chinese Cited Count:
30 Days PV: 1
Affiliated Colleges: