Maximal nontraceable graphs with toughness less than one.
Bullock, Frank; Frick, Marietjie; Singleton, Joy; van Aardt, Susan; Mynhardt, Kieka (C.M.) — 2008
The Electronic Journal of Combinatorics [electronic only]
Maximal nontraceable graphs with toughness less than one.
A traceability conjecture for oriented graphs.
Hamiltonicity of -traceable graphs.
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-traceable oriented graph is traceable.
Independent Detour Transversals in 3-Deficient Digraphs
In 1982 Laborde, Payan and Xuong [Independent sets and longest directed paths in digraphs, in: Graphs and other combinatorial topics (Prague, 1982) 173-177 (Teubner-Texte Math., 59 1983)] conjectured that every digraph has an independent detour transversal (IDT), i.e. an independent set which intersects every longest path. Havet [Stable set meeting every longest path, Discrete Math. 289 (2004) 169-173] showed that the conjecture holds for digraphs with independence number two. A digraph is p-deficient...
The directed path partition conjecture
The Directed Path Partition Conjecture is the following: If D is a digraph that contains no path with more than λ vertices then, for every pair (a,b) of positive integers with λ = a+b, there exists a vertex partition (A,B) of D such that no path in D⟨A⟩ has more than a vertices and no path in D⟨B⟩ has more than b vertices. We develop methods for finding the desired partitions for various classes of digraphs.
Page 1